On the sparsity of LASSO minimizers in sparse data recovery

2020/04/09 by Simon Foucart, Eitan Tadmor, Foucart, Simon +4
Computer Science · Engineering · Mathematics · Medicine · #Mathematical Analysis and Transform Methods #Medical Imaging Techniques and Applications #Sparse and Compressive Sensing Techniques #cs.IT #math.FA #math.IT #msc:94A12 #msc:94A20

paper · pdf · doi:10.48550/arxiv.2004.04348

arxiv created 2022/03/14 · arxiv updated 2022/03/16

Abstract

We present a detailed analysis of the unconstrained ℓ₁-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 ℓ₂/ℓ₁ 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.

Related

• The Sparsity of LASSO-type Minimizers
• Sharp Support Recovery from Noisy Random Measurements by L1 minimization
• Information-theoretic limits on sparsity recovery in the high-dimensional and noisy setting
• Compressed Sensing over ℓ_p-balls: Minimax Mean Square Error
• Dictionary LASSO: Guaranteed Sparse Recovery under Linear Transformation