PaperlayerView exact revision on arXiv

Source-linked AI summary

Robust Lasso with missing and grossly corrupted observations

Nam H. Nguyen, Trac D. Tran

arXiv:1112.0391v2math.STcs.IT

TL;DR

The paper studies recovery of a sparse regression vector and a sparse corruption vector from measurements containing bounded noise and arbitrarily large sparse errors. It proposes extended Lasso, analyzes it using extended restricted eigenvalues and Gaussian-design conditions, and reports stable recovery plus exact signed-support recovery with Ω(k log p log n) observations even when corruption approaches 100%.

  • Problem

    The problem is to recover sparse β⋆ and sparse e⋆ when measurements contain bounded noise and corruptions with unknown locations and arbitrarily large magnitudes.

  • Method

    The paper proposes extended Lasso, jointly penalizing the regression and corruption vectors, and analyzes the augmented design [X, I] using extended restricted eigenvalues and Gaussian-design assumptions.

  • Results

    The method faithfully recovers both vectors, including exact signed supports from Ω(k log p log n) observations when the corruption fraction is arbitrarily close to one.

  • Takeaways & Limitations

    Extended Lasso supports parameter and variable-selection recovery under sparse gross corruption, including corruption fractions close to unity.

Abstract

from arXiv · show

This paper studies the problem of accurately recovering a sparse vector $β^{\star}$ from highly corrupted linear measurements $y = X β^{\star} + e^{\star} + w$ where $e^{\star}$ is a sparse error vector whose nonzero entries may be unbounded and $w$ is a bounded noise. We propose a so-called extended Lasso optimization which takes into consideration sparse prior information of both $β^{\star}$ and $e^{\star}$. Our first result shows that the extended Lasso can faithfully recover both the regression as well as the corruption vector. Our analysis relies on the notion of extended restricted eigenvalue for the design matrix $X$. Our second set of results applies to a general class of Gaussian design matrix $X$ with i.i.d rows $\oper N(0, Σ)$, for which we can establish a surprising result: the extended Lasso can recover exact signed supports of both $β^{\star}$ and $e^{\star}$ from only $Ω(k \log p \log n)$ observations, even when the fraction of corruption is arbitrarily close to one. Our analysis also shows that this amount of observations required to achieve exact signed support is indeed optimal.

I. INTRODUCTION

The paper addresses sparse linear regression when observations contain both bounded noise and sparse, arbitrarily large corruptions. It proposes extended Lasso to recover regression and corruption vectors, including settings where corruption affects nearly all observations.

  • Motivation: Sparse regression becomes ill-posed when p ≥ n without additional assumptions.High-dimensional inference therefore requires structural assumptions such as sparsity.
  • Problem setting: The model allows sparse errors with unknown locations and arbitrarily large magnitudes alongside conventional bounded noise.Missing observations are included as a special case of this model.
  • Proposed approach: Extended Lasso jointly exploits sparsity in β⋆ and e⋆ to recover both the regression and corruption vectors.The error penalty has its own regularization parameter controlling reconstructed-error sparsity.
  • Research questions: The paper studies parameter-error recovery and exact signed-support recovery under scalings of n, p, k, and corruption sparsity or fraction.It specifically asks whether support recovery remains possible when almost all observations are corrupted.
  • Related work: Earlier Gaussian-design results either impose stringent proportional-growth conditions or fail to allow the corruption fraction to approach one.Prior exact-recovery results based on the restricted isometry property require n ≥ C(k + s) log p but do not cover corruption fractions near unity.
  • Analysis: Extended restricted eigenvalue analysis handles the general recovery question, while Gaussian designs additionally use invertibility and mutual incoherence.The augmented matrix [X, I] couples the Gaussian design with the identity component representing corruptions.

II. MAIN RESULTS

