PaperlayerView exact revision on arXiv

Source-linked AI summary

Sparse Matrix Inversion with Scaled Lasso

Tingni Sun, Cun-Hui Zhang

arXiv:1202.2723v2math.STstat.ML

TL;DR

The paper addresses sparse estimation of inverse covariance and correlation matrices in high dimensions, where sample covariance matrices may be singular. It uses columnwise scaled Lasso with data-determined penalties and symmetrization, proving faster spectrum-norm rates under weaker conditions than prior analyses. The theory also supplies sharper concentration at smaller penalty levels, while smaller penalties can complicate variable-selection guarantees.

  • Problem

    High-dimensional inverse covariance estimation requires sparse methods because the sample covariance matrix is singular when variables outnumber observations.

  • Method

    The method estimates each inverse-matrix column with scaled Lasso, symmetrizes the result, and selects each penalty by convex minimization without cross-validation.

  • Results

    The scaled Lasso estimator has a faster proven spectrum-norm convergence rate under weaker conditions than prior ℓ1-regularized analyses, especially when the ℓ1-to-spectrum norm ratio diverges.

  • Takeaways & Limitations

    The analysis supports smaller, data-determined penalties with simultaneous control across columnwise applications, and least-squares estimation after selection has similar performance bounds.

  • Takeaways & Limitations

    Using a smaller penalty can make variable selection inconsistent, even though estimation or prediction may still improve.

Abstract

from arXiv · show

We propose a new method of learning a sparse nonnegative-definite target matrix. Our primary example of the target matrix is the inverse of a population covariance or correlation matrix. The algorithm first estimates each column of the target matrix by the scaled Lasso and then adjusts the matrix estimator to be symmetric. The penalty level of the scaled Lasso for each column is completely determined by data via convex minimization, without using cross-validation. We prove that this scaled Lasso method guarantees the fastest proven rate of convergence in the spectrum norm under conditions of weaker form than those in the existing analyses of other $\ell_1$ regularized algorithms, and has faster guaranteed rate of convergence when the ratio of the $\ell_1$ and spectrum norms of the target inverse matrix diverges to infinity. A simulation study demonstrates the computational feasibility and superb performance of the proposed method. Our analysis also provides new performance bounds for the Lasso and scaled Lasso to guarantee higher concentration of the error at a smaller threshold level than previous analyses, and to allow the use of the union bound in column-by-column applications of the scaled Lasso without an adjustment of the penalty level. In addition, the least squares estimation after the scaled Lasso selection is considered and proven to guarantee performance bounds similar to that of the scaled Lasso.

1 Introduction

The paper proposes a column-by-column scaled Lasso estimator for sparse inverse covariance or correlation matrices, with data-determined penalties and symmetrization. It establishes spectrum-norm convergence under weaker conditions than prior ℓ1-regularized analyses and develops sharper error concentration for columnwise applications.

  • Motivation: High-dimensional inverse covariance estimation is difficult because the sample covariance is singular when the number of variables exceeds the sample size.The paper imposes sparsity on the target inverse matrix, including maximum-degree and capped-ℓ1 conditions.
  • Related methods: Existing columnwise ℓ1-regularized methods achieve d√((log p)/n) rates under bounded ℓ1 operator norms, while GLasso analyses use broader sparsity measures.The column-by-column approach reduces graphical-model estimation to p regression problems, followed by methods such as symmetrization or direct column estimation.
  • Method: The proposed method applies scaled Lasso separately to each column, then symmetrizes the estimator into a symmetric matrix.It maps a nonnegative-definite input matrix to a symmetric estimator and determines each column’s penalty by convex minimization without cross-validation.
  • Theory: Theorem 1 guarantees spectrum-norm convergence under bounded spectrum norm of Ω∗ and d^2(log p)/n → 0, with an additional bounded-diagonal condition for Θ∗.The theorem uses λ0 = A√(4(log p)/n), A > 1, and identifies spectrum norm as the ℓ2 matrix operator norm.
  • Theory: When the precision matrix’s ℓ1-to-spectrum norm ratio diverges, the proposed estimator has a faster proven convergence rate than prior analyses.The weaker spectrum-norm condition contrasts with prior bounded-ℓ1-operator-norm assumptions.
  • Error analysis: A sparse ℓ2 noise analysis permits a smaller penalty, λ0 ≈ √((2/n)log(p/k)), while still controlling all p columnwise scaled-Lasso errors simultaneously.This addresses the gap between practical penalty choices and union-bound-based theory, and yields faster rates when log(p/k) is much smaller than log p.

2 Matrix inversion via scaled Lasso

