On the Sparsity of LASSO Minimizers in Sparse Data Recovery.

We present a detailed analysis of the unconstrained ℓ 1 -weighted LASSO method for recovery of sparse data from its observation by randomly generated matrices, satisfying the restricted isometry property (RIP) with constant δ < 1 , and subject to negligible measurement and compressibility errors. We prove that if the data are k-sparse, then the size of support of the LASSO minimizer, s, maintains a comparable sparsity, s ⩽ C δ k . For example, if δ = 0.7 then s < 11 k and a slightly smaller δ = 0.4 yields s < 4 k . We also derive new ℓ 2 / ℓ 1 error bounds which highlight precise dependence on k and on the LASSO parameter λ , before the error is driven below the scale of negligible measurement/ and compressiblity errors. [ABSTRACT FROM AUTHOR]