Inverse Covariance Estimation for High-Dimensional Data in Linear Time and Space: Spectral Methods for Riccati and Sparse Models

Jean Honorio, Tommi Jaakkola
Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, PMLR R11:441-450, 2013.

Abstract

We propose maximum likelihood estimation for learning Gaussian graphical models with a Gaussian (‘2 2) prior on the parameters. This is in contrast to the commonly used Laplace (‘1) prior for encouraging sparseness. We show that our optimization problem leads to a Riccati matrix equation, which has a closed form solution. We propose an efficient al- gorithm that performs a singular value de- composition of the training data. Our algo- rithm is O(NT 2)-time and O(NT)-space for N variables and T samples. Our method is tailored to high-dimensional problems (N $\gg$ T), in which sparseness promoting methods become intractable. Furthermore, instead of obtaining a single solution for a specific reg- ularization parameter, our algorithm finds the whole solution path. We show that the method has logarithmic sample complexity under the spiked covariance model. We also propose sparsification of the dense solution with provable performance guarantees. We provide techniques for using our learnt mod- els, such as removing unimportant variables, computing likelihoods and conditional distri- butions. Finally, we show promising results in several gene expressions datasets.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR11-honorio13a, title = {Inverse Covariance Estimation for High-Dimensional Data in Linear Time and Space: Spectral Methods for Riccati and Sparse Models}, author = {Honorio, Jean and Jaakkola, Tommi}, booktitle = {Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence}, pages = {441--450}, year = {2013}, editor = {Nicholson, Ann and Smyth, Padhraic}, volume = {R11}, series = {Proceedings of Machine Learning Research}, month = {12--14 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r11/main/assets/honorio13a/honorio13a.pdf}, url = {https://proceedings.mlr.press/r11/honorio13a.html}, abstract = {We propose maximum likelihood estimation for learning Gaussian graphical models with a Gaussian (‘2 2) prior on the parameters. This is in contrast to the commonly used Laplace (‘1) prior for encouraging sparseness. We show that our optimization problem leads to a Riccati matrix equation, which has a closed form solution. We propose an efficient al- gorithm that performs a singular value de- composition of the training data. Our algo- rithm is O(NT 2)-time and O(NT)-space for N variables and T samples. Our method is tailored to high-dimensional problems (N $\gg$ T), in which sparseness promoting methods become intractable. Furthermore, instead of obtaining a single solution for a specific reg- ularization parameter, our algorithm finds the whole solution path. We show that the method has logarithmic sample complexity under the spiked covariance model. We also propose sparsification of the dense solution with provable performance guarantees. We provide techniques for using our learnt mod- els, such as removing unimportant variables, computing likelihoods and conditional distri- butions. Finally, we show promising results in several gene expressions datasets.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Inverse Covariance Estimation for High-Dimensional Data in Linear Time and Space: Spectral Methods for Riccati and Sparse Models %A Jean Honorio %A Tommi Jaakkola %B Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2013 %E Ann Nicholson %E Padhraic Smyth %F pmlr-vR11-honorio13a %I PMLR %P 441--450 %U https://proceedings.mlr.press/r11/honorio13a.html %V R11 %X We propose maximum likelihood estimation for learning Gaussian graphical models with a Gaussian (‘2 2) prior on the parameters. This is in contrast to the commonly used Laplace (‘1) prior for encouraging sparseness. We show that our optimization problem leads to a Riccati matrix equation, which has a closed form solution. We propose an efficient al- gorithm that performs a singular value de- composition of the training data. Our algo- rithm is O(NT 2)-time and O(NT)-space for N variables and T samples. Our method is tailored to high-dimensional problems (N $\gg$ T), in which sparseness promoting methods become intractable. Furthermore, instead of obtaining a single solution for a specific reg- ularization parameter, our algorithm finds the whole solution path. We show that the method has logarithmic sample complexity under the spiked covariance model. We also propose sparsification of the dense solution with provable performance guarantees. We provide techniques for using our learnt mod- els, such as removing unimportant variables, computing likelihoods and conditional distri- butions. Finally, we show promising results in several gene expressions datasets. %Z Reissued by PMLR on 04 October 2026.
APA
Honorio, J. & Jaakkola, T.. (2013). Inverse Covariance Estimation for High-Dimensional Data in Linear Time and Space: Spectral Methods for Riccati and Sparse Models. Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R11:441-450 Available from https://proceedings.mlr.press/r11/honorio13a.html. Reissued by PMLR on 04 October 2026.

Related Material