Symposium on Machine Learning in Speech and Language Processing (MLSLP)

Portland, Oregon, USA
September 14, 2012

Sparse Inverse Covariance Matrix Estimation Using Quadratic Approximation

Inderjit S. Dhillon, Cho-Jui Hsieh, Matyas Sustik, Pradeep Ravikumar

Uni versity of Texas at Austin, TX, USA

The L1-regularized Gaussian maximum likelihood estimator has been shown to have strong statistical guarantees in recovering a sparse inverse covariance matrix, or alternatively the underlying graph structure of a Gaussian Markov Random Field, from very limited samples. We propose a new algorithm for solving the resulting optimization problem which is a regularized log-determinant program. In contrast to other state-of-the-art methods that largely use first order gradient information, our algorithm is based on Newton's method and employs a quadratic approximation, but with some modifications that leverage the structure of the sparse Gaussian MLE problem. We present experimental results using synthetic and real application data that demonstrate the considerable improvements in performance of our method when compared to other state-of-the-art methods.


Bibliographic reference.  Dhillon, Inderjit S. / Hsieh, Cho-Jui / Sustik, Matyas / Ravikumar, Pradeep (2012): "Sparse inverse covariance matrix estimation using quadratic approximation", In MLSLP-2012 (abstract).