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

-

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.


Speech

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


ECG, EEG

 SDR signal to distortion ratio


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

-