Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
add comment

1 Answer

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|improve this answer
add comment

Your Answer

 
discard

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.