The LASSO risk for gaussian matrices

Mohsen Bayati; Andrea Montanari

Source-linked AI summary

The LASSO risk for gaussian matrices

Mohsen Bayati, Andrea Montanari

arXiv:1008.2581v3Aug 16, 2010math.STcs.IT

TL;DR

The paper asks for an exact asymptotic characterization of LASSO risk when recovering sparse signals from noisy linear measurements. It analyzes AMP for iid Gaussian measurement matrices and proves that the normalized LASSO mean squared error converges to an explicit limit, with simulations suggesting relevance beyond the proved setting.

Problem
Earlier LASSO-related mean squared error results provided bounds only up to unknown or logarithmic multiplicative factors, motivating asymptotically exact expressions.
Method
The proof analyzes AMP and its state evolution, then establishes the connection between the AMP limit and the exact LASSO optimum for iid Gaussian matrices.
Results
The normalized LASSO risk converges almost surely to an explicit asymptotic expression characterized by τ∗ and θ∗ for Gaussian matrix sequences.
Takeaways & Limitations
The formulas are reported as accurate on problems with a few hundreds of variables and encouraging on continuous and binary real-data matrices.
Takeaways & Limitations
The rigorous theorem applies to converging sequences with iid Gaussian measurement matrices, while broader matrix universality is presented as an expectation or supported direction rather than proved here.

Abstract

from arXiv · show

We consider the problem of learning a coefficient vector x_0\in R^N from noisy linear observation y=Ax_0+w \in R^n. In many contexts (ranging from model selection to image processing) it is desirable to construct a sparse estimator x'. In this case, a popular approach consists in solving an L1-penalized least squares problem known as the LASSO or Basis Pursuit DeNoising (BPDN). For sequences of matrices A of increasing dimensions, with independent gaussian entries, we prove that the normalized risk of the LASSO converges to a limit, and we obtain an explicit expression for this limit. Our result is the first rigorous derivation of an explicit formula for the asymptotic mean square error of the LASSO for random instances. The proof technique is based on the analysis of AMP, a recently developed efficient algorithm, that is inspired from graphical models ideas. Simulations on real data matrices suggest that our results can be relevant in a broad array of practical applications.

1 Introduction

The paper develops rigorous asymptotic characterizations of LASSO mean squared error for Gaussian measurement matrices, addressing limitations of earlier rough bounds. It derives these results through AMP analysis and connects the resulting formulas to practical behavior and parameter mappings.

Problem: The paper studies reconstructing an unknown vector from noisy linear measurements and uses LASSO/BPDN when sparse solutions are desired.The observations are modeled using a known measurement matrix and noise, with mean squared error as the main performance metric.
Problem: Earlier results bounded LASSO-related mean squared error only up to an unknown factor or a factor C log N under different assumptions.This motivates seeking asymptotically exact expressions rather than rough performance guarantees.
Main result: The paper proves asymptotically exact mean squared error expressions almost surely for increasing problem sequences with fixed aspect ratio and iid Gaussian measurement entries.The signal and noise sequences are deterministic, while randomness is in the Gaussian measurement matrices.
Novelty: The paper’s proof strategy is algorithmic: it characterizes an iterative AMP procedure and proves that its limit reaches the exact LASSO optimum.This differs from earlier approaches based on constructing approximate optima or dual witnesses.
Method: The proof analyzes AMP, whose effective observations behave asymptotically like the signal corrupted by Gaussian noise, followed by componentwise soft thresholding.The AMP state evolution is characterized through the recursion involving τ_t and the function F.
Main result: The AMP recursion converges to the largest fixed-point solution, and the LASSO estimator has an asymptotic characterization using τ∗ and θ∗ linked to α(λ).The parameter mapping α → λ(α) is continuous and uniquely invertible for positive λ and σ2 under the stated assumptions.
Scope and implications: The rigorous proof is specific to Gaussian matrices, although the authors expect the mean squared error prediction to extend to broader matrix families.The paper presents simulations on continuous gene-expression and binary hospital-record matrices, while emphasizing that universality remains an expectation or supported conjecture rather than the main theorem.
Scope and implications: The high-dimensional result requires taking N →∞ before the iteration limit, while simulations report accuracy on problems with a few hundreds of variables.The analysis also suggests convergence rates of order log(1/ε) above a phase-transition sampling ratio and encouraging behavior on real data matrices.

