A Simple Proof for Recoverability of L1-Minimization (II): the Nonnegativity Case
When using L1 minimization to recover a sparse, nonnegative solution to a under-determined linear system of equations, what is the highest sparsity level at which recovery can still be guaranteed? Recently, Donoho and Tanner discovered, by invoking classic results from the theory of convex polytopes that the highest sparsity level equals half of the number of equations. In this report, we provide a completely self-contained, yet short and elementary, proof for this remarkable result. We also connect dots for different recoverability conditions obtained from different spaces.
Citable link to this pagehttps://hdl.handle.net/1911/102041
MetadataShow full item record
- CAAM Technical Reports