Tuesday, January 9, 2018

convex optimization - How Come RIP Guarantees Unique Restoration of the Sparse Solution by $ {L}_{1} $ Minimization?


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




No comments:

Post a Comment

digital communications - Understanding the Matched Filter

I have a question about matched filtering. Does the matched filter maximise the SNR at the moment of decision only? As far as I understand, ...