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, privacy policy and cookie policy

Browse other questions tagged or ask your own question.