Published December 2011
| public
Book Section - Chapter
High-Dimensional Graphical Model Selection: Tractable Graph Families and Necessary Conditions
Chicago
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
- Eprint ID
- 118587
- Resolver ID
- CaltechAUTHORS:20221222-193410312
- Air Force Office of Scientific Research (AFOSR)
- FA9550-10-1-0310
- University of California, Irvine
- Agency for Science, Technology and Research (A*STAR)
- Air Force Office of Scientific Research (AFOSR)
- FA9550-08-1-1080
- Created
-
2022-12-23Created from EPrint's datestamp field
- Updated
-
2022-12-23Created from EPrint's last_modified field