First-Order Methods for Sparse Covariance Selection

By Alexandre d'Aspremont, Onureena Banerjee, Laurent El Ghaoui. SIAM Journal on Matrix Analysis and Applications, 2006

397 citations recorded by the source corpus.

Given a sample covariance matrix, we solve a maximum likelihood problem penalized by the number of nonzero coefficients in the inverse covariance matrix. Our objective is to find a sparse representation of the sample data and to highlight conditional independence relationships between the sample variables. We first formulate a convex relaxation of this combinatorial problem, we then detail two efficient first-order algorithms with low memory requirements to solve large-scale, dense problem instances.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/3ed4b177990ff9a9614b84a9ea869a2a131d1d2f

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Vision and Pattern Recognition

In Statistics and Probability

Citations in the corpus

An optimal method for stochastic composite optimization (2011, methodology): “These rst-order methods were further studied in, for example, [1, 39, 27, 10, 40, 50, 29], and successfully used in sparse covariance selection, rank reduction in multivariate linear regression and compressed sensing etc. (see, for example, [ 11 , 25, 26, 4]).”
Sparse Multivariate Regression With Covariance Estimation (2010, background): “…1 ( B ) = j,k | b jk | , the lasso constraint (Tibshirani, 1996) on the entries of B and P The ﬁrst constraint introduces sparsity in the entries of ˆ B and the second constraint introduces zeros for all entires in some rows of ˆ B , meaning that some predictors are irrelevant for all q responses.”
Convex optimization under inexact first-order information (2009, neutral): “(see, for example, [16, 37, 38, 52, 4]).”
Estimating Sparse Precision Matrix: Optimal Rates of Convergence and Adaptive Estimation (2012, background): “See also Friedman, Hastie and Tibshirani (2008), d’Aspremont, Banerjee and El Ghaoui (2008), Rothman et al. (2008), Lam and Fan (2009), and Ravikumar et al. (2011).”
Regularized estimation of large covariance matrices (2008, neutral): “19 09 v1 [ m at h. ST ] 1 3 M ar 2 00 8 The Annals of Statistics 2008, Vol. 36, No. 1, 199–227 DOI: 10.1214/009053607000000758 c© Institute of Mathematical Statistics, 2008”
Confidence intervals for high-dimensional inverse covariance estimation (2014, methodology): “A popular estimation procedure which relies on the sparsity in Θ ∗ is the graphical Lasso [5, 4, 16].”
Generalized Thresholding of Large Covariance Matrices (2009, methodology): “Soft thresholding has been studied in the context of wavelet shrinkage by Donoho and Johnstone (1994) and Donoho et al.”
High-dimensional analysis of semidefinite relaxations for sparse principal components (2008, methodology): “Various researchers have proposed methods for extracting sparse eigenvectors, a problem often referred to as sparse principal component analysis (SPCA).”