On the sparsity of LASSO minimizers in sparse data recovery
Published in Construtive Approximation, 2022
Recommended citation: Foucart, S. and Tadmor, E. and Zhong, M. (2022). "On the sparsity of LASSO minimizers in sparse data recovery." Construtive Approximation. https://link.springer.com/article/10.1007/s00365-022-09594-1
Abstract: 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 is 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<11k and a slightly smaller δ=0.4 yields s<4k. 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.