High-dimensional Gaussian graphical model selection: walk summability and local separation criterion
High-dimensional Gaussian graphical model selection: walk summability and local separation criterion
复制标题
DOI：
10.5555/2503308.2503317
复制
发表时间：
2011-07
期刊：
影响因子：
--
通讯作者：
Anima Anandkumar;V. Tan;Furong Huang;A. Willsky
中科院分区：
文献类型：
--
作者：
Anima Anandkumar;V. Tan;Furong Huang;A. Willsky
我们考虑高维高斯图模型选择的问题。我们确定了一组存在有效估计算法的图，该算法基于经验条件协方差的阈值处理。在一组明确的条件下，当样本数量\(n = \Omega(J_{\min}^{-2}\log p)\)时（其中\(p\)是变量的数量，\(J_{\min}\)是图模型的最小（绝对）边势），我们为所提出的算法建立了结构一致性（或稀疏一致性）。稀疏一致性的充分条件基于模型的可步行求和概念以及基础图中存在稀疏局部顶点分隔器。我们还推导出了关于稀疏一致性所需样本数量的新的非渐近必要条件。
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 = Ω(Jmin-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.