On the sparsity of LASSO minimizers in sparse data recovery

Abstract

We present a detailed analysis of the unconstrained ${\ell }_1$-weighted LASSO method for recovery of sparse data from its observation by randomly generated matrices, satisfying the Restricted Isometry Property (RIP) with constant $\delta <1$, and subject to negligible measurement and compressibility errors. We prove that if the data is $k$-sparse, then the size of support of the LASSO minimizer, $s$, maintains a comparable sparsity, $s\le C_{\delta }k$. For example, if $\delta =0.7$ then $s<11k$ and a slightly smaller $\delta =0.4$ yields $s<4k$. We also derive new ${\ell }_2/{\ell }_1$ error bounds which highlight precise dependence on $k$ and on the LASSO parameter $\lambda$, before the error is driven below the scale of negligible measurement/ and compressiblity errors.