On the sparsity of LASSO minimizers in sparse data recovery
Institutional Repository Document
Overview
Research
Identity
View All
Overview
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, $sleq 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.