Smoothed Analysis in Compressed Sensing

Arbitrary matricesM∈ Rm×n, randomly perturbed in an additive manner using a random matrixR∈ Rm×n, are shown to asymptotically almost surely satisfy the so-calledrobust null space property. Whilst insisting on an asymptotically optimal order of magnitude formrequired to attainunique reconstructionvia ℓ1-minimisation algorithms, our results track the level of arbitrariness allowed for the fixed seed matrixMas well as the degree of distributional irregularity allowed for the entries of the perturbing matrixR. Starting with sub-gaussian entries forR, our results culminate with these allowed to have substantially heavier tails than sub-exponential ones. Throughout this trajectory, two measures control the arbitrariness allowed forM; the first is ∥M∥∞ and the second is a localised notion of the Frobenius norm ofM(which depends on the sparsity of the signal being reconstructed). A key tool driving our proofs isMendelson’s small-ball method (Learning without concentration, J. ACM, Vol. 62, 2015).