# How does one verify if a vector is really recovered?

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.

-
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.