Gaussian Graphical Models and the Graphical LASSO

Intuition Beginner

Imagine a network of quantities that move together — gene activity levels, stock returns, sensor readings. If you only look at two of them at a time you will see all sorts of apparent links, because two things can wobble together just by both responding to a third. What you usually want is the direct link: do these two still move together once you account for everything else in the network? That is a much sharper and much more useful question.

A Gaussian graphical model answers exactly that question. You draw the quantities as dots and you connect two dots with an edge only when they are directly related — related even after the influence of all the other quantities is held fixed. Most pairs end up with no edge, so the picture is a sparse web that shows the genuine wiring of the system rather than a tangle of indirect echoes.

The surprising part is where this wiring lives. For data that follow a bell-shaped (normal) pattern, the right object is not the ordinary table of how each pair varies together. It is the inverse of that table. A zero in the inverse table is the precise mathematical signal that two quantities have no direct link. So the network you want is just the map of where the inverse table has zeros.

That turns network discovery into a hunt for zeros in a matrix. And hunting for zeros is exactly what the previous unit's tool, the lasso, is built for. The graphical lasso adds a budget on the total size of the entries of that inverse table, which pushes the small, unsure entries all the way to zero and leaves a clean, readable graph behind.

Visual Beginner

What you measure	What it shows	What you actually want
Ordinary covariance of two variables	they move together at all	too generous — counts indirect links
Same, but holding the rest fixed (partial)	they move together directly	the real edge
A zero in the inverse table (precision matrix)	no direct link	a missing edge in the graph
Many zeros in the inverse table	a sparse network	a clean, readable picture

The single picture to carry forward: the graph of direct links is the same thing as the pattern of nonzero entries in the inverse covariance matrix. Find the zeros and you have found the missing edges.

Worked example Beginner

Take three variables with this inverse-covariance table (the precision matrix), where the rows and columns are variables 1, 2, 3:

$$\left(\begin{array}{ccc}2& -1& 0\\ -1& 2& -1\\ 0& -1& 2\end{array}\right).$$

Read off the off-diagonal entries. The entry for the pair (1, 2) is $-1$, which is nonzero, so variables 1 and 2 have a direct link: draw an edge. The entry for (2, 3) is $-1$, nonzero, so 2 and 3 have a direct link: draw an edge. The entry for (1, 3) is $0$, so variables 1 and 3 have no direct link: no edge between them.

The resulting graph is a chain: $1-2-3$. Variable 2 sits in the middle. Variables 1 and 3 are not directly connected, even though both are connected to 2.

This matches the intuition. Variables 1 and 3 can still look correlated in the raw data, because each one talks to variable 2 and so they echo each other through the middle. But once you hold variable 2 fixed, that echo disappears and nothing direct remains. The zero in position (1, 3) records exactly this.

What this tells us: to read the network, you do not stare at the covariances; you invert to the precision matrix and look at which off-diagonal entries are zero. Here two entries survive and one is zero, giving a three-node chain with the middle node as the hub.

Check your understanding Beginner

Formal definition Intermediate+

Let $X=(X_1,\dots ,X_p{)}^{\top }\sim N(\mu ,\Sigma )$ be a $p$-dimensional Gaussian vector with positive-definite covariance $\Sigma$. The precision (or concentration) matrix is $\Theta ={\Sigma }^{-1}$. The conditional-independence graph $G=(V,E)$ has vertex set $V=\{1,\dots ,p\}$ and an edge $\{j,k\}\in E$ precisely when $X_j$ and $X_k$ are not conditionally independent given the remaining variables $X_{\setminus \{j,k\}}$. The defining structural fact of the Gaussian model, following Lauritzen ^{[Lauritzen, S. L. — Graphical Models]} Ch. 5 and Hastie, Tibshirani & Friedman ^{[Hastie, T., Tibshirani, R. & Friedman, J. — The Elements of Statistical Learning (2nd ed.)]} §17.3, is the equivalence

$${\Theta }_{jk}=0⟺X_j\perp \perp X_k\mid X_{\setminus \{j,k\}}.$$

