HIGH-DIMENSIONAL STRUCTURE ESTIMATION IN ISING MODELS: LOCAL SEPARATION CRITERION

• 成果类型: Article
• 署名作者: Anandkumar, Animashree; Tan, Vincent Y. F.; Huang, Furong; Willsky, Alan S.
• 署名单位: National University of Singapore; Agency for Science Technology & Research (A*STAR); A*STAR - Institute for Infocomm Research (I2R)
• 刊物名称: ANNALS OF STATISTICS
• ISSN/ISSBN: 0090-5364
• DOI: 10.1214/12-AOS1009
• 发表日期: 2012
• 页码: 1346-1375
• 关键词: graphs; distributions; selection; networks

摘要

We consider the problem of high-dimensional Ising (graphical) model selection. We propose a simple algorithm for structure estimation based on the thresholding of the empirical conditional variation distances. We introduce a novel criterion for tractable graph families, where this method is efficient, based on the presence of sparse local separators between node pairs in the underlying graph. For such graphs, the proposed algorithm has a sample complexity of n = Omega(J(min)(-2) log p), where p is the number of variables, and J(min) is the minimum (absolute) edge potential in the model. We also establish nonasymptotic necessary and sufficient conditions for structure estimation.