Source-linked AI summary
A new approach to Cholesky-based covariance regularization in high dimensions
Adam J. Rothman, Elizaveta Levina, Ji Zhu
TL;DR
High-dimensional covariance estimation needs alternatives to poorly performing sample covariance estimators and commonly separates covariance from inverse-covariance estimation. This paper interprets the covariance Cholesky factor through regressions, producing positive definite regularized estimators and connecting them to sparsity and constrained likelihood. Banded covariance-Cholesky estimation has the same computational order as direct covariance banding, while numerical comparisons favor it in the reported simulations.
Problem
Sample covariance estimation performs poorly when variables outnumber observations, while covariance and inverse-covariance estimation are usually treated separately.
Method
The paper applies a regression interpretation of the covariance Cholesky factor to banding and penalized regularization, and analyzes its sparsity and likelihood connections.
Results
Banded covariance-Cholesky estimation is positive definite, has the same low computational cost as direct covariance banding, and provides the best operator norm performance in every reported simulation case.
Takeaways & Limitations
Covariance-Cholesky regularization provides a computationally competitive way to enforce positive definiteness in high-dimensional covariance estimation.
Takeaways & Limitations
The authors lack suitable constrained maximum likelihood algorithms for p > n, and convergence analysis is technically difficult because regression predictor errors are unobservable.
Abstract
from arXiv · showhide
In this paper we propose a new regression interpretation of the Cholesky factor of the covariance matrix, as opposed to the well known regression interpretation of the Cholesky factor of the inverse covariance, which leads to a new class of regularized covariance estimators suitable for high-dimensional problems. Regularizing the Cholesky factor of the covariance via this regression interpretation always results in a positive definite estimator. In particular, one can obtain a positive definite banded estimator of the covariance matrix at the same computational cost as the popular banded estimator proposed by Bickel and Levina (2008b), which is not guaranteed to be positive definite. We also establish theoretical connections between banding Cholesky factors of the covariance matrix and its inverse and constrained maximum likelihood estimation under the banding constraint, and compare the numerical performance of several methods in simulations and on a sonar data example.
1 Introduction
High-dimensional covariance estimation is difficult when variables outnumber observations, motivating sparse or ordered-variable methods. The paper introduces covariance-Cholesky regularization, which yields sparse positive definite estimators at low computational cost.
- Motivation: Sample covariance estimation performs poorly when there are more variables than observations.High-dimensional applications often require estimating the covariance matrix or its inverse.
- Motivation: Existing high-dimensional estimators commonly exploit sparsity in the population covariance matrix or its inverse.
- Existing approaches: Covariance estimation methods include thresholding, banding, or tapering under an ordering where distant variables are weakly correlated.
- Contribution: The paper gives the covariance Cholesky factor a regression interpretation, enabling Cholesky-based regularization with guaranteed positive definiteness.
- Contribution: Banded covariance-Cholesky estimation retains the low computational complexity of direct covariance banding while ensuring positive definiteness.
- Paper scope: The paper connects covariance and inverse-covariance Cholesky banding to sparsity and constrained maximum likelihood, and evaluates methods numerically.
2 Modified Cholesky decomposition of the covariance matrix
The covariance Cholesky factor can be constructed through sequential regressions on prior regression errors rather than prior variables. This interpretation provides a regression-based route to estimating covariance factors and recovers the sample covariance without regularization.
- Setup: The paper assumes centered iid p-variate observations with population covariance matrix Σ and sample covariance matrix ˆΣ.
- Inverse Cholesky: Inverse-covariance Cholesky estimation uses regressions of each variable on its predecessors, whose error variances form a diagonal matrix D.
- Covariance Cholesky: The covariance Cholesky factor L is obtained by inverting the inverse-covariance factorization.
- Covariance Cholesky: Each variable Xj is regressed on previous regression errors ǫj−1,...,ǫ1, giving the covariance factor a new regression interpretation.
- Estimation: In the sample algorithm, coefficients are estimated by sequential projections onto prior residuals, with p < n ensuring full-rank model matrices.
- Estimation: Unregularized least-squares regressions recover the sample covariance matrix through the estimated factors ˆL and ˆD.
3 Regularized estimation of the Cholesky factor L
Regularization sparsifies the covariance Cholesky factor through banding or penalties while preserving positive definiteness. The paper establishes distinct likelihood properties for inverse versus covariance Cholesky banding and discusses computational and high-dimensional boundaries.
- Regularized estimation: Regularizing the covariance Cholesky factor introduces sparsity while preserving positive definiteness.
- Banded estimation: Cholesky banding retains only the first k sub-diagonals, corresponding to regressions on the k previous residuals.
- Banded estimation: Banded Cholesky estimation costs O(kpn), matching the order of direct sample-covariance banding.
- Sparsity connections: A covariance matrix is k-banded if and only if its covariance Cholesky factor is k-banded, with analogous column-band equivalence for the inverse covariance.
- Constrained maximum likelihood: Inverse-Cholesky banding is the normal constrained maximum likelihood estimator under a banded inverse-covariance constraint.
- Constrained maximum likelihood: Covariance-Cholesky banding is not the constrained maximum likelihood estimator because the inverse covariance is the normal model’s canonical parameter.
- Scope and comparison: The constrained maximum likelihood algorithm is limited to p < n, while the two estimators perform similarly in practice in that regime.
4 Numerical results
Simulations compare covariance estimators across ordered-variable structures and dimensions, emphasizing operator loss, sparsity recovery, eigenvalues, eigenspaces, and positive definiteness. Cholesky banding performs strongly overall and uniquely guarantees positive definiteness among the banding approaches.
- Operator norm loss: Cholesky banding provides the best operator norm loss in every simulated case and outperforms direct sample covariance banding particularly in high dimensions.Both banding methods outperform Ledoit–Wolf and regularized regression methods.
- Operator norm loss: For p = 30, constrained banded maximum likelihood has losses 1.27(0.04) for Σ1 and 0.76(0.02) for Σ2, essentially matching Cholesky banding.The banded maximum likelihood algorithm is applicable only when p < n.
- Sparsity recovery: For sparse Σ2, Cholesky banding has a better true positive rate than sample covariance banding, while both achieve perfect true negative rates.Sample banding tends to remove more nonzero diagonals than necessary; lasso has a low true negative rate because Cholesky zeros are not preserved.
- Eigenvalues: At p = 1000, both banding methods outperform sample covariance and Ledoit–Wolf in eigenvalue estimation, especially for larger true eigenvalues.Cholesky banding has a slight edge for small eigenvalues, while the sample covariance has only 99 nonzero eigenvalues because n = 100.
- Eigenspace agreement: At p = 1000, Cholesky and ordinary banding have similar eigenspace agreement and both outperform the sample covariance and Ledoit–Wolf estimators.K(q) = q denotes perfect agreement; Ledoit–Wolf and sample covariance share eigenvectors because one is a linear combination of the other and the identity.
5 Sonar data example
The sonar analysis compares Cholesky and sample covariance banding for metal and rock spectra, examining correlation structure, eigenvalues, eigenspaces, and QDA classification. Cholesky banding shrinks nonzero correlations while preserving positive definiteness, with similar eigenvector behavior to sample banding.
- Data and setup: The dataset contains 111 metal spectra and 97 rock spectra, each with 60 frequency-band energy measurements.The spectra were measured at multiple angles, but the analysis assumes independence.
- Data and setup: Metal and rock sample correlation matrices show correlations generally decaying away from the diagonal, supporting banding.Variables were standardized first because the two types of spectra were on different scales.
- Tuning and covariance estimates: Random-splitting selection chose 31 sub-diagonals for both methods on metal, while Cholesky and sample banding chose 17 and 18 for rock, respectively.For visual comparison, both rock estimators were plotted with 17 sub-diagonals.
- Tuning and covariance estimates: Cholesky banding shrinks nonzero correlations, whereas sample banding leaves retained correlations unchanged, enabling the Cholesky estimator's positive definiteness.Figure 3 encodes correlation magnitude from white at zero to black at one.
- Spectral comparisons: The sample covariance has the most dispersed eigenvalues, Cholesky banding the least dispersed, and the estimators show no major eigenvector differences.The eigenvalue and eigenspace comparisons are shown in Figure 4.
- Classification: The estimators were also compared in QDA for discriminating rock from metal, using class-specific inverse covariance estimates.The study additionally included a diagonal covariance estimator corresponding to naive Bayes.
6 Summary and discussion
The paper introduces covariance-Cholesky regularization and connects Cholesky sparsity with covariance and inverse-covariance structure. It reports positive definite estimators with favorable numerical performance, while noting unresolved technical difficulties for convergence analysis.
- Contributions: The proposed regression interpretation makes Cholesky-based regularization applicable to the covariance matrix and yields positive definite covariance estimators.The approach extends a regression interpretation previously available for the inverse covariance.
- Contributions: Banded covariance-Cholesky estimation has the same computational cost as sample covariance banding, so positive definiteness requires no additional computational penalty.More complex lasso or nested-lasso regularization is possible at additional computational cost.
- Conclusions: The proposed estimators perform well numerically under a variety of measures and are expected to be practically useful.This conclusion is based on the reported empirical performance.
- Theoretical connections: Inverse-Cholesky banding is equivalent to constrained maximum likelihood under the banding constraint, whereas covariance-Cholesky banding is not.The two approaches were nevertheless found to perform similarly empirically.
- Limitations: Convergence analysis for covariance-Cholesky banding is technically difficult because regression predictors are unobservable and must be estimated from residuals.The paper expects an analogous convergence result but does not establish it here.
Acknowledments
The acknowledgments recognize contributions from Richard Davis and Bala Rajaratnam. The funding acknowledgments identify support for the authors from Yahoo! and the NSF.
- Acknowledgments: Richard Davis was thanked for pointing out the use of regression on residuals in time series.
- Acknowledgments: Bala Rajaratnam was thanked for discussions on sparse Cholesky factors.
- Funding: The authors report support from a Yahoo! Ph.D. Fellowship and several NSF grants.The grants supported A.J. Rothman, E. Levina, and J. Zhu.