Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published December 2011 | public
Book Section - Chapter

High-Dimensional Graphical Model Selection: Tractable Graph Families and Necessary Conditions

Abstract

We consider the problem of Ising and Gaussian graphical model selection given n i.i.d. samples from the model. We propose an efficient threshold-based algorithm for structure estimation based known as conditional mutual information test. This simple local algorithm requires only low-order statistics of the data and decides whether two nodes are neighbors in the unknown graph. Under some transparent assumptions, we establish that the proposed algorithm is structurally consistent (or sparsistent) when the number of samples scales as n= Ω(Jₘᵢₙ⁻⁴ log p), where p is the number of nodes and Jₘᵢₙ is the minimum edge potential. We also prove novel non-asymptotic necessary conditions for graphical model selection.

Additional Information

The first author is supported by the setup funds at UCI and in part by the AFOSR under Grant FA9550-10-1-0310, the second author is supported by A*STAR, Singapore and the third author is supported in part by AFOSR under Grant FA9550-08-1-1080.

Additional details

Created:
August 19, 2023
Modified:
October 24, 2023