Skip to main content
eScholarship
Open Access Publications from the University of California

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.
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−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.

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.

Main Content
Current View