2 Numerical illustrations

Numerical simulations compare the asymptotic LASSO risk prediction with results from real-data and random matrices. The agreement is reported as good even for problems with dimensions of a few hundred, and the prediction can guide regularization selection.

Scope: The theorem assumes iid Gaussian measurement matrices, although the authors expect the MSE prediction to be robust for a much larger family of matrices.The reported broader applicability is supported by simulations and related rigorous evidence, rather than by the theorem’s stated assumptions.
Experimental setup: N was varied over 200, 500, 1000, and 2000 while the aspect ratio was fixed at δ = 0.64.The estimator was computed using CVX and OWLQN across several λ values between 0 and 2.
Results: The agreement between empirical MSE and the asymptotic prediction was remarkably good when N and n were of the order of a few hundreds.The observed deviations were consistent with statistical fluctuations.
Measurement matrices: The simulations used real continuous, sparse binary, Gaussian, and random ±1 measurement matrices with fixed aspect ratio δ.The real datasets included gene-expression measurements and patient records with binary medical and demographic features.
Results: The asymptotic prediction has a minimum as a function of λ, whose location can be used to select the regularization parameter.This behavior was reported for the random ±1 matrix simulations.

3 A structural property and proof of the main results

This section develops the structural lemmas and proof steps connecting AMP estimates to the LASSO solution, then describes simulations across several matrix ensembles.

The proof of Theorem 1.8 combines a structural property from Section 3.2 with auxiliary lemmas from Section 3.3.
Numerical comparisons: The simulations compare MSE versus λ with asymptotic predictions for gene-expression, hospital-record, Gaussian, and random ±1 matrices.
Proof conclusion: The LASSO proof concludes by taking the large-system limit and then the AMP-iteration limit, with convergence holding eventually almost surely.
Structural property: The structural lemma establishes singular-value bounds for submatrices associated with nearly active coordinates and small additional supports.
Auxiliary bounds: The proof controls AMP and LASSO estimates using bounded norms, approximate optimality, nonsingularity, and convergence of AMP iterates.

4 State evolution estimates

This section applies AMP state evolution to characterize the asymptotic behavior of iterates and residuals, using Gaussian limits and recursive covariance parameters.

AMP is treated as a special case of a general iterative procedure, with updates expressed through scalar functions and correction coefficients.
Technical issue: A discontinuous derivative requires separate handling before weak-convergence arguments can be applied to the empirical coordinate distribution.
State evolution: State evolution represents AMP coordinates asymptotically through X0 plus jointly Gaussian variables whose covariances follow a recursion.
Asymptotic characterization: For iid-normal matrices with variance 1/n, pseudo-Lipschitz functions of AMP iterates converge almost surely to corresponding state-evolution expectations.
Convergence: The AMP estimates and residuals converge asymptotically under the conditions of Theorem 1.5.

5 Proofs of auxiliary lemmas

The auxiliary proofs establish boundedness, approximate optimality, and spectral properties needed to transfer AMP state-evolution results to the LASSO estimator.

State evolution bounds the normalized squared norm of AMP iterates, providing the first step toward controlling the LASSO estimator.
Norm control: Random-matrix singular-value estimates control components of the LASSO estimator in the kernel and its orthogonal complement.
Approximate optimality: The AMP iterates have subgradients with small residuals, so they become approximate minima of the LASSO cost function.
Spectral properties: Conditioned AMP subspaces retain bounded Gram matrices and restricted minimum singular values, supporting the required nonsingularity arguments.
Iterate control: The covariance recursion yields positive-definite covariance matrices and bounds differences between sufficiently late AMP iterates.