The method estimates each target-matrix column through scaled Lasso regression, converts the results into a preliminary inverse-matrix estimator, and then symmetrizes it. The scaled Lasso jointly estimates regression coefficients and noise levels with a data-determined penalty, while normalization and symmetrization address scale and structural properties.

  • Columnwise scaled Lasso: The method applies scaled Lasso column-by-column to estimate regression coefficients and noise levels for the target matrix.The columnwise regressions arise from the relationship between positive-definite matrix inversion and linear regression.
  • Matrix construction: The column estimates are translated into a preliminary matrix estimator using the coefficient–diagonal relationship for the target inverse matrix.The construction uses the relation Θ∗ = −β(diag Θ∗) to recover target-matrix columns from regression quantities.
  • Columnwise scaled Lasso: The scaled Lasso penalty level is determined from the data through convex minimization rather than cross-validation.This resolves the need to choose the penalty level and estimate each column’s noise scale separately.
  • Normalization: The scaled Lasso construction is scale-free for inverse correlation estimation, so normalized and original data yield equivalent estimators after normalization.The estimator can target either inverse covariance or inverse correlation matrices.
  • Symmetrization: The preliminary estimator is symmetrized by linear programming to produce a symmetric estimate, although positive-definiteness is not guaranteed by this step.Semidefinite programming can instead produce a nonnegative-definite estimator at higher computational cost.

3 Theoretical properties

The theoretical analysis establishes spectrum-norm error bounds for scaled-Lasso estimators of precision and inverse-correlation matrices under sparsity, invertibility, and Gaussian-data conditions. It also develops smaller-threshold concentration results that support simultaneous columnwise analysis and weakens the sparsity requirement relative to earlier bounds.

  • Sparsity conditions: The analysis uses capped ℓ1 sparsity for inverse-matrix columns, with ordinary graph degree as a special ℓ0-sparsity case.When the support set contains exactly the nonzero entries, the capped sparsity becomes one plus the column degree.
  • Invertibility conditions: The required invertibility condition is a partial invertibility condition on the population correlation matrix and is implied by a suitable lower-eigenvalue condition.This condition regularizes the design matrix in the associated linear regressions.
  • Main assumptions and bounds: Under Gaussian sample-covariance data and stated sparsity and invertibility conditions, the scaled-Lasso estimators have bounded spectrum-norm errors with large probability.The target matrices are the inverses of the population covariance and correlation matrices.
  • Sharper concentration: New Lasso and scaled-Lasso analysis permits a smaller threshold level while retaining simultaneous columnwise control through a union-bound argument.The resulting theory allows a smaller penalty level than the earlier level based on applying existing oracle inequalities across all columns.
  • Sharper concentration: The newer bound weakens the earlier ℓ0 sparsity requirement by controlling capped ℓ1 sparsity, while adding an upper sparse-eigenvalue condition.The added sparse-eigenvalue requirement is described as mild because its normalized value decreases with the sparsity index.
  • Comparison with prior bounds: The spectrum-norm condition is weaker and more natural for spectrum-norm convergence than the bounded ℓ1 operator-norm condition used in earlier methods.When the ℓ1 operator norm diverges relative to the spectrum norm, the proposed estimator has a faster proven convergence rate.

4 Linear regression revisited

This section develops sharper Lasso and scaled Lasso error bounds at smaller, fixed penalty thresholds. The results support simultaneous control across p subproblems and can yield sharper rates when the threshold reflects sparsity.

  • Sharper analytical bounds: New oracle inequalities characterize Lasso and scaled Lasso errors under fixed, smaller thresholds and permit high correlation among nuisance design vectors.The analysis uses a sparse ℓ2 measure of the noise rather than only an ℓ∞ noise bound.
  • Sharper analytical bounds: The smaller penalty level is chosen through a Gaussian tail probability k/p, with k potentially large and linked to the model complexity.The supported range includes k up to a quantity determined by the sparsity measure s∗.
  • Simultaneous applications: The new inequalities allow the union bound to control p simultaneous Lasso or scaled Lasso applications without increasing the penalty level.This directly addresses the gap between single-regression theory and column-by-column precision-matrix estimation.
  • Probabilistic guarantees: Theorem 8 supplies probability bounds of order 1−ǫ/p for each subproblem, justifying a fixed smaller threshold in precision-matrix applications.The threshold is λ∗,0 = L_n^-3/2(k/p), approximately proportional to (2/n) log(p/k).
  • Rates: For k ≍ m and log(p/k) ≍ log(p/(s∗∨1)), the resulting prediction and ℓq error bounds use log(p/(s∗∨1)) rather than log p.The corresponding orders are reported as σ²((s∗∨1)/n)² log(p/(s∗∨1)) for prediction and σ(s∗∨1)^(1/q)λ∗,0 for ℓq error.
  • Lower performance bound: A threshold that is too small can make prediction and ℓ2 estimation errors no smaller than kσ²L_n²(k/p), which becomes suboptimal when k log(p/k) greatly exceeds s∗ log(p/s∗).Thus the smaller-threshold analysis does not support arbitrarily reducing the regularization level.

5 Estimation after model selection

