A Simple Proof for Recoverability of L1-Minimization: Go Over or Under?

It is well-known by now that L1 minimization can help recover sparse solutions to under-determined linear equations or sparsely corrupted solutions to over-determined equations, and the two problems are equivalent under appropriate conditions. So far almost all theoretic results have been obtained through studying the ``under-determined side'' of the problem. In this note, we take a different approach from the ``over-determined side'' and show that a recoverability result (with the best available order) follows almost immediately from an inequality of Garnaev and Gluskin. We also connect dots with recoverability conditions obtained from different spaces