High-Dimensional Gaussian Graphical Model Selection: Walk Summability and Local Separation Criterion
Abstract
We consider the problem of high-dimensional Gaussian graphical model selection. We identify a set of graphs for which an efficient estimation algorithm exists, and this algorithm is based on thresholding of empirical conditional covariances. Under a set of transparent conditions, we establish structural consistency (or sparsistency) for the proposed algorithm, when the number of samples n=Ω(Jmin-2 log p), where p is the number of variables and Jmin is the minimum (absolute) edge potential of the graphical model. The sufficient conditions for sparsistency are based on the notion of walk-summability of the model and the presence of sparse local vertex separators in the underlying graph. We also derive novel non-asymptotic necessary conditions on the number of samples required for sparsistency.
Cite
Text
Anandkumar et al. "High-Dimensional Gaussian Graphical Model Selection: Walk Summability and Local Separation Criterion." Journal of Machine Learning Research, 2012.Markdown
[Anandkumar et al. "High-Dimensional Gaussian Graphical Model Selection: Walk Summability and Local Separation Criterion." Journal of Machine Learning Research, 2012.](https://mlanthology.org/jmlr/2012/anandkumar2012jmlr-highdimensional/)BibTeX
@article{anandkumar2012jmlr-highdimensional,
title = {{High-Dimensional Gaussian Graphical Model Selection: Walk Summability and Local Separation Criterion}},
author = {Anandkumar, Animashree and Tan, Vincent Y.F. and Huang, Furong and Willsky, Alan S.},
journal = {Journal of Machine Learning Research},
year = {2012},
pages = {2293-2337},
volume = {13},
url = {https://mlanthology.org/jmlr/2012/anandkumar2012jmlr-highdimensional/}
}