A.1 Proof of Proposition 1.3

This section analyzes the scalar state-evolution map, establishing its concavity, monotonicity, and the existence and uniqueness of the relevant fixed point.

The map τ^2 7→F(τ^2, ατ) is concave, and strictly concave when α > 0 and X0 is not identically 0.
The map is increasing everywhere because it is strictly increasing for sufficiently large τ^2 and concave.
For α > αmin(δ), the fixed-point equation has at least one solution because the map lies above τ^2 near zero and below it for large τ^2.
Strict concavity makes the fixed-point solution unique, and the corresponding iterates converge to it.

A.2 Proof of Proposition 1.4

The section establishes regularity and limiting behavior of τ∗(α) and λ(α), using implicit-function arguments and asymptotic properties of the defining equations.

Regularity: α ↦ τ∗(α) is continuously differentiable on (0, ∞).This follows from the implicit function theorem applied to the defining mapping.
Regularity: τ∗(α) is characterized through an implicit equation whose derivative condition permits application of the implicit function theorem.The relevant derivative is strictly below one, as established using concavity and the limiting derivative behavior.
Limits: As α → ∞, τ∗(α) approaches the limit determined by σ2 + E{X0^2}/δ.The threshold event probability vanishes because τ∗(α) remains bounded.
Regularity: λ(α) is continuously differentiable because it is obtained by evaluating the continuously differentiable function g at τ∗2(α).The relation used is λ(α) = g(α, τ∗2(α)).
Limits: As α ↓ αmin(δ), λ(α) diverges to −∞ because l∗ < 0 and ατ∗(α) diverges.The sign l∗ < 0 is obtained from the characterization of αmin and a Gaussian-tail inequality.

A.3 Proof of Corollary 1.7

The proof shows that every positive λ corresponds to a unique α > αmin, ruling out two distinct parameter values producing the same λ.

Uniqueness: For any λ > 0, it suffices to prove existence and uniqueness of α > αmin satisfying λ(α) = λ.The argument proceeds by contradiction from the assumption of two such values.
Uniqueness: Applying Theorem 1.5 with ψ(x, y) = (x − y)2 shows that τ∗(α1) = τ∗(α2).The left-hand side of the resulting identity is independent of which α is chosen.
Uniqueness: Applying Theorem 1.5 with ψ(x, y) = |x| yields α1τ∗(α1) = α2τ∗(α2).The relevant expression is strictly decreasing in θ.

B Proof of Theorem 4.2

The proof of Theorem 4.2 identifies AMP-related quantities with Gaussian comparison quantities by induction over iteration indices and cases.

Inductive proof: The representation xt + A∗zt = x0 − ht+1 supplies an initial identity used in the argument.Subsequent equalities invoke the induction hypothesis to transfer identities between the compared quantities.
Inductive proof: The proof reduces the result to showing that Rt,s and ˜Rt,s are equal for all s, t ≥ 0.Equality is established by induction on max(s, t).
Inductive proof: The base case s = t = 0 is obtained using Lemma F.3(b).The resulting quantity is identified with R0,0.
Inductive proof: For t = k + 1, the proof treats s = 0 first and uses Lemma F.3(c) almost surely.The case s = k + 1 is stated to be analogous.
Inductive proof: The induction uses q0 = −x0 and Lemma F.3(b) for a pseudo-Lipschitz function.The variables X0 and ˜Zk are independent, with ˜Zk mean-zero Gaussian.
Inductive proof: The remaining cases similarly apply Lemma F.3(b)(c) almost surely, including Gaussian variables independent of X0.This completes the induction and yields the stated result.

C Proof of Lemma 4.3

The proof of Lemma 4.3 is delegated to Lemma 5.7, which is proved in the first subsection.

