I am specifically thinking about the reconstruction error of L1-minimization from compressed measurements with noise. I know a bound from (8) in The restricted isometry property and its implications for compressed sensing, but I was wondering if there is anything newer and or tighter that I am not aware of. Additionally, I would like to relate $\delta_{2s}$ to the size of e.g. a Gaussian measurement matrix. It seems I can do that from Lemma 3.1 and (3.22) in Decoding by linear programming, but how tight is (3.22) and can I get closer?


1 Answer 1


According to Michael McCoy on LinkedIn:

The best bound for Gaussian matrices is in: W. Xu and B. Hassibi, Precise Stability Phase Transitions for l1 Minimization: A Unified Geometric Framework, IEEE Trans. Inf. Theory. Oct. 2011

See, for example, the curves in Fig. 1.

  • 1
    $\begingroup$ Would please give out your understanding of the paper, in non-technical way, preferably? $\endgroup$
    – MimSaad
    Apr 11, 2017 at 9:30

Your Answer

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

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