1
$\begingroup$

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.

$\endgroup$

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.