The graph is thus read directly off the zero pattern of $\Theta$: the off-diagonal support of $\Theta$ is the edge set $E$. This is the Markov property of the Gaussian model — missing edges are exactly the pairwise conditional independences — and by the Hammersley-Clifford theorem for positive densities the pairwise, local, and global Markov properties coincide here.

The link to partial correlation makes the equivalence concrete. The partial correlation between $X_j$ and $X_k$ after linearly removing the rest is

$${\rho }_{jk\cdot \text{rest}}=-\frac{{\Theta }_{jk}}{\sqrt{{\Theta }_{jj}{\Theta }_{kk}}},$$

so ${\Theta }_{jk}=0$ is the same statement as zero partial correlation, which for jointly Gaussian variables is the same as conditional independence. A regression reading is equivalent: regressing $X_j$ on all other variables, the coefficient on $X_k$ is $-{\Theta }_{jk}/{\Theta }_{jj}$, so a coordinate is absent from the optimal predictor of $X_j$ exactly when the corresponding precision entry vanishes — the bridge to neighborhood selection.

For estimation, given $n$ i.i.d. samples with empirical covariance $S=\frac{1}{n}{\sum }_i(x_i-\bar{x})(x_i-\bar{x}{)}^{\top }$, the Gaussian log-likelihood, dropping constants and reparametrizing in $\Theta$, is

$$\ell (\Theta )=\log \det \Theta -\mathrm{tr}(S\Theta ),\Theta \succ 0,$$

which is concave on the positive-definite cone. Its unconstrained maximizer is $\hat{\Theta }=S^{-1}$, undefined when $S$ is singular ($p>n$). The graphical lasso restores well-posedness and induces sparsity by adding an ${\ell }_1$ penalty on the entries:

$$\hat{\Theta }(\lambda )=\arg \underset{\Theta \succ 0}{\max }\{\log \det \Theta -\mathrm{tr}(S\Theta )-\lambda \Vert \Theta {\Vert }_1\},\Vert \Theta {\Vert }_1=\sum _{j,k}|{\Theta }_{jk}|,$$

with $\Vert \cdot {\Vert }_1$ usually taken over the off-diagonal entries so the diagonal is unpenalized. This is the $\log \det$ analogue of the lasso of 45.06.06: the penalty drives small entries of $\Theta$ to exact zeros, and each zero is a missing edge.

Counterexamples to common slips

• Covariance zeros are not the graph. ${\Sigma }_{jk}=0$ means marginal independence of $X_j,X_k$; the graph is governed by ${\Theta }_{jk}=0$, conditional independence. A chain has zero precision entries off the chain but generally no zero covariance entries.
• The penalty acts on $\Theta$, not $\Sigma$. Sparsity is imposed on the precision matrix. The estimated covariance $\hat{W}={\hat{\Theta }}^{-1}$ is generally full even when $\hat{\Theta }$ is sparse; inverting a sparse matrix does not preserve zeros.
• Penalizing the diagonal is a modeling choice. Including the diagonal in $\Vert \Theta {\Vert }_1$ shrinks the partial variances and changes the solution; the standard graphical lasso leaves the diagonal unpenalized so only edges are selected.
• Neighborhood selection is not the exact MLE. Regressing each node on the rest by lasso (Meinshausen-Bühlmann) is a pseudo-likelihood method whose recovered supports may be asymmetric; the AND/OR symmetrization is a convention, and it need not coincide with the graphical-lasso support at finite $n$.

Key theorem with proof Intermediate+

The signature result is the equivalence that makes the whole framework work: in a Gaussian model the conditional-independence graph is the zero pattern of the precision matrix.

Theorem (precision zeros are conditional independences). Let $X\sim N(\mu ,\Sigma )$ with $\Sigma \succ 0$ and $\Theta ={\Sigma }^{-1}$. For any pair $j\ne k$,

$${\Theta }_{jk}=0⟺X_j\perp \perp X_k\mid X_{\setminus \{j,k\}}.$$

The argument follows the Schur-complement / partial-correlation route of Lauritzen ^{[Lauritzen, S. L. — Graphical Models]} Ch. 5.

Proof. Fix the pair and write $a=\{j,k\}$ and $b=\{1,\dots ,p\}\setminus a$. Partition, after the implicit permutation that puts $a$ first,

