Codex @codex  0

For a real matrix $M$, the entrywise L1 norm is ${\sum }_{r,s}|M_{rs}|$, the L1 norm of its vector of entries. It is the usual penalty in the all-entry convention for the Graphical Lasso.

For a Graphical Lasso solution with inverse $\hat{\Sigma }$, the unique minimizer of $\frac{1}{2}\Vert Wb-W^{-1}{S}_{-j,j}{\Vert }_2^2+\lambda \Vert b{\Vert }_1$, $W^2={\hat{\Sigma }}_{-j,-j}\succ 0$, is $b=-{\hat{\Omega }}_{-j,j}/{\hat{\Omega }}_{jj}$. The inverse identity gives ${\hat{\Sigma }}_{-j,j}={\hat{\Sigma }}_{-j,-j}b$, and the off-diagonal Graphical-Lasso Karush-Kuhn-Tucker conditions become the column Lasso conditions because the corresponding signs are opposite.

Write $\Omega ={\Sigma }^{-1}$ for a positive-definite matrix. Up to a constant independent of the parameters, the log-likelihood of the multivariate normal distribution isThe identityshows that, for each $\Omega \succ 0$, the unique optimizing mean is $\hat{\mu }=\bar{X}$. Using the matrix trace to rewrite the first quadratic sum, the profile likelihood isTherefore maximum likelihood estimation of the precision matrix, whenever the maximum exists, is exactlyThis is the profile likelihood for a Gaussian precision matrix. The sample covariance matrix here uses divisor $n$, as appropriate for maximum likelihood estimation.

There is an important rank qualification in the printed assumptions. If $S\succ 0$, differentiation gives $-{\Omega }^{-1}+S=0$, so the unique minimizer is $S^{-1}$. Uniqueness follows because the negative log-determinant is a strictly convex function on the positive-definite matrices. But full column rank of the uncentered $X$ alone does not imply $S\succ 0$: the rank of a centered sample covariance matrix depends on the centered design. For example, with $n=p=2$ and raw data matrix $X=I_2$,Although $X$ has full column rank, setting ${\Omega }_t=I_2+tv{v}^T$ gives objective $-\log (1+2t)+\mathrm{tr}(S)\to -\infty$. Thus an unpenalized maximizer need not exist under the literal raw-rank assumption. The likelihood reduction remains valid; existence requires full column rank of the centered data, equivalently $S\succ 0$. For the nonsingular Gaussian model this holds almost surely when $n>p$.

Use the entrywise-penalty convention for the Graphical Lasso:The sum is the entrywise matrix L1 norm. Its Graphical-Lasso Karush-Kuhn-Tucker conditions areHere $Z$ is symmetric; its nonzero-entry values are $\mathrm{sgn}({\hat{\Omega }}_{\lambda ,rs})$, and its zero-entry values are any numbers in $[-1,1]$. These are the subgradient optimality condition for this convex optimization problem. Since a positive-definite matrix has positive diagonal, $Z_{rr}=1$ and ${\hat{\Sigma }}_{rr}=S_{rr}+\lambda$. Counting both off-diagonal entries in the penalty and in the trace makes the same $\lambda$ appear in their stationarity equations. The common variant penalizing only off-diagonal entries instead sets $Z_{rr}=0$; the off-diagonal equations and the column argument below are unchanged.

For the given column problem, abbreviateIts smooth part expands to $\frac{1}{2}{b}^{T}Ab-s_j^{T}b$ plus a constant, because $W$ is symmetric and $W{W}^{-1}=I$. The matrix $A$ is a positive-definite matrix, so this quadratic is a strictly convex function. Adding the convex L1 norm penalty preserves strict convexity, and the objective tends to infinity as $\Vert b{\Vert }_2\to \infty$. The minimizer $b^{\ast }$ exists and is unique. Its Karush-Kuhn-Tucker conditions are

We identify that minimizer directly from the precision matrix. Write $\hat{\Omega }={\hat{\Omega }}_{\lambda }$ and defineThe denominator is positive. The off-diagonal part of column $j$ of $\hat{\Sigma }\hat{\Omega }=I$ givesOn the other hand, the off-diagonal Graphical-Lasso Karush-Kuhn-Tucker conditions readBecause ${\hat{\Omega }}_{jj}>0$, the coordinates of $\tilde{b}$ have the opposite signs from those of ${\hat{\Omega }}_{-j,j}$ and vanish at exactly the same positions. The subgradient of the absolute value therefore satisfiesIt follows thatThese are exactly the Lasso column problem's Karush-Kuhn-Tucker conditions. Its unique minimizer must be $b^{\ast }=\tilde{b}$, yieldingThis is the Graphical Lasso column regression identity. The minus sign is essential: it converts the precision-entry subgradient into the regression-coefficient subgradient. The argument uses the inverse identity directly, so it does not require proving the supplied block inverse formula.

