High-Dimensional Gaussian Graphical Model Selection: Walk Summability and Local Separation Criterion
- Author(s): Anandkumar, Animashree;
- Tan, Vincent Y.F.;
- Huang, Furong;
- Willsky, Alan S.
- et al.
Published Web Locationhttp://jmlr.org/papers/volume13/anandkumar12a/anandkumar12a.pdf
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 = Ω(J−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.