The paper studies least-squares estimation after scaled Lasso model selection, extending its theory to smaller threshold levels and precision-matrix estimation. Under additional conditions, the post-selection estimator achieves error bounds comparable in order to those of scaled Lasso.

  • 5 Estimation after model selection: The section extends least-squares-after-selection theory to smaller threshold levels and precision-matrix estimation.The extension builds on the use of least squares to reduce regularization bias after model selection.
  • 5 Estimation after model selection: The selected-model least-squares estimator has prediction and estimation error bounds of the same order as scaled Lasso under extra sparse-eigenvalue conditions.These conditions involve the relevant sparse eigenvalues of the design or population correlation matrix.
  • 5 Estimation after model selection: For precision-matrix estimation, the least-squares estimator is constructed column-by-column from the selected scaled-Lasso supports and then incorporated into the matrix estimator.The resulting theory requires an additional upper sparse-eigenvalue condition.
  • 5 Estimation after model selection: The precision-matrix results parallel the scaled-Lasso results, with corresponding estimators for the inverse correlation matrix and possibly different numerical constants.The paper states that the same theoretical framework applies after replacing the scaled-Lasso coefficients and scale estimates with least-squares estimates.

6 Numerical study

The numerical study compares scaled Lasso, GLasso, CLIME, and post-selection least squares across three matrix models and several dimensions. Scaled Lasso generally outperforms GLasso and often CLIME, while post-selection least squares is strongest in sparse settings but less reliable for denser models and ℓ1 error.

  • 6 Numerical study: The study compares scaled Lasso, post-selection least squares, GLasso, and CLIME across three models using spectrum, matrix ℓ1, and Frobenius losses.The experiments use training and validation samples, with 100 replications for dimensions from 30 to 1000.
  • 6 Numerical study: Model 2 is the densest model, while Model 3 has unequal diagonal values in its target matrix.For p = 1000, capped ℓ1 sparsity is 8.84, 24.63, and 8.80 for the three models, respectively.
  • 6 Numerical study: Scaled Lasso outperforms GLasso in all cases except smaller dimensions in Frobenius loss for the denser Model 2.The exception concerns p ∈ {30, 60, 90}.
  • 6 Numerical study: Scaled Lasso outperforms CLIME in most cases, with exceptions at smaller dimensions in the sparser Models 1 and 3.CLIME was not computed for p = 300 and p = 1000 because of computational costs.
  • 6 Numerical study: Post-selection least squares has the largest gains in spectrum and Frobenius losses for Models 1 and 3, but generally underperforms in matrix ℓ1 loss and Model 2.The paper characterizes this procedure as aggressive bias correction that works better when variable selection is easier.

7 Discussion

The discussion emphasizes adaptive column-specific penalty selection as an advantage of scaled Lasso, especially when precision-matrix columns differ in scale. An example shows faster convergence than fixed-penalty methods and extends the rate result to settings where the target norm is unbounded.

  • 7 Discussion: Scaled Lasso adapts the penalty level separately for each precision-matrix column, unlike methods using one fixed penalty across columns.This adaptivity is expected to help when the diagonal of the precision matrix is heterogeneous.
  • 7 Discussion: The discussion identifies a faster convergence rate for the scaled-Lasso estimator than the fixed-penalty estimator in the example.The comparison concerns the estimator in equation (54).
  • 7 Discussion: The example demonstrates that the Theorem 2 rate dλ0 can hold with unbounded ∥Θ∗∥2, where Theorem 1 does not apply.The construction uses a partition of variables and asymptotic conditions on m and p.
  • 7 Discussion: In the example, the ℓ1 and spectrum error orders of the fixed-penalty estimator exceed those of scaled Lasso by a factor involving the example’s diverging dimension parameter.The supplied passage states the factor comparison but truncates its displayed expression.

8 Proofs

The proofs establish concentration and error bounds for scaled Lasso through convexity, Gaussian concentration, sparse-noise control, and KKT-based arguments. These results support columnwise guarantees, union-bound control across the precision matrix, and subsequent theorem applications.

  • 8 Proofs: The appendix proves the main results by first establishing the linear-regression bounds used for precision-matrix estimation.The proof organization explicitly treats the results in Section 4 before those in Section 3.
  • 8 Proofs: Convexity of the joint scaled-Lasso loss and KKT conditions control the estimated noise level and regression error.The proof bounds prediction and coefficient errors by relating the scaled estimator to a Lasso estimator.
  • 8 Proofs: Gaussian concentration and Lévy concentration inequalities bound sparse noise measures at the smaller penalty level.The analysis uses Lipschitz and convexity properties of the sparse-noise function.
  • 8 Proofs: The proofs derive tail and moment bounds for the noise terms that yield the stated scaled-Lasso theorems.These bounds are then combined with sparse-eigenvalue and compatibility conditions.
  • 8 Proofs: Additional algebra verifies the theorem conditions through Gram-matrix concentration, sparse-eigenvalue control, and bounds on selected-support errors.The proof also controls false positives and projection errors in the selected model.
  • 8 Proofs: A union bound converts per-column probability guarantees into simultaneous precision-matrix guarantees.The supplied result gives probability 1 − 3ǫ for all columns after combining the individual bounds.
Loading 1202.2723v2…