Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In compressed sensing, how to verify if a vector is really recovered or how does one plot the figures on recovery rate? Since in numerical experiments, there is always a difference between the original vector and the vector produced by compressed sensing algorithms.

share|cite|improve this question
Any helpful answers would be greatly appreciated! – nika Mar 10 '13 at 14:50
Can you give some context or examples for the benefit of people not intimately familiar with compressed sensing? – Rahul Mar 11 '13 at 8:05

Given the original sparse representation of $x \in \mathbb{R}^n$ over a dictionary $D_{n \times n}$, i.e. a sparse vector $s\in \mathbb{R}^n$ , you project $x$ over $m$ random i.i.d. subgaussian vectors (the rows of a matrix $A_{m \times n}$, usually i.i.d. Gaussian or symmetric Bernoulli) so that $$y = A x = A D s \in \mathbb{R}^m$$ with $m < n$. Optimization by linear programming yields $$\hat{s} = \min_{s \in \mathbb{R}^n} ||s||_1$$ $$s.t.$$ $$y = A D s$$

If the number of measurements $m \geq C k \log (n/k)$, where $k$ is the sparsity (the cardinality of the support of the original $s$), then $$||s - \hat{s}||^2_2$$ will be small because the sparsest solution is also the minimum $\ell_1$ solution for the given underdetermined linear system $y = A D s$.

As for performance figures, for a fixed $n$ you can plot the average reconstruction error $\mathbf{E}[||s - \hat{s}||^2_2]$ (or the SNR) over a Monte Carlo of sparse random vectors $s$ and measurement matrices $A$ for various $m$ and $k$. This may be misleading though, because it mixes low-error or perfect instances with critical instances for low values of $m$.

Another more effective alternative is plotting the probability $P(||s - \hat{s}||^2_2 > \zeta)$ with $\zeta$ a small precision threshold (e.g. $10^{-6}$), which is the probability of successful reconstruction, and count the number of instances in a Monte Carlo batch which are above/below this threshold. By plotting the PSR you should see a sharp phase transition phenomenon which has been studied here.

share|cite|improve this answer

Most of the times it depends on the signal under consideration.

E.g. Images

   PSNR for recovery or denoising.
   SSIM for structural similarity in segmentation problem.
   Edginess inrange image super-resolution.


   PESQ objective scores.
   MOS  subjective score or listener's test
   WER word error rate in reconstructed speech.


 SDR signal to distortion ratio

Apart for these in general average reconstruction error using ecludian norm, spectral difference etc.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.