Proof dependency: Lemma 4.3 relies on Lemma 5.7.The dependency is stated explicitly at the start of the section.
Proof dependency: Lemma 5.7 is proved in the first subsection.The section therefore points forward to that subsection for the supporting argument.
Proof dependency: The proof strategy for Lemma 4.3 is to establish it through the separately proved Lemma 5.7.No additional intermediate argument is given in the supplied passage.

C.1 Proof of Lemma 5.7

The lemma analyzes a Gaussian recursion through correlated Gaussian variables and establishes monotone convergence to a fixed point, with the third state component vanishing exponentially fast.

Invariant region: The recursion preserves the invariant inequality y_t,3 < y_t,1 + y_t,2 from its initialization.Positive correlation of successive Gaussian variables and monotonicity of the denoiser propagate the inequality.
Fixed-point stability: The full state y_t converges to y_* by compactness, and the Jacobian at the fixed point has spectral radius below 1.The spectral-radius condition yields exponential convergence once the state approaches the fixed point.
Coordinate convergence: y_t,2 and y_t,1 converge monotonically to τ_*^2.The second coordinate evolves independently under the state-evolution map, while y_t,1 follows it with one-step delay.
Coordinate convergence: y_t,3 converges to 0 geometrically because G′(0) < 1 and G′ is decreasing.The bound y_t,3 ≤ G′(0)^t y_0,3 gives exponential decay.
Iterate convergence: The iterates’ successive differences vanish because both the threshold sequence and the covariance terms converge to their limiting values.State evolution controls the squared difference between consecutive iterates.

D Proof of Lemma 5.2

The proof controls random matrix quantities using Gaussian singular-value bounds, concentration, induction, and standard properties of random subspaces and matrices.

Eigenvalue control: The upper eigenvalue bound for R/N follows from bounded matrix entries and fixed matrix dimensions.The proof therefore focuses on establishing a positive lower bound for the minimum eigenvalue.
Inductive argument: For R = Y*Y and R = X*X, the proof proceeds by induction on the iteration index.The base case uses the Gaussian limit ⟨h_1 − x_0, h_1 − x_0⟩ → σ^2 + δ + 1 almost surely.
Inductive argument: The induction conditions use conditional Gaussian structure after exposing the previous iterates and apply concentration-of-measure arguments.The random subspace proposition is proved through an orthogonal-matrix representation, an epsilon-net, and spherical concentration.
Auxiliary results: The appendix invokes established results on Kashin subspaces, extreme singular values, and Gaussian matrix decompositions.These results provide the auxiliary probabilistic bounds used throughout the proof.

F.3 Two Lemmas from [BM11]

The cited lemmas provide the state-evolution framework for AMP, including Gaussian limit representations, deterministic limiting correlations, and identities used in the convergence proof.

State-evolution assumptions: Lemma F.3 assumes Gaussian matrices with n/N → δ and empirical convergence of x_0 and w with bounded moments.The assumptions also include a deterministic initial condition and finite limiting moment conditions.
State-evolution assumptions: State evolution defines the sequences {σ_t, τ_t} uniquely through a recursion with specified initialization.An independent Gaussian matrix copy and orthogonal bases for iterate column spaces appear in the construction.
State-evolution conclusions: For pseudo-Lipschitz and Lipschitz test functions, the relevant empirical limits exist, are bounded, and have degenerate distributions.The Gaussian comparison variables are independent of X_0 and W and have standard-normal marginals.
State-evolution conclusions: The technical identities include an almost-sure limit relating ⟨h_{r+1}, ϕ(h_{s+1}, x_0)⟩ to a covariance-weighted derivative expectation.This identity is one of the auxiliary relations used to analyze AMP iterates.
Gaussian matrix tools: Gaussian matrix projection results show that fixed-dimensional projected components vanish asymptotically.For a projection onto a d-dimensional subspace, the corresponding coefficient vector satisfies lim ∥x∥ = 0 almost surely when d is fixed.