$$\Sigma =\left(\begin{array}{cc}{\Sigma }_{aa}& {\Sigma }_{ab}\\ {\Sigma }_{ba}& {\Sigma }_{bb}\end{array}\right),\Theta ={\Sigma }^{-1}=\left(\begin{array}{cc}{\Theta }_{aa}& {\Theta }_{ab}\\ {\Theta }_{ba}& {\Theta }_{bb}\end{array}\right).$$

The conditional distribution of the Gaussian sub-vector $X_a$ given $X_b=x_b$ is itself Gaussian, with conditional covariance equal to the Schur complement of ${\Sigma }_{bb}$,

$$\mathrm{Cov}(X_a\mid X_b)={\Sigma }_{aa}-{\Sigma }_{ab}{\Sigma }_{bb}^{-1}{\Sigma }_{ba}=:{\Sigma }_{a\mid b}.$$

The block-inverse (Schur-complement) identity for the leading block of an inverse states ${\Theta }_{aa}=({\Sigma }_{aa}-{\Sigma }_{ab}{\Sigma }_{bb}^{-1}{\Sigma }_{ba}{)}^{-1}={\Sigma }_{a\mid b}^{-1}$. Therefore the $2\times 2$ conditional precision of the pair $(X_j,X_k)$ given the rest is exactly ${\Theta }_{aa}$.

Now $X_j$ and $X_k$ are conditionally independent given $X_b$ iff their conditional covariance ${\Sigma }_{a\mid b}$ is diagonal (uncorrelated jointly-Gaussian coordinates are independent). A $2\times 2$ positive-definite matrix is diagonal iff its inverse is diagonal, and the inverse of ${\Sigma }_{a\mid b}$ is ${\Theta }_{aa}$. The off-diagonal entry of the $2\times 2$ block ${\Theta }_{aa}$ is precisely ${\Theta }_{jk}$. Hence ${\Sigma }_{a\mid b}$ is diagonal iff ${\Theta }_{jk}=0$, giving

$$X_j\perp \perp X_k\mid X_b⟺{\Theta }_{jk}=0.$$

The partial-correlation form follows by normalizing the conditional precision: ${\rho }_{jk\cdot \text{rest}}=-{\Theta }_{jk}/\sqrt{{\Theta }_{jj}{\Theta }_{kk}}$, whose vanishing is the same condition. $\square$

Bridge. The proof's engine is the Schur complement: conditioning a Gaussian on the remaining variables inverts to the leading block of the precision matrix, so the local question of a single conditional independence is read off a global matrix inverse. This builds toward the estimation theory, where the same identity reappears as the block structure of the graphical-lasso updates — leaving out one variable and conditioning on the rest is a Schur complement, and that is exactly the step that turns each outer iteration into a lasso regression. It appears again in the Master-tier sparsistency analysis, where the Hessian of $\log \det$ is the Kronecker product $\Sigma \otimes \Sigma$ and the incoherence condition controlling support recovery is its restriction. The foundational reason the framework is tractable is that this is exactly the regression reading of the precision matrix: the coefficients of $X_j$ on the rest are $-{\Theta }_{j\cdot }/{\Theta }_{jj}$, so a zero precision entry is a dropped predictor, which is what the lasso of 45.06.06 selects. The result generalises the elementary fact that for two jointly Gaussian variables zero correlation is independence, lifting "marginal" to "conditional" by replacing $\Sigma$ with $\Theta$; the central insight is that conditional independence in the Gaussian world is a linear-algebraic zero pattern, not a probabilistic limit. Putting these together, edge selection becomes sparse precision-matrix estimation, and the next sections make that estimation high-dimensional.

Exercises Intermediate+

Lean formalization Intermediate+

Mathlib does not yet host Gaussian graphical models or the graphical lasso, so no module is wired in (lean_status: none). The intended statements of the precision-zero/conditional-independence equivalence and the concavity of the penalized log-likelihood, once a multivariate-Gaussian-conditional-distribution API exists, would read roughly as follows.

-- Intended shape; not part of the current Babel Bible Lean build.
-- Requires: a multivariate Gaussian with conditional-distribution API,
-- a conditional-independence predicate, and a matrix-ℓ₁ subdifferential.
variable {p : ℕ} (Σ : Matrix (Fin p) (Fin p) ℝ) (hΣ : Σ.PosDef)

