## High-Dimensional Gaussian Graphical Model Selection: Walk Summability and Local Separation Criterion

** Animashree Anandkumar, Vincent Y.F. Tan, Furong Huang, Alan S. Willsky**; 13(Aug):2293−2337, 2012.

### 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=Ω(J*, where

_{min}^{-2}log p)*p*is the number of variables and

*J*is the minimum (absolute) edge potential of the graphical model. The sufficient conditions for sparsistency are based on the notion of

_{min}*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.

[abs][pdf]