From Graphical Lasso to Atomic Norms: High-Dimensional Pattern Recovery

Abstract

We study high-dimensional precision-matrix estimation with polyhedral atomic-norm penalties on the off-diagonal entries. This framework covers the graphical lasso, ${\ell }_{\infty }$-type penalties, SLOPE/OWL penalties, and penalties motivated by colored graphical models. We define the target pattern through the subdifferential face of the dual ball and derive sufficient conditions for exact pattern recovery from the sample covariance matrix. Our analysis introduces two geometric thresholds, a generalized irrepresentability condition, and extends the primal-dual witness method beyond the ${\ell }_1$ setting. For the graphical lasso, our results yield weaker covariance-deviation requirements and a less restrictive irrepresentability condition than existing theory, leading to sharper asymptotic guarantees. Numerical experiments for several graph topologies show that the resulting bounds are often close to the empirical recovery threshold.

48 pages, 2 figures