Total: 1
Arbitrary matrices M∈Rm×n, randomly perturbed in an additive manner using a random matrix R∈Rm×n, are shown to asymptotically almost surely satisfy the so-called {\sl robust null space property} whilst asymptotically meeting the optimal number of measurements required for {\sl unique reconstruction} via ℓ1-minimisation algorithms. A wide range of random perturbation matrices is considered; in that, R is allowed to be sub-gaussian, sub-exponential, as well as extremely heavy-tailed, where only the first logn moments of each entry of R are bounded. A key tool driving our proofs is {\sl Mendelson's small-ball method} ({\em Learning without concentration}, J. ACM, Vol. 62, 2015).