The main-results section establishes parameter-estimation results through an extended restricted-eigenvalue condition and then develops feature-selection results for random Gaussian designs.

  • Parameter estimation: The first subsection establishes parameter estimation through a deterministic extended restricted-eigenvalue result.It also shows that random Gaussian design matrices satisfy this property with high probability.
  • Feature selection: Random Gaussian designs are analyzed separately for feature estimation and exact signed-support recovery.The supplied passage introduces this as the next subsection’s focus without giving its full theorem statement.
  • Recovery criteria: The main results distinguish parameter estimation from feature selection as separate recovery objectives.The section’s organization treats these objectives in successive subsections.

A. Parameter estimation

The paper develops parameter-estimation guarantees for extended Lasso under an extended restricted-eigenvalue condition, including Gaussian designs. The resulting bounds separate regression and corruption sparsity, while allowing corruption proportional to sample size and, without dense noise, exact recovery.

  • Extended restricted eigenvalue: The extended restricted-eigenvalue condition generalizes the standard restricted-eigenvalue assumption by incorporating both regression and corruption errors.When the corruption component is removed, the condition reduces to the usual restricted-eigenvalue condition.
  • General error bound: Theorem 1 bounds estimation error using the sparsity indices of β⋆ and e⋆, the regularization parameters, and the extended restricted-eigenvalue constant.The bound decomposes naturally into components associated with the regression vector and corruption vector.
  • Gaussian designs: For Gaussian designs, the extended restricted-eigenvalue condition holds with high probability under sample-size, covariance, and corruption-sparsity conditions.The stated result assumes n ≥ C ξ(Σ) Cmin^-1 k log p and constrains s through additional constants and logarithmic factors.
  • Regularization: The regularization parameters can be selected explicitly when the noise is Gaussian and the design columns are √n-normed.The paper relates this choice to high-probability control of the stochastic-noise terms.
  • Gaussian designs: Mutual incoherence between X and the identity matrix separates regression effects from sparse errors and yields a combined lower bound when 4κm < κr.Under this condition, the lower-bound constant becomes κr − 2κm.
  • Corruption scaling: When γ = 1/√log n, extended Lasso tolerates corruption proportional to n and recovers both vectors within bounded error.With σ = 0, the method recovers the exact solution; choosing γ = 1 is preferable when corruption is known to be O(n/log p).

B. Feature selection with random Gaussian design

The paper studies exact signed-support recovery for both regression and sparse corruption vectors under Gaussian designs. Extended Lasso achieves recovery under invertibility and mutual incoherence, while the required sample scaling grows by a log n factor near-total corruption and is shown to be optimal.

  • Feature selection requires the recovered regression and sparse error vectors to have the same signed supports as their true counterparts.
  • Invertibility and mutual incoherence of the covariance matrix support uniqueness and exact signed-support recovery for Gaussian designs.These are the same conditions used for exact signed-support recovery in standard Lasso.
  • Under the stated scaling conditions, extended Lasso has a unique solution with exact signed support and bounded element-wise estimation errors.
  • Ω(k log(p−k)) samples suffice when the corruption fraction is O(n/log n), while almost-total corruption requires an additional log n factor.The method remains robust to arbitrarily large sparse errors, but corruption robustness increases the sample requirement.
  • For i.i.d. standard Gaussian designs, exact signed-support recovery with s close to n requires n log n = Ω(k log(p−k)), and the regression ℓ∞ error increases as corruption becomes more prevalent.
  • When corruption is linearly proportional to n, exact signed-support recovery requires Ω(k log p log n) samples rather than Ω(k log p) for small estimation error.
  • The sample scaling for exact signed-support recovery is optimal: below the corresponding threshold, no extended-Lasso solution correctly identifies both signed supports with high probability.

III. ILLUSTRATIVE SIMULATIONS

Simulations test extended Lasso under Gaussian designs with varying dimensions and sparsity while half the observations are corrupted. The results support the predicted recovery threshold and its failure below that threshold.

  • The experiments vary p over {128, 256, 512} and use sublinear, linear, and fractional-power regression sparsity with s = n/2 corrupted observations.
  • Theorem 2 predicts exact signed-support recovery when n ≥ 2Ck log(p−k) log n for the half-corrupted setting.
  • Extended Lasso recovers the exact signed supports of both β⋆ and e⋆ when 50% of observations are contaminated.
  • When n log n ≤ 2k log(p−k), the success probability declines toward zero, matching the predicted failure threshold up to unknown constants.

