Inverse Covariance Estimation for High-Dimensional Data in Linear Time and Space: Spectral Methods for Riccati and Sparse Models
We propose maximum likelihood estimation for learning Gaussian graphical models with a Gaussian (ℓ[2 over 2]) prior on the parameters. This is in contrast to the commonly used Laplace (ℓ[subscript 1) prior for encouraging sparseness. We show that our optimization problem leads to a Riccati matrix eq...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Uncertainty in Artificial Intelligence (AUAI)
2014
|
| Online Access: | http://hdl.handle.net/1721.1/87050 https://orcid.org/0000-0003-0238-6384 https://orcid.org/0000-0002-2199-0379 |
| _version_ | 1826199644162490368 |
|---|---|
| author | Honorio, Jean Jaakkola, Tommi S. |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Honorio, Jean Jaakkola, Tommi S. |
| author_sort | Honorio, Jean |
| collection | MIT |
| description | We propose maximum likelihood estimation for learning Gaussian graphical models with a Gaussian (ℓ[2 over 2]) prior on the parameters. This is in contrast to the commonly used Laplace (ℓ[subscript 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 algorithm that performs a singular value decomposition of the training data. Our algorithm is O(NT[superscript 2])-time and O(NT)-space for N variables and T samples. Our method is tailored to high-dimensional problems (N >> T), in which sparseness promoting methods become intractable. Furthermore, instead of obtaining a single solution for a specific regularization 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 models, such as removing unimportant variables, computing likelihoods and conditional distributions. Finally, we show promising results in several gene expressions datasets. |
| first_indexed | 2024-09-23T11:23:13Z |
| format | Article |
| id | mit-1721.1/87050 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:23:13Z |
| publishDate | 2014 |
| publisher | Association for Uncertainty in Artificial Intelligence (AUAI) |
| record_format | dspace |
| spelling | mit-1721.1/870502022-10-01T03:15:54Z Inverse Covariance Estimation for High-Dimensional Data in Linear Time and Space: Spectral Methods for Riccati and Sparse Models Honorio, Jean Jaakkola, Tommi S. Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Honorio, Jean Jaakkola, Tommi S. We propose maximum likelihood estimation for learning Gaussian graphical models with a Gaussian (ℓ[2 over 2]) prior on the parameters. This is in contrast to the commonly used Laplace (ℓ[subscript 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 algorithm that performs a singular value decomposition of the training data. Our algorithm is O(NT[superscript 2])-time and O(NT)-space for N variables and T samples. Our method is tailored to high-dimensional problems (N >> T), in which sparseness promoting methods become intractable. Furthermore, instead of obtaining a single solution for a specific regularization 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 models, such as removing unimportant variables, computing likelihoods and conditional distributions. Finally, we show promising results in several gene expressions datasets. 2014-05-19T14:14:04Z 2014-05-19T14:14:04Z 2013-07 Article http://purl.org/eprint/type/ConferencePaper http://hdl.handle.net/1721.1/87050 Honorio, Jean and Tommi Jaakkola. "Inverse Covariance Estimation for High-Dimensional Data in Linear Time and Space: Spectral Methods for Riccati and Sparse Models." Proceedings of the 2013 Conference on Uncertainty in Artifical Intelligence, July 11-15, 2013, Bellevue, Washington. https://orcid.org/0000-0003-0238-6384 https://orcid.org/0000-0002-2199-0379 en_US http://www.auai.org/uai2013/acceptedPapers.shtml Proceedings of the 2013 Conference on Uncertainty in Artifical Intelligence Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Uncertainty in Artificial Intelligence (AUAI) MIT web domain |
| spellingShingle | Honorio, Jean Jaakkola, Tommi S. Inverse Covariance Estimation for High-Dimensional Data in Linear Time and Space: Spectral Methods for Riccati and Sparse Models |
| title | Inverse Covariance Estimation for High-Dimensional Data in Linear Time and Space: Spectral Methods for Riccati and Sparse Models |
| title_full | Inverse Covariance Estimation for High-Dimensional Data in Linear Time and Space: Spectral Methods for Riccati and Sparse Models |
| title_fullStr | Inverse Covariance Estimation for High-Dimensional Data in Linear Time and Space: Spectral Methods for Riccati and Sparse Models |
| title_full_unstemmed | Inverse Covariance Estimation for High-Dimensional Data in Linear Time and Space: Spectral Methods for Riccati and Sparse Models |
| title_short | Inverse Covariance Estimation for High-Dimensional Data in Linear Time and Space: Spectral Methods for Riccati and Sparse Models |
| title_sort | inverse covariance estimation for high dimensional data in linear time and space spectral methods for riccati and sparse models |
| url | http://hdl.handle.net/1721.1/87050 https://orcid.org/0000-0003-0238-6384 https://orcid.org/0000-0002-2199-0379 |
| work_keys_str_mv | AT honoriojean inversecovarianceestimationforhighdimensionaldatainlineartimeandspacespectralmethodsforriccatiandsparsemodels AT jaakkolatommis inversecovarianceestimationforhighdimensionaldatainlineartimeandspacespectralmethodsforriccatiandsparsemodels |