On the sparsity of LASSO minimizers in sparse data recovery Institutional Repository Document uri icon

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.

altmetric score

  • 0.5

author list (cited authors)

  • Foucart, S., Tadmor, E., & Zhong, M.

citation count

  • 0

complete list of authors

  • Foucart, Simon||Tadmor, Eitan||Zhong, Ming

Book Title

  • arXiv

publication date

  • April 2020