IV. PROOF OF THEOREM 1 AND RELATED RESULTS

The proof of Theorem 1 establishes recovery guarantees through an extended restricted eigenvalue argument for Gaussian designs. Concentration bounds control the relevant error terms and yield a combined estimation bound.

  • Deterministic recovery argument: The proof analyzes the optimality error pair through an extended restricted eigenvalue lower bound.The argument decomposes the objective into terms involving the design prediction error, coefficient error, and corruption error.
  • Error control: The resulting lower bound is proportional to ∥h∥2^2 + ∥f∥2^2, where h and f are the regression and corruption estimation errors.The proof identifies h = bβ − β⋆ and f = be − e⋆ before applying the bound.
  • Conditions: The argument assumes sample size and corruption sparsity conditions involving k log p, γ, and log n.The stated Gaussian-design lemma requires a lower bound on n and an upper bound on s under covariance-related assumptions.
  • Gaussian design control: Gaussian design concentration controls blockwise interactions between coefficient and corruption errors with high probability.The proof partitions coordinates into blocks and applies Gaussian matrix concentration followed by union bounds.

V. PROOF OF THEOREM 2 - ACHIEVABILITY

The achievability proof verifies the KKT conditions for a candidate extended-Lasso solution supported on the true regression and corruption supports. Gaussian concentration bounds control subgradient terms and establish exact signed-support recovery under Theorem 2’s assumptions.

  • KKT verification: KKT optimality requires active-coordinate equalities and inactive-coordinate subgradient magnitudes below one.The proof checks these conditions separately for β and e.
  • Candidate solution: The candidate solution is constructed as (bβ, be) = (β⋆ + h, e⋆ + g), with errors restricted to the true supports.The restricted error expressions are obtained by solving the KKT conditions on the active coordinates.
  • Signed-support recovery: The active-coordinate estimation errors are bounded in ℓ∞ norm below the minimum nonzero signal magnitudes, yielding exact signed supports.The stated bounds apply separately to the regression and corruption supports.
  • Inactive coordinates: The proof bounds the inactive regression and corruption subgradients using Gaussian tails, projection properties, and matrix concentration.These bounds are combined by the triangular inequality and hold with probabilities controlled by dimensions and n − s.
  • Subgradient bounds: Under Theorem 2’s sample-size and corruption-fraction assumptions, the inactive subgradient norms are strictly less than one.The proof states this conclusion for both z(β) and z(e).

C. Establish the ℓ∞bound of bβT −β⋆

This subsection bounds the regression error on its true support in ℓ∞ norm by decomposing the relevant quantity into two terms and controlling each probabilistically.

  • Term decomposition: The regression-support bound is decomposed as T1 + T2 and analyzed term by term.The first term involves projected noise, while the second is controlled through Gaussian matrix arguments.
  • Probabilistic control: Gaussian concentration bounds the two terms and yields a high-probability bound for the regression-support error.The proof uses a lemma for Gaussian matrices and combines the resulting estimates with the triangular inequality.
  • Final bound: The proof combines the termwise estimates to obtain the stated ℓ∞ bound for bβT − β⋆.This bound is subsequently used to compare the estimation error with the smallest nonzero regression coefficient.

D. Establish the ℓ∞bound of beS −e⋆

This subsection bounds the corruption-vector error on its true support in ℓ∞ norm by controlling projected noise and design-dependent Gaussian terms.

  • Term decomposition: The corruption-support error is decomposed into terms involving projected noise and interactions with the design matrix.The proof separately bounds T1 and T2 before combining them.
  • Noise term: Gaussian tail bounds control the projected-noise contribution to the corruption-support error.The argument uses the independence and Gaussian distribution of the noise coordinates.
  • Design term: Matrix concentration controls the design-dependent contribution through bounds on Gaussian matrix norms and inverse Gram terms.The proof derives intermediate bounds involving X and its support-restricted submatrices.
  • Final bound: Combining the two contributions gives the stated high-probability ℓ∞ bound for beS − e⋆.The resulting bound is used in the achievability proof to establish signed-support recovery for the corruption vector.

