Smoothed analysis in compressed sensing

Elad Aigner-Horev, Dan Hefetz, Michael Trushkin

Arbitrary matrices $M\in {\mathbb{R}}^{m\times n}$, randomly perturbed in an additive manner using a random matrix $R\in {\mathbb{R}}^{m\times n}$, are shown to asymptotically almo…