Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 205 / 2

The matrix $S$ is the sample covariance matrixChanging $n$ to $n-1$ is another convention, but the objective must use the same convention throughout.

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.

Multiply the Karush-Kuhn-Tucker conditions on the right by $\hat{\Omega }$ and take the matrix trace:Symmetry and the defining property of the subgradient of the absolute value giveConsequently the last two terms in the objective sum to $p$, and hence

Let ${\hat{\Omega }}^{(k)}$ solve the $k$th diagonal-block problem and setIts inverse is block diagonal. On each diagonal block, the Graphical-Lasso Karush-Kuhn-Tucker conditions hold by the definition of ${\hat{\Omega }}^{(k)}$. On the off-diagonal blocks chooseThe assumed inequalities $|S_{ij}|\le \lambda$ ensure that every entry lies in $[-1,1]$, exactly the allowed subgradient at a zero entry of $\tilde{\Omega }$.

Thus $-{\tilde{\Omega }}^{-1}+S+\lambda Z=0$ on every block. The KKT conditions and the fact that the objective is strictly convex prove that $\tilde{\Omega }=\hat{\Omega }$, giving the claimed block decomposition.