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