A framework to characterize performance of LASSO algorithms

Abstract

In this paper we consider solving \emph{noisy} under-determined systems of linear equations with sparse solutions. A noiseless equivalent attracted enormous attention in recent years, above all, due to work of \cite{CRT,CanRomTao06,DonohoPol} where it was shown in a statistical and large dimensional context that a sparse unknown vector (of sparsity proportional to the length of the vector) can be recovered from an under-determined system via a simple polynomial ${\ell }_1$-optimization algorithm. \cite{CanRomTao06} further established that even when the equations are \emph{noisy}, one can, through an SOCP noisy equivalent of ${\ell }_1$, obtain an approximate solution that is (in an ${\ell }_2$-norm sense) no further than a constant times the noise from the sparse unknown vector. In our recent works \cite{StojnicCSetam09,StojnicUpper10}, we created a powerful mechanism that helped us characterize exactly the performance of ${\ell }_1$ optimization in the noiseless case (as shown in \cite{StojnicEquiv10} and as it must be if the axioms of mathematics are well set, the results of \cite{StojnicCSetam09,StojnicUpper10} are in an absolute agreement with the corresponding exact ones from \cite{DonohoPol}). In this paper we design a mechanism, as powerful as those from \cite{StojnicCSetam09,StojnicUpper10}, that can handle the analysis of a LASSO type of algorithm (and many others) that can be (or typically are) used for "solving" noisy under-determined systems. Using the mechanism we then, in a statistical context, compute the exact worst-case ${\ell }_2$ norm distance between the unknown sparse vector and the approximate one obtained through such a LASSO. The obtained results match the corresponding exact ones obtained in \cite{BayMon10,DonMalMon10}. Moreover, as a by-product of our analysis framework we recognize existence of an SOCP type of algorithm that achieves the same performance.

References in corpus (13)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Simultaneous analysis of Lasso and Dantzig selector
• Sharp thresholds for high-dimensional and noisy recovery of sparsity
• The Dantzig selector and sparsity oracle inequalities
• Algorithmic linear dimension reduction in the l_1 norm for sparse vectors
• Various thresholds for ${\ell }_1$-optimization in compressed sensing
• Discussion: The Dantzig selector: Statistical estimation when $p$ is much larger than $n$
• Discussion: The Dantzig selector: Statistical estimation when $p$ is much larger than $n$
• Subspace Pursuit for Compressive Sensing Signal Reconstruction
• Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling
• Upper-bounding ${\ell }_1$-optimization weak thresholds
• The LASSO risk for gaussian matrices
• A rigorous geometry-probability equivalence in characterization of ${\ell }_1$-optimization

Cited by in corpus (44)

• The LASSO with Non-linear Measurements is Equivalent to One With Linear Measurements
• Learning curves of generic features maps for realistic datasets with a teacher-student model
• Symbol Error Rate Performance of Box-relaxation Decoders in Massive MIMO
• The Lasso with general Gaussian designs with applications to hypothesis testing
• The achievable performance of convex demixing
• The Impact of Regularization on High-dimensional Logistic Regression
• Phase Retrieval via Polytope Optimization: Geometry, Phase Transitions, and New Algorithms
• A Precise High-Dimensional Asymptotic Theory for Boosting and Minimum-${\ell }_1$-Norm Interpolated Classifiers
• The Gaussian min-max theorem in the Presence of Convexity
• A Model of Double Descent for High-dimensional Binary Linear Classification
• Sharp MSE Bounds for Proximal Denoising
• Don't Just Blame Over-parametrization for Over-confidence: Theoretical Analysis of Calibration in Binary Classification
• Precise Error Analysis of Regularized M-estimators in High-dimensions
• Fundamental Limits of Ridge-Regularized Empirical Risk Minimization in High Dimensions
• Statistical and Algorithmic Insights for Semi-supervised Learning with Self-training
• Phase Transitions in Transfer Learning for High-Dimensional Perceptrons
• On the Inherent Regularization Effects of Noise Injection During Training
• Theoretical Insights Into Multiclass Classification: A High-dimensional Asymptotic View
• Asymptotically Exact Error Analysis for the Generalized ${\ell }_2^2$-LASSO
• Sharp recovery bounds for convex demixing, with applications
• Label-Imbalanced and Group-Sensitive Classification under Overparameterization
• Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfitting
• Sharp Asymptotics and Optimal Performance for Inference in Binary Models
• Precise Error Analysis of the LASSO under Correlated Designs
• Derivatives and residual distribution of regularized M-estimators with application to adaptive tuning
• Local convexity of the TAP free energy and AMP convergence for Z2-synchronization
• CAD: Debiasing the Lasso with inaccurate covariate model
• Out-of-sample error estimate for robust M-estimators with convex penalty
• On the best choice of Lasso program given data parameters
• Asymptotic Behavior of Adversarial Training in Binary Classification
• Optimum GSSK Transmission in Massive MIMO Systems Using the Box-LASSO Decoder
• Minimum ${\ell }_1$-norm interpolators: Precise asymptotics and multiple descent
• Understanding the Under-Coverage Bias in Uncertainty Estimation
• Learning Gaussian Mixtures with Generalised Linear Models: Precise Asymptotics in High-dimensions
• The Performance Analysis of Generalized Margin Maximizer (GMM) on Separable Data
• The Limiting Poisson Law of Massive MIMO Detection with Box Relaxation
• Asymptotic normality of robust $M$-estimators with convex penalty
• BER Analysis of the box relaxation for BPSK Signal Recovery
• Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspective
• A simple bound on the BER of the MAP decoder for massive MIMO systems
• Concentration of the Frobenius norm of generalized matrix inverses
• Robustifying Binary Classification to Adversarial Perturbation
• Precise Performance Analysis of the LASSO under Matrix Uncertainties
• Beyond Independent Measurements: General Compressed Sensing with GNN Application