Suppose the received vector $y$ is generated from a vector $x^*$ as $y = { D}x^* + z$ for some ``dictionary" matrix ${D}$ and noise vector $z$ s.t for some $\epsilon >0$ we have, $\Vert z \Vert_2 \leq \epsilon$.

Now we solve the so-called $P_1^\epsilon$ optimization question to get, $\hat{x} := \min \Vert x \Vert_1 \text{ s.t } \Vert {D}x - y \Vert _2 \leq \epsilon$.

  • Then under certan RIP conditions on D and some constant $C$ it follows that, $\Vert x^* - \hat{x} \Vert \leq C \epsilon$. Can someone kindly reference me the exact theorem and proof of this statement?

Are there more general forms of such a result? I would be glad to get some references in that direction too.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.