We have a sensing matrix $\Phi$, satisfying the restricted isometry property (RIP), and a sparse signal $x$. We want to recover $\hat x$ from the measurement $y=\Phi x$ by using $l_1$-minimization.

I am wondering about, how the RIP can guarantee the uniqueness of the recovered sparse vector solution $\hat x$.

On slide 4, at 01:15 minute, Mark Davenport says in his presentation about compressed sensing:

The RIP is what we need to ensure, that this hyperplane is oriented in a way, that guarantees us, that there is actually only one sparse vector in this hyperplane. So we are going to be guaranteed to get the right answer.

But why is that? I do not see that the RIP can guarantee this.

For example, consider this picture below. It's a slide from the linked presentation. The blue hyperplane also intersects at least one other axis. How can we be sure, that this other sparse vector isn't the actual solution, i.e. was our formler signal $x$?

Screenshot of Mark Davenports slides

  • $\begingroup$ It seems we can't gain access to the video you referred us to. $\endgroup$ – Royi Apr 13 '16 at 6:28

Compressed sensing theory (see for example Candès & Wakin, 2008) states that, given you have enough measurements $y$, the shown $\ell_1$ minimisation problem recovers $x$ exactly with very high probability. This means that your correct solution must have the smallest possible $\ell_1$ norm.

This is what the figure shows; the "$\ell_1$ ball" intersects the plane given by $\Phi x' = y$ at the point $x'$ with the smallest $\ell_1$ norm. There are, as you mention, other sparse solutions - i.e. the ones where the plane intersects the other two axes. As we can imagine from the figure, these points however have larger $\ell_1$ norm and are therefore not the correct solution.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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