Estimating high dimensional faithful gaussian graphical models by low-order conditioning
Dhafer Malouche, Sylvie Sevestre-ghalila · 2008
When the number of variables p is larger than the sample size n of a dataset generated from a Gaussian Graphical Model, the maximum likelihood estimation of the precision matrix does not exist. To circumvent this difficulty, in [14], the authors assume a faithful property on the models and propose a procedure based on conditioning on only one variable. The aim of this paper is to devise a new PC-algorithm (partial correlation), uPC-algorithm, for estimating a high dimension undirected graph associated to a faithful Gaussian Graphical Model. First, we define the separability order of a graph as the maximum cardinality among all its minimal separators. We construct a sequence of graphs by increasing the number of the conditioning variables. We prove that these graphs are nested and at a limited stage, equal to the separability order, this sequence is constant and equal to the true graph. In this paper, we devise two algorithms. The first computes the separability order of a graph and the second is the uPC-algorithm. Thus we estimate the true graph from a given dataset by a step-down procedure based on a recursive estimation of the nested graphs. We show on simulated data its accuracy and consistency.