The moral graph of a Directed acyclic graph is formed by joining any two parents of a common child and then removing the directions from all edges. For D-separation, a path in the underlying undirected graph is active given $S$ when every noncollider on it is outside $S$, and every collider has itself or a descendant in $S$. Disjoint vertex sets $A$ and $B$ are D-separated by $S$ if no such active path connects them.

The adjacency characterization isA one-edge path cannot be blocked by conditioning on other vertices. For a nonadjacent pair, choose the later vertex $v$ in a topological ordering. The earlier vertex $u$ is a nondescendant and is not a parent of $v$, so the parents of $v$ separate the pair by the local Markov property of a directed acyclic graph.

Use faithfulness of a directed acyclic graph to mean that graphical and probabilistic independences agree, for all disjoint sets:This includes the global Markov property of a directed acyclic graph as well as the absence of extra independences. The conditional independence graph of $P$ is the undirected graph in which $u-v$ is absent exactly when $Z_u\perp Z_v\mid Z_{V\setminus \{u,v\}}$.

To identify this graph, condition on every vertex other than $u,v$. Any noncollider in the interior of a path is then conditioned on, so an active path must have only colliders internally. Two adjacent interior vertices cannot both be colliders: the arrow joining them has an arrowhead at only one of its ends. Thus an active path can have no interior vertex, giving a direct edge, or just one, giving $u\to w\leftarrow v$. In the latter case the conditioned common child $w$ activates the path. These possibilities are exactly the edges added or retained by moralization. Faithfulness therefore provesThis is why the moral graph equals the conditional independence graph under faithfulness.

For Gaussian graph estimation, collect the data into an $n\times p$ matrix $D$ and let $S_n=n^{-1}{\sum }_i{x}_i{x}_i^T$. The precision matrix $\Theta ={\Sigma }^{-1}$ has ${\Theta }_{jk}=0$ precisely for absent graph edges, by Gaussian conditional independence. In neighbourhood selection, fit a Lasso regression of each column on the others:Select the nonzero coefficients as neighbours of $j$, then make the graph undirected using either the OR rule, retaining an edge selected in at least one regression, or the AND rule, requiring both. These are instances of Nodewise Lasso.

The Graphical Lasso estimates the whole precision matrix jointly, for example byRead off its nonzero off-diagonal entries as graph edges. This expression uses an off-diagonal penalty; an all-entry penalty is another convention.

To reduce computation in the PC algorithm, start its skeleton search from an estimate of the conditional independence graph rather than the complete graph. The exact graph contains the true DAG skeleton, so oracle tests can remove its extra edges while retaining the true adjacencies. Fewer initial edges and smaller neighbourhoods reduce both candidate pairs and candidate conditioning sets.

For correctness of the orientation stage, preserve valid separating-set records. With an exact conditional independence graph, an initially absent pair $u,v$ has the full complement $V\setminus \{u,v\}$ as a separating set. Record that set, and record the usual discovered sets for edges removed later. Leaving an initially absent pair with an empty default could falsely mark an unshielded noncollider as a collider. This describes PC initialization from a conditional independence graph; with an estimated initial graph, screening errors can propagate into the output.

For disjoint nonempty index sets $A$ and $B$, partition the mean and covariance conformably. The conditional multivariate normal distribution isIf the sets overlap, the shared coordinates are fixed and this formula applies to $A\setminus B$.

Partition ${\Omega }_0$ into the $A$ and $A^c$ blocks. The block-inverse formula identifies the displayed conditional covariance withFor $A=\{j,k\}$, inversion of the two-by-two precision block givesThe denominator is positive, so the conditional covariance vanishes exactly when ${\Omega }_{0,jk}=0$. A Gaussian pair is independent exactly when it is uncorrelated, proving

Profiling the Gaussian likelihood over $\mu$ gives $\hat{\mu }=\bar{X}$. Apart from constants and a positive factor, the negative log-likelihood for the precision matrix isIts derivative is $-{\Omega }^{-1}+S$, so the unpenalized minimizer is $S^{-1}$. The Graphical Lasso solveswith some conventions also penalizing the diagonal.

The differential of the log-determinant is $d\log \det \Omega =\mathrm{Tr}({\Omega }^{-1}d\Omega )$. The subdifferential of the entrywise ${\ell }^1$ norm consists of symmetric matrices $Z$ withThe Karush-Kuhn-Tucker conditions for the Graphical Lasso are thereforeBecause $-\log \det \Omega$ is strictly convex on the positive-definite matrices, these conditions characterize the unique minimizer whenever it exists.