The Sparsity of LASSO-type Minimizers

2022/09/12 by Simon Foucart, Foucart, Simon
Computer Science · Mathematics · #Matrix Theory and Algorithms #Mathematical Inequalities and Applications #Advanced Optimization Algorithms Research

paper · pdf · doi:10.48550/arxiv.2209.04986

Abstract

This note extends an attribute of the LASSO procedure to a whole class of related procedures, including square-root LASSO, square LASSO, LAD-LASSO, and an instance of generalized LASSO. Namely, under the assumption that the input matrix satisfies an ℓ_p-restricted isometry property (which in some sense is weaker than the standard ℓ₂-restricted isometry property assumption), it is shown that if the input vector comes from the exact measurement of a sparse vector, then the minimizer of any such LASSO-type procedure has sparsity comparable to the sparsity of the measured vector. The result remains valid in the presence of moderate measurement error when the regularization parameter is not too small.

Related

• On the sparsity of LASSO minimizers in sparse data recovery
• The degrees of freedom of the Lasso for general design matrix
• Statistical Learning with Sparsity: The Lasso and Generalizations
• An Equivalence between the Lasso and Support Vector Machines
• Sharp thresholds for high-dimensional and noisy recovery of sparsity