noncomputable def precision : Matrix (Fin p) (Fin p) ℝ := Σ⁻¹

-- Precision zeros ⟺ conditional independence given the rest.
theorem precision_zero_iff_condIndep (j k : Fin p) (hjk : j ≠ k) :
    (precision Σ) j k = 0 ↔
      CondIndep (gaussian Σ) j k {i | i ≠ j ∧ i ≠ k} := by
  sorry

-- Concavity of the Gaussian log-likelihood on the PD cone.
theorem logdet_likelihood_concaveOn (S : Matrix (Fin p) (Fin p) ℝ) :
    ConcaveOn ℝ {Θ : Matrix (Fin p) (Fin p) ℝ | Θ.PosDef}
      (fun Θ => Real.log Θ.det - (S * Θ).trace) := by
  sorry

-- Graphical-lasso stationarity: Θ⁻¹ - S - λ Γ = 0 with Γ ∈ ∂‖Θ‖₁.
theorem glasso_kkt (S : Matrix (Fin p) (Fin p) ℝ) (lam : ℝ) (hlam : 0 < lam)
    (Θhat : Matrix (Fin p) (Fin p) ℝ) (hpd : Θhat.PosDef) :
    IsMaxOn (fun Θ => Real.log Θ.det - (S * Θ).trace - lam * matrixL1 Θ)
        {Θ | Θ.PosDef} Θhat ↔
      ∃ Γ, Γ ∈ subgradientL1 Θhat ∧ Θhat⁻¹ - S - lam • Γ = 0 := by
  sorry

the Mathlib gap analysis records what is missing: the Gaussian conditional-distribution and conditional-independence layer, the partial-correlation identity, the concavity of $\log \det \Theta -\mathrm{tr}(S\Theta )$ on the positive-definite cone with its Kronecker-product Hessian, the matrix-${\ell }_1$ subdifferential, the existence/uniqueness of the graphical-lasso maximizer, the block-coordinate-descent reduction to a lasso regression, and the model-selection consistency under the $\Sigma \otimes \Sigma$ incoherence condition.

Advanced results Master

The graphical-lasso problem is not merely concave but strictly concave on the positive-definite cone whenever the diagonal is penalized or $\lambda >0$ confines the iterates to a compact PD sublevel set, so its maximizer is unique. Strict concavity of $\log \det$ supplies the curvature: the Hessian of $\Theta \mapsto \log \det \Theta$ is the negative-definite operator $H[\Delta ]=-{\Theta }^{-1}\Delta {\Theta }^{-1}$, equivalently $-{\Theta }^{-1}\otimes {\Theta }^{-1}$ in vectorized form, and $\mathrm{tr}(S\Theta )$ is linear while $\lambda \Vert \Theta {\Vert }_1$ is convex; the objective is concave with a unique argmax. The ${\ell }_1$ term forces the sublevel sets to be bounded, so a maximizer exists even when $S$ is singular — the high-dimensional well-posedness that the unpenalized MLE $S^{-1}$ lacks. This is the $\log \det$ counterpart of how the ${\ell }_1$ penalty in 45.06.06 restored uniqueness and existence to least squares in the $p>n$ regime.

The block-coordinate-descent solver of Friedman, Hastie & Tibshirani ^{[Friedman, J., Hastie, T. & Tibshirani, R. — Sparse Inverse Covariance Estimation with the Graphical Lasso]} operates on the working covariance $W={\Theta }^{-1}$ rather than on $\Theta$ directly. Cycling through variables, each outer step fixes all but one row/column, and the stationarity condition restricted to that block is the KKT system of a single lasso regression ${\min }_{\beta }\frac{1}{2}{\beta }^{\top }{W}_{11}\beta -{\beta }^{\top }{s}_{12}+\lambda \Vert \beta {\Vert }_1$ with Gram matrix the leading block $W_{11}$; this is solved by coordinate descent 44.06.07, after which $w_{12}$ is updated to $W_{11}\hat{\beta }$. The outer cycle is itself block coordinate ascent on the dual, and because the objective is strictly concave with a unique optimum the sweeps converge to the global maximizer. The Schur-complement structure of the Key theorem is the reason the per-block update is a regression: leaving out one variable and conditioning is a Schur complement, and the regression coefficients of one node on the rest are the off-diagonal precision entries up to scale.

