What is "exact recovery"?

| No Comments
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."

Leave a comment

About this Entry

This page contains a single entry by Bob L. Sturm published on December 6, 2011 12:57 PM.

A simple example where BP fails and OMP succeeds was the previous entry in this blog.

Compressive Sampling Might Now Be Patented is the next entry in this blog.

Find recent content on the main index or look in the archives to find all content.