VI. PROOF OF THEOREM 3 - INACHIEVABILITY

The inachievability proof uses a primal-dual witness construction to show that extended Lasso cannot recover both signed supports under the theorem’s corruption regime. The argument establishes that a dual feasibility or sign-consistency condition fails with high probability.

  • Primal-dual witness construction: The proof constructs restricted primal solutions and dual vectors, then checks dual feasibility and signed-support consistency.Failure of either the dual feasibility or sign-consistency step implies incorrect signed-support recovery.
  • Failure mechanism: When s = ηn, the relevant dual quantity exceeds unity with probability tending to one under the theorem’s assumptions.The proof analyzes separate regimes for the scaling quantity M and derives lower bounds for the dual terms.
  • Inachievability conclusion: The resulting inequalities show that the required dual conditions fail regardless of the sample size n in the specified parameter regime.The proof combines bounds on regularization parameters, Gaussian matrix terms, and projected noise.
  • Probabilistic bounds: The argument bounds the dual components using projection geometry, Gaussian concentration, and lower bounds on projected noise norms.Orthogonality of projected terms and chi-square concentration provide the needed bounds.

VII. CONCLUSION

The conclusion presents extended Lasso as a generalization of Lasso for jointly recovering sparse regression and corruption vectors under grossly corrupted observations. It reports stable estimation and exact signed-support results, while identifying broader corrupted-data models as open directions.

  • Main contribution: Extended Lasso jointly targets the regression vector and sparse error vector, including corruptions with arbitrarily large magnitudes.The method addresses observations containing both sparse and dense errors.
  • Estimation guarantee: The ℓ2 estimation error is bounded through an extended restricted eigenvalue condition on the combination matrix [X I].
  • Support recovery: Exact signed-support recovery is possible for Gaussian designs even when almost all observations are significantly corrupted.The paper establishes both lower and upper sample-size bounds for support recovery success and failure with high probability.
  • Open questions: The paper leaves robust group or multivariate Lasso, jointly corrupted observations and data matrices, and sparse additive models as open extensions.

A. Proof of Lemma 5

The proof of Lemma 5 decomposes the Gaussian design into a random Gaussian matrix and covariance factors, then uses singular-value and Haar-measure concentration to control the relevant quantities.

  • Gaussian decomposition: The design submatrix is decomposed using a Gaussian matrix with independent entries and covariance factors.This representation enables random-matrix concentration arguments.
  • Spectral control: Singular-value bounds control the spectral behavior of the Gaussian matrix when k is sufficiently smaller than n − s.
  • Haar concentration: The proof treats the target quantity as a Lipschitz function of a Haar-distributed orthogonal factor.Orthogonal invariance makes the function symmetric and allows concentration around its median.

B. Proof of Lemma 9

The proof of Lemma 9 bounds a maximum of Gaussian-derived functions by combining Lipschitz concentration with a lower bound on its expectation. Gaussian comparison and extreme-value estimates yield the required high-probability control.

  • Concentration setup: The relevant maximum is formulated as a function of a standard Gaussian matrix and shown to concentrate around its expectation.The functions involved are Lipschitz with respect to the Euclidean norm.
  • Expectation lower bound: Sudakov-Fernique comparison lower-bounds the expected maximum by the maximum of independent Gaussian variables.
  • Extreme-value estimate: The independent-Gaussian maximum contributes a logarithmic factor in n − s to the lower bound.The bound is expressed through a factor approaching (2 − δ) log(n − s).
  • Auxiliary bounds: Standard Gaussian, chi-square, and random-matrix inequalities supply the auxiliary tail and singular-value bounds used in the argument.
Loading 1112.0391v2…