# What is the tightest known bound on the reconstruction error in compressed sensing?

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

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.

• Would please give out your understanding of the paper, in non-technical way, preferably? – MimSaad Apr 11 '17 at 9:30