Certifiably optimal sparse inverse covariance estimation
- PDF / 1,700,351 Bytes
- 40 Pages / 439.37 x 666.142 pts Page_size
- 97 Downloads / 185 Views
Series A
Certifiably optimal sparse inverse covariance estimation Dimitris Bertsimas1
· Jourdain Lamperski1 · Jean Pauphilet1
Received: 6 March 2016 / Accepted: 1 August 2019 © Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2019
Abstract We consider the maximum likelihood estimation of sparse inverse covariance matrices. We demonstrate that current heuristic approaches primarily encourage robustness, instead of the desired sparsity. We give a novel approach that solves the cardinality constrained likelihood problem to certifiable optimality. The approach uses techniques from mixed-integer optimization and convex optimization, and provides a high-quality solution with a guarantee on its suboptimality, even if the algorithm is terminated early. Using a variety of synthetic and real datasets, we demonstrate that our approach can solve problems where the dimension of the inverse covariance matrix is up to 1000 s. We also demonstrate that our approach produces significantly sparser solutions than Glasso and other popular learning procedures, makes less false discoveries, while still maintaining state-of-the-art accuracy. Keywords Sparse inverse covariance estimation · Semidefinite optimization · Mixed-integer optimization · Glasso · Maximum likelihood estimation Mathematics Subject Classification 90C11 · 90C22 · 62H12
1 Introduction Estimating inverse covariance (precision) matrices is a fundamental task in modern multivariate analysis. Applications include undirected Gaussian graphical models [41], high dimensional discriminant analysis [12], portfolio allocation [22,24], complex data visualization [62], amongst many others, see Fan et al. [25] for a review.
B
Dimitris Bertsimas [email protected] Jourdain Lamperski [email protected] Jean Pauphilet [email protected]
1
Massachusetts Institute of Technology, Operations Research Center, Cambridge, MA, USA
123
D. Bertsimas et al.
For example, in the context of undirected Gaussian graphical models, estimating the precision matrix corresponds to inferring the conditional independence structure on the related graphical model; zero entries in the precision matrix indicate that variables are conditionally independent. Sparsity of the true precision matrix is a prevailing assumption [10,20,40,54,67] for two reasons. 1. The covariance matrix is often estimated empirically using the maximum likelihood estimator: n 1 (i) = (x − x)(x ¯ (i) − x) ¯ T, (1) n i=1
where the number of samples n can be lower than the space dimension p. When this is the case, it is known that the empirical covariance matrix1 is singular, and thus does not accurately model the true covariance matrix. Moreover, the empirical covariance matrix can not be inverted to obtain an estimate of the precision matrix. Assuming sparsity of the true precision matrix is required for the precision matrix estimation problem to be well-defined. 2. In many applications, we use models to improve our knowledge of a given phenomenon and it is fair to admit that humans are
Data Loading...
