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.
Citable link to this pagehttps://hdl.handle.net/1911/102040
MetadataShow full item record
- CAAM Technical Reports