High Dimensional Inverse Covariance Matrix Estimation via Linear Programming
Journal of Machine Learning ResearchPublished 1 March 2010
Ming Yuan
Citations350
SJR quartileQ1
SJR score2.02
SNIP3.07
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
This paper considers the problem of estimating a high dimensional inverse covariance matrix that can be well approximated by sparse matrices. Taking advantage of the connection between multivariate linear regression and entries of the inverse covariance matrix, we propose an estimating procedure that can effectively exploit such sparsity. The proposed method can be computed using linear programming and therefore has the potential to be used in very high dimensional problems. Oracle inequalities are established for the estimation error in terms of several operator norms, showing that the method is adaptive to different types of sparsity of the problem.
Keywords
MathematicsEngineering
Journal of the Royal Statistical Society Series B (Statistical Methodology)Regression Shrinkage and Selection Via the Lasso
51,790 Citations1996Robert Tibshirani
A new method for estimation in linear models called the lasso, which minimizes the residual sum of squares subject to the sum of the absolute value of the coefficients being less than a constant, is proposed.
The Annals of StatisticsLeast angle regression
9,493 Citations2004Bradley Efron, Trevor Hastie +2 more
Journal of Business and Economic StatisticsAn Introduction to Multivariate Statistical Analysis
9,232 Citations1986Robb J. Muirhead, T. W. Anderson
BiostatisticsSparse inverse covariance estimation with the graphical lasso
6,574 Citations2007Jerome H. Friedman, Trevor Hastie +1 more
Using a coordinate descent procedure for the lasso, a simple algorithm is developed that solves a 1000-node problem in at most a minute and is 30-4000 times faster than competing methods.
TechnometricsAspects of Multivariate Statistical Theory
3,357 Citations1984Leon Jay Gleser, Robb J. Muirhead
Journal of Multivariate AnalysisA well-conditioned estimator for large-dimensional covariance matrices
2,931 Citations2003Olivier Ledoit, Michael Wolf
This paper introduces an estimator that is both well-conditioned and more accurate than the sample covariance matrix asymptotically, that is distribution-free and has a simple explicit formula that is easy to compute and interpret.
The Annals of StatisticsSimultaneous analysis of Lasso and Dantzig selector
2,536 Citations2009Peter J. Bickel, Ya’acov Ritov +1 more
It is shown that, under a sparsity scenario, the Lasso estimator and the Dantzig selector exhibit similar behavior and derive, in parallel, oracle inequalities for the prediction risk in the general nonparametric regression model as well as bounds on the l p estimation loss in the linear model.
TechnometricsGraphical Models in Applied Multivariate Statistics
1,827 Citations1991Colin Goodall, Joe Whittaker
BiometrikaModel selection and estimation in the Gaussian graphical model
1,734 Citations2007Ming Yuan, Yi Lin
The implementation of the penalized likelihood methods for estimating the concentration matrix in the Gaussian graphical model is nontrivial, but it is shown that the computation can be done effectively by taking advantage of the efficient maxdet algorithm developed in convex optimization.
Journal of Machine Learning ResearchModel Selection Through Sparse Maximum Likelihood Estimation for Multivariate Gaussian or Binary Data
1,296 Citations2008Onureena Banerjee, Laurent El Ghaoui +1 more
Regularized estimation of large covariance matrices
1,234 Citations2008Peter J. Bickel, Elizaveta Levina
Covariance regularization by thresholding
1,171 Citations2007Peter J. Bickel, Elizaveta Levina
Electronic Journal of StatisticsHigh-dimensional covariance estimation by minimizing ℓ1-penalized log-determinant divergence
793 Citations2011Pradeep Ravikumar, Martin J. Wainwright +2 more
The first result establishes consistency of the estimate b � in the elementwise maximum-norm, which allows us to derive convergence rates in Frobenius and spectral norms, and shows good correspondences between the theoretical predictions and behavior in simulations.
Sparse Permutation Invariant Covariance Estimation
764 Citations2007Adam J. Rothman, Peter J. Bickel +1 more
Journal of EconometricsHigh dimensional covariance matrix estimation using a factor model
709 Citations2008Jianqing Fan, Yingying Fan +1 more
This work examines covariance matrix estimation in the asymptotic framework that the dimensionality p tends to [infinity] as the sample size n increases and identifies situations under which the factor approach increases performance substantially or marginally.
BiometrikaJoint mean-covariance models with applications to longitudinal data: unconstrained parameterisation
589 Citations1999M. Pourahmadi
Journal of the American Statistical AssociationGeneralized Thresholding of Large Covariance Matrices
512 Citations2009Adam Rothman, Elizaveta Levina +1 more
It is shown that generalized thresholding has the “sparsistency” property, meaning it estimates true zeros as zeros with probability tending to 1, and, under an additional mild condition, is sign consistent for nonzero elements.
BiometrikaCovariance matrix selection and estimation via penalised normal likelihood
424 Citations2006Jianhua Z. Huang, Naiping Liu +2 more
A nonparametric method for identifying parsimony and for producing a statistically efficient estimator of a large covariance matrix and an algorithm is developed for computing the estimator and selecting the tuning parameter.
Lecture notes in statisticsMinimax Theory of Image Reconstruction
375 Citations1993A. P. Korostelev, A. B. Tsybakov
This book is concerned with a technique for image reconstruction known as the asymptotic minimax approach, which is based on non-parametric regression and change-point analysis, and presents results under the simplest assumptions.
Operator norm consistent estimation of large-dimensional sparse covariance matrices
366 Citations2012Noureddine El Karoui
BernoulliMinimum Contrast Estimators on Sieves: Exponential Bounds and Rates of Convergence
344 Citations1998Lucien Birgé, Pascal Massart +1 more
SIAM Journal on Matrix Analysis and ApplicationsFirst-Order Methods for Sparse Covariance Selection
333 Citations2008Alexandre d’Aspremont, Onureena Banerjee +1 more
This work first formulate a convex relaxation of this combinatorial problem, then detail two efficient first-order algorithms with low memory requirements to solve large-scale, dense problem instances.
BiometrikaNonparametric estimation of large covariance matrices of longitudinal data
302 Citations2003Wei Biao Wu
BiometrikaMaximum likelihood estimation of generalised linear models for multivariate normal covariance matrix
254 Citations2000M. Pourahmadi
Neural Information Processing SystemsModel Selection in Gaussian Graphical Models: High-Dimensional Consistency of boldmathell_1-regularized MLE
113 Citations2008Garvesh Raskutti, Bin Yu +2 more
This work considers the problem of estimating the graph structure associated with a Gaussian Markov random field (GMRF) from i.i.d. samples and provides sufficient conditions on (n, p, d) for the l1-regularized MLE estimator to recover all the edges of the graph with high probability.
A Path Following Algorithm for Sparse Pseudo-Likelihood Inverse Covariance Estimation (SPLICE)
58 Citations2008Guilherme V. Rocha, Peng Zhao +1 more
This paper proposes an ‘1 penalized pseudo-likelihood estimate for the inverse covariance matrix, and names it SPLICE, which gives the best overall performance in terms of three metrics on the precision matrix and ROC curve for model selection.
arXiv (Cornell University)High-dimensional covariance estimation by minimizing $\ell_1$-penalized log-determinant divergence
47 Citations2008Pradeep Ravikumar, Martin J. Wainwright +2 more
Primal dual pursuit: a homotopy based algorithm for the Dantzig selector
38 Citations2008M. Salman Asif
The author thanks her advisor, Justin Romberg, for all the inspiration, motivation and guidance, and all her teachers here at Georgia Tech, all of whom influenced her a lot.
Journal of Computational and Graphical StatisticsEfficient Computation of ℓ<sub>1</sub>Regularized Estimates in Gaussian Graphical Models
34 Citations2008Ming Yuan
An effcient algorithm can be used to efficiently approximate the entire solution path of the ℓ1 regularized maximum likelihood estimates, which also facilitates the choice of tuning parameter.
Journal of Computational and Graphical StatisticsLarge Gaussian Covariance Matrix Estimation With Markov Structures
22 Citations2009Xinwei Deng, Ming Yuan
The proposed methods exploit sparsity in the inverse covariance matrix in a systematic fashion so that the estimate conforms with models of Markov structure and is amenable for subsequent stochastic modeling.