What is “exact recovery”?

Since compressive sampling (CS) is all about signal acquisition, its faithful recoverability of sensed signals is of paramount importance. Thus, “exact recovery” is a good thing to measure when it comes time for experimental work. However, we find in the CS literature at least three definitions of “exact recovery”:

  1. When the signal support is recovered with no false alarms, and no missed detections;
  2. When the normalized squared model error is less than \(\epsilon^2\).
  3. When the largest magnitude difference in the model error is less than \(\epsilon\).

In a digital world of limited precision, the second and third definitions give trouble if we define \(\epsilon = 0\). Thus, this value is usually made a little larger. In Maleki and Donoho, e.g., they set \(\epsilon^2 = 0.0001\) in the second criterion. Others set it to \(\epsilon^2 = 0.000001\). Sometimes I find work that does not mention what value was used, or even the criterion for “exact recovery”! So what does this value mean? And how should it be set?


In my paper “When ‘exact recovery’ is exact recovery in compressive sampling“, I analyze the first and second “exact recovery” criteria, and show when they are equivalent, how to interpret \(\epsilon^2\), and an appropriate range over which to define it.
In short,

  • \(\epsilon^2\) sets the maximum acceptable false detection rate;
  • In the noiseless case, \(\epsilon^2 < 1/s\) for the two conditions to be equivalent for \(s\)-sparse signals a majority of the time, independent of how the sparse signal is distributed;
  • In the noisy case, with measurement noise of variance \(\sigma_v^2 > 0\), the parameter \(\epsilon^2 \ge \sigma_v^2/s\) so that the second condition can even be met
  • In the noisy case, with measurement noise of variance \(\sigma_v^2\), \(\epsilon^2 \le (k/s) + \sigma_v^2(1 – k/s)\) for the two conditions to be equivalent for \(s\)-sparse signals a majority of the time, independent of how the sparse signal is distributed.

Thus, we see that the acceptable range for this parameter is
$$
\epsilon^2 \in \left [\frac{\sigma_v^2}{s}, \frac{k}{s} + \sigma_v^2 \left (1 – \frac{k}{s}\right ) \right ]
$$
where \(k\) is the maximum acceptable number of support elements an \(s\)-sparse solution can be missing, and still be considered “exact.”

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s