Abstract: The penalized likelihood estimator is the state-of-the-art method for estimating a Gaussian graphical model, because it delivers a symmetric graph and is efficient to compute, owing to the graphical lasso implementation. However, the estimator requires a stringent irrepresentability condition in order to achieve con- sistent recovery of the underlying graph. Another popular method, neighborhood selection, does not offer a symmetric solution by itself, and also requires a set of irrepresentability conditions for exact recovery. In this paper, we propose a new method, called the simple graph maker, for estimating an ℓ1-penalized quadratic problem, which is easily computed by coordinate descent. Furthermore, it is shown to recover the underlying graph with overwhelming probability, without assuming additional structure conditions on the variables. The rates of convergence under various matrix norms are also established. The new method is shown to exhibit excellent performance on simulated and real data.
Key words and phrases: Coordinate descent, exact recovery, Gaussian graphical model, graphical Lasso, irrepresentable conditions, sparsity.