The exact maximum-likelihood and the neighborhood-selection estimator of Meinshausen & Bühlmann ^{[Friedman, J., Hastie, T. & Tibshirani, R. — Sparse Inverse Covariance Estimation with the Graphical Lasso]} are two routes to the same graph. Neighborhood selection regresses each $X_j$ on $X_{\setminus j}$ by lasso and declares edges from the recovered supports, symmetrized by an AND or OR rule. This is a pseudo-likelihood approximation: it replaces the joint Gaussian likelihood by the product of $p$ conditional regressions, each of which is exactly the conditional-mean reading of the precision matrix established above. Its high-dimensional consistency holds under a neighborhood-stability condition — an irrepresentable condition imposed nodewise, descending directly from the support-recovery theory of 45.06.06 — together with a $\beta$-min lower bound on the nonzero partial correlations and the sample-size scaling $n\gtrsim d^2\log p$, where $d$ is the maximum node degree.

Model-selection consistency (sparsistency) of the graphical lasso itself was established by Ravikumar, Wainwright, Raskutti & Yu (2011) under an incoherence condition on the Hessian of the log-determinant at the truth. With ${\Gamma }^{\ast }={\Sigma }^{\ast }\otimes {\Sigma }^{\ast }$ the Hessian, $S^{\ast }$ the true edge set (with diagonal), and the irrepresentable-type bound $\Vert {\Gamma }_{(S^{\ast }{)}^c{S}^{\ast }}^{\ast }({\Gamma }_{S^{\ast }{S}^{\ast }}^{\ast }{)}^{-1}{\Vert }_{\infty }\le 1-\alpha$ for some $\alpha \in (0,1]$, choosing $\lambda \asymp \sqrt{\log p/n}$ yields, with high probability, that $\hat{\Theta }$ has the correct signed support and $\Vert \hat{\Theta }-{\Theta }^{\ast }{\Vert }_{\infty }\lesssim \sqrt{\log p/n}$, provided $n\gtrsim d^2\log p$. The structure mirrors the lasso primal-dual witness of 45.06.06 exactly: the incoherence condition is the precision-matrix analogue of the mutual-incoherence / irrepresentable condition there, the Hessian ${\Sigma }^{\ast }\otimes {\Sigma }^{\ast }$ playing the role the Gram matrix $X^{\top }X$ played for the lasso. As with the lasso, prediction-type bounds (in Frobenius or operator norm) hold under weaker conditions than exact edge recovery, which needs the incoherence assumption.

Synthesis. The foundational reason this entire theory coheres is the Schur-complement identity, which turns the probabilistic notion of conditional independence into the algebraic zero pattern of the precision matrix $\Theta ={\Sigma }^{-1}$, and the same identity then turns estimation of that zero pattern into a sequence of lasso regressions. This is exactly the $\log \det$ lift of the lasso of 45.06.06: where the lasso penalizes a coefficient vector to select predictors, the graphical lasso penalizes a matrix to select edges, and both are governed by the identical subgradient stationarity $0\in \nabla (\text{smooth})-\lambda \partial \Vert \cdot {\Vert }_1$ whose inactive clause $|\cdot |\le \lambda$ produces exact zeros. The block-coordinate-descent solver generalises plain coordinate descent 44.06.07 to a matrix optimization in which each inner solve is itself a lasso, and the central insight is that conditioning on the rest of the variables — a Schur complement — is a regression, so the precision matrix is nothing but the assembled coefficients of every nodewise regression. Putting these together, the high-dimensional theory transfers wholesale: the compatibility/restricted-eigenvalue machinery of the lasso becomes the incoherence condition on ${\Sigma }^{\ast }\otimes {\Sigma }^{\ast }$, the noise event $\lambda \ge 2{\lambda }_0$ becomes the concentration of $S$ around ${\Sigma }^{\ast }$, and the primal-dual witness for sign consistency is dual to the neighborhood-stability condition for nodewise recovery — sparsistency in both settings is the strict feasibility of the dual certificate off the true support. The graph is dual to the matrix: edges are the support of $\Theta$, and estimating one is estimating the other.

Full proof set Master

The precision-zero/conditional-independence equivalence, the partial-correlation identity, the concavity and unconstrained maximizer of the log-likelihood, the graphical-lasso KKT condition, and the block-coordinate-descent reduction are proved in full in the Formal definition, Key theorem, and Exercises sections. The remaining Master claims are recorded here.

Proposition 1 (existence and uniqueness of the graphical-lasso estimate). For $S⪰0$ and $\lambda >0$ with the diagonal penalized (or with $S$ having strictly positive diagonal), the problem ${\max }_{\Theta \succ 0}\log \det \Theta -\mathrm{tr}(S\Theta )-\lambda \Vert \Theta {\Vert }_1$ has a unique maximizer.

Proof. The objective $f(\Theta )=\log \det \Theta -\mathrm{tr}(S\Theta )-\lambda \Vert \Theta {\Vert }_1$ is the sum of the strictly concave $\log \det$ (Hessian $-{\Theta }^{-1}\otimes {\Theta }^{-1}\prec 0$), the linear $-\mathrm{tr}(S\Theta )$, and the concave $-\lambda \Vert \Theta {\Vert }_1$, hence strictly concave on the convex set $\{\Theta \succ 0\}$. For existence, note $-\mathrm{tr}(S\Theta )-\lambda \Vert \Theta {\Vert }_1\le -\lambda \Vert \Theta {\Vert }_1$ drives $f\to -\infty$ as $\Vert \Theta \Vert \to \infty$, while $\log \det \Theta \to -\infty$ as any eigenvalue of $\Theta$ approaches $0$ (the boundary of the PD cone). So $f$ attains its supremum on a compact subset of the open cone, and strict concavity makes the maximizer unique. $\square$

Proposition 2 (the working-covariance fixed point). At the optimum, the working covariance $W={\hat{\Theta }}^{-1}$ satisfies $W_{jj}=S_{jj}+\lambda$ (diagonal penalized) or $W_{jj}=S_{jj}$ (diagonal unpenalized) and $|W_{jk}-S_{jk}|\le \lambda$ for all $j\ne k$, with equality $W_{jk}-S_{jk}=\lambda \mathrm{sign}({\hat{\Theta }}_{jk})$ on the edge support.

Proof. The stationarity condition from Exercise 5 is ${\hat{\Theta }}^{-1}-S-\lambda \Gamma =0$ with $\Gamma \in \partial \Vert \hat{\Theta }{\Vert }_1$. Writing $W={\hat{\Theta }}^{-1}$ entrywise: on the diagonal, if penalized, ${\Gamma }_{jj}=\mathrm{sign}({\hat{\Theta }}_{jj})=+1$ (positive-definiteness forces ${\hat{\Theta }}_{jj}>0$), giving $W_{jj}=S_{jj}+\lambda$; if unpenalized, ${\Gamma }_{jj}=0$ and $W_{jj}=S_{jj}$. Off the diagonal, where ${\hat{\Theta }}_{jk}\ne 0$, ${\Gamma }_{jk}=\mathrm{sign}({\hat{\Theta }}_{jk})$ gives $W_{jk}-S_{jk}=\lambda \mathrm{sign}({\hat{\Theta }}_{jk})$; where ${\hat{\Theta }}_{jk}=0$, ${\Gamma }_{jk}\in [-1,1]$ gives $|W_{jk}-S_{jk}|\le \lambda$. $\square$

Proposition 3 (neighborhood regression coefficients are precision entries). Let $X\sim N(0,\Sigma )$, $\Theta ={\Sigma }^{-1}$. The least-squares regression of $X_j$ on $X_{\setminus j}$ has coefficient vector with $k$-th entry $-{\Theta }_{jk}/{\Theta }_{jj}$, and the residual variance is $1/{\Theta }_{jj}$.

Proof. For a jointly Gaussian vector, $\mathbb{E}[X_j\mid X_{\setminus j}]={\Sigma }_{j,\setminus j}{\Sigma }_{\setminus j,\setminus j}^{-1}{X}_{\setminus j}$, a linear function whose coefficients are the population regression coefficients. By the block-inverse identity applied to the $1\times 1$ leading block $\{j\}$, the precision row satisfies ${\Theta }_{jj}=({\Sigma }_{jj}-{\Sigma }_{j,\setminus j}{\Sigma }_{\setminus j,\setminus j}^{-1}{\Sigma }_{\setminus j,j}{)}^{-1}$, which is the reciprocal of the conditional (residual) variance $\mathrm{Var}(X_j\mid X_{\setminus j})$, so that residual variance is $1/{\Theta }_{jj}$. The off-diagonal block-inverse relation gives ${\Theta }_{j,\setminus j}=-{\Theta }_{jj}{\Sigma }_{j,\setminus j}{\Sigma }_{\setminus j,\setminus j}^{-1}$, hence the regression coefficient vector ${\Sigma }_{j,\setminus j}{\Sigma }_{\setminus j,\setminus j}^{-1}=-{\Theta }_{j,\setminus j}/{\Theta }_{jj}$, whose $k$-th entry is $-{\Theta }_{jk}/{\Theta }_{jj}$. A zero coefficient is therefore a zero precision entry, which is the neighborhood-selection criterion. $\square$

Proposition 4 (sparsistency, stated). Let the rows of the data be i.i.d. $N(0,{\Sigma }^{\ast })$ with ${\Theta }^{\ast }=({\Sigma }^{\ast }{)}^{-1}$, edge set $S^{\ast }$, maximum degree $d$, and Hessian ${\Gamma }^{\ast }={\Sigma }^{\ast }\otimes {\Sigma }^{\ast }$. Assume the incoherence condition \lVert\Gamma^\ast_{(S^\ast)^c S^\ast}(\Gamma^\ast_{S^\astS^\ast})^{-1}\rVert_\infty\le 1-\alpha for some $\alpha \in (0,1]$, bounded \lVert(\Gamma^\ast_{S^\astS^\ast})^{-1}\rVert_\infty and $\Vert {\Sigma }^{\ast }{\Vert }_{\infty }$, and a $\beta$-min bound ${\min }_{(j,k)\in S^{\ast }}|{\Theta }_{jk}^{\ast }|>c\sqrt{\log p/n}$. Then for $\lambda \asymp \sqrt{\log p/n}$ and $n\gtrsim d^2\log p$, with probability tending to one the graphical-lasso estimate $\hat{\Theta }$ has $\mathrm{sign}(\hat{\Theta })=\mathrm{sign}({\Theta }^{\ast })$ and $\Vert \hat{\Theta }-{\Theta }^{\ast }{\Vert }_{\infty }\lesssim \sqrt{\log p/n}$.

Proof (reference). This is Theorem 1 of Ravikumar, Wainwright, Raskutti & Yu (2011), proved by a primal-dual witness construction for the $\log \det$ program directly paralleling the lasso witness of 45.06.06: one solves the program restricted to $S^{\ast }$, sets the off-support entries to zero, and shows that the dual variable $\Gamma$ constructed from the stationarity condition is strictly feasible ($\Vert {\Gamma }_{(S^{\ast }{)}^c}{\Vert }_{\infty }<1$) on the high-probability event that the empirical Hessian and the gradient $S-{\Sigma }^{\ast }$ concentrate, the latter via a sub-exponential maximal inequality over the $p^2$ entries. The incoherence condition is exactly what certifies the strict dual feasibility. Stated without re-derivation here; the witness mechanics are the matrix lift of the proof in 45.06.06. $\square$

Connections Master

• The lasso 45.06.06 is the direct parent: each block-coordinate update of the graphical lasso is literally a lasso regression with Gram matrix $W_{11}$, and the whole sparsistency theory (incoherence condition, primal-dual witness, $\sqrt{\log p/n}$ rate) is the matrix lift of the lasso's support-recovery theory. Neighborhood selection runs one lasso per node.

• Linear model theory 45.06.01 supplies the regression reading that makes the precision matrix interpretable: the population regression of $X_j$ on the rest is the conditional mean of a Gaussian, and its coefficients are $-{\Theta }_{jk}/{\Theta }_{jj}$ — the BLUE/projection geometry of that unit specialized to the Gaussian conditional distribution, which is what neighborhood selection estimates node by node.

• Coordinate descent 44.06.07 is the inner engine: each block update of the working covariance reduces to a lasso whose solution is computed by exactly the coordinate-descent sweep developed there, and the outer cycle over columns is block coordinate ascent whose convergence rests on the strict concavity established here.

• The multivariate normal and its covariance algebra 26.03.01 provide the conditional-distribution machinery — the Schur-complement form of $\mathrm{Cov}(X_a\mid X_b)$ and the transformation rule for Gaussian sub-vectors — that the Key theorem turns into the precision-zero/conditional-independence equivalence.

Historical & philosophical context Master

Covariance selection — fitting a Gaussian model by setting selected entries of the inverse covariance to zero — was introduced by A. P. Dempster in 1972 ^{[Dempster 1972]}, who recognized that the natural parameters of the Gaussian family are the precision-matrix entries and that zeros among them encode conditional independences, giving a parsimonious model class. The graph-theoretic formalization of conditional independence through Markov properties on undirected graphs, and the equivalence of the pairwise, local, and global properties for positive densities via the Hammersley-Clifford theorem, was systematized in S. L. Lauritzen's Graphical Models ^{[Lauritzen 1996]}, the standard reference for the structure underlying this unit.

The high-dimensional turn came in the 2000s. N. Meinshausen and P. Bühlmann ^{[Meinshausen 2006]} showed in 2006 that running a lasso regression of each variable on the rest consistently recovers the neighborhood structure when $p$ grows with $n$, under a neighborhood-stability condition descended from the irrepresentable condition for the lasso. J. Friedman, T. Hastie, and R. Tibshirani ^{[Friedman, J., Hastie, T. & Tibshirani, R. — Sparse Inverse Covariance Estimation with the Graphical Lasso]} gave the graphical-lasso algorithm in 2008, solving the exact ${\ell }_1$-penalized Gaussian likelihood by block coordinate descent and making sparse precision estimation routine. P. Ravikumar, M. Wainwright, G. Raskutti, and B. Yu established its model-selection consistency in 2011 under an incoherence condition on the Hessian ${\Sigma }^{\ast }\otimes {\Sigma }^{\ast }$, completing the parallel with lasso sparsistency.

Bibliography Master

@book{hastie2009elements,
  author    = {Hastie, Trevor and Tibshirani, Robert and Friedman, Jerome},
  title     = {The Elements of Statistical Learning: Data Mining, Inference, and Prediction},
  edition   = {2},
  publisher = {Springer},
  year      = {2009},
  note      = {Chapter 17, undirected graphical models}
}

@book{lauritzen1996graphical,
  author    = {Lauritzen, Steffen L.},
  title     = {Graphical Models},
  series    = {Oxford Statistical Science Series},
  publisher = {Oxford University Press},
  year      = {1996}
}

@article{dempster1972covariance,
  author  = {Dempster, A. P.},
  title   = {Covariance Selection},
  journal = {Biometrics},
  volume  = {28},
  number  = {1},
  pages   = {157--175},
  year    = {1972}
}

@article{meinshausen2006high,
  author  = {Meinshausen, Nicolai and B\"uhlmann, Peter},
  title   = {High-dimensional graphs and variable selection with the Lasso},
  journal = {The Annals of Statistics},
  volume  = {34},
  number  = {3},
  pages   = {1436--1462},
  year    = {2006}
}

@article{friedman2008sparse,
  author  = {Friedman, Jerome and Hastie, Trevor and Tibshirani, Robert},
  title   = {Sparse inverse covariance estimation with the graphical lasso},
  journal = {Biostatistics},
  volume  = {9},
  number  = {3},
  pages   = {432--441},
  year    = {2008}
}

@article{ravikumar2011high,
  author  = {Ravikumar, Pradeep and Wainwright, Martin J. and Raskutti, Garvesh and Yu, Bin},
  title   = {High-dimensional covariance estimation by minimizing $\ell_1$-penalized log-determinant divergence},
  journal = {Electronic Journal of Statistics},
  volume  = {5},
  pages   = {935--980},
  year    = {2011}
}