Coordinate minimization, positive-definiteness invariant and termination of the finite-budget graphical-lasso procedure

Initially $W$ is symmetric, and for every nonzero $x\in {\mathbb{R}}^p$, $x^{T}Wx=x^{T}Sx+\lambda \mathrm{\parallel }x{\mathrm{\parallel }}^2\ge \lambda \mathrm{\parallel }x{\mathrm{\parallel }}^2>0$. Thus initialization is positive definite. If the current $W$ is positive definite, reindexing both its rows and columns only reindexes this quadratic form. For a nonzero $z\in {\mathbb{R}}^{p-1}$, extending $z$ by a last zero in the temporary ordering gives $z^{T}Vz>0$. Hence $V$ is positive definite and $V_{\mathrm{\ell }\mathrm{\ell }}=e_{\mathrm{\ell }}^{T}V{e}_{\mathrm{\ell }}>0$ at each coordinate.

Hold all coordinates except ${\beta }_{\mathrm{\ell }}=t$ fixed, and write $v=V_{\mathrm{\ell }\mathrm{\ell }}>0$ and $r=s_{\mathrm{\ell }}-{\sum }_{k\mathrm{\ne }\mathrm{\ell }}{V}_{\mathrm{\ell }k}{\beta }_k$. Expanding the symmetric quadratic gives $Q_{V,s}(\beta )=q(t)+C$, where $q(t)=\frac{1}{2}v{t}^2-rt+\lambda \mathrm{\mid }t\mathrm{\mid }$ and $C$ is independent of $t$. Put $a=(r-\lambda )\mathrm{/}v$ if $r>\lambda$, $a=0$ if $\mathrm{\mid }r\mathrm{\mid }\le \lambda$, and $a=(r+\lambda )\mathrm{/}v$ if $r<-\lambda$. In these three cases respectively put $u=1$, $u=r\mathrm{/}\lambda$, and $u=-1$. Then $va-r+\lambda u=0$, $\mathrm{\mid }u\mathrm{\mid }\le 1$, and $ua=\mathrm{\mid }a\mathrm{\mid }$, so $\mathrm{\mid }t\mathrm{\mid }-\mathrm{\mid }a\mathrm{\mid }-u(t-a)=\mathrm{\mid }t\mathrm{\mid }-ut\ge 0$. Consequently $q(t)-q(a)=\frac{1}{2}v(t-a{)}^2+\lambda (\mathrm{\mid }t\mathrm{\mid }-\mathrm{\mid }a\mathrm{\mid }-u(t-a))\ge \frac{1}{2}v(t-a{)}^2$, and the lower bound is strictly positive whenever $t\mathrm{\ne }a$. Thus $a=\mathsf{S}\mathsf{o}\mathsf{f}\mathsf{t}(r,\lambda )\mathrm{/}v$ is the unique coordinate minimizer. All quantities are real and division is by a positive number, so finitely many such updates produce a finite real vector $\beta$; the nonpositive-diagonal guard cannot fire while the current $W$ is positive definite.

For such a block, $V\beta$ and $d$ are finite and the block candidate $\left(\begin{array}{cc}V& V\beta \\ (V\beta {)}^T& d\end{array}\right)$ is symmetric. Restoring original indexing preserves symmetry. By [F2] any symmetric candidate $A$ has a representation $A=UD{U}^T$ with $U$ orthogonal and $D$ real diagonal. The identity $x^{T}Ax={\sum }_i{D}_{ii}(U^{T}x{)}_i^2$ shows that $A$ is positive definite if all $D_{ii}>0$; conversely applying positive definiteness to $x=U{e}_i$ shows that every $D_{ii}>0$. Thus the candidate guard accepts exactly the positive-definite candidates. Initialization, the within-block reasoning and this acceptance rule give induction over all reached blocks: every accepted $W$ is symmetric positive definite, and each later block again has the properties proved above until a candidate guard returns failure.

There are at most $Rp$ blocks, each with $K(p-1)$ coordinate updates and one finite-dimensional eigenvalue test; early failure only decreases these counts. Every reached operation is well-defined by the preceding steps and the stipulated exact matrix operations, so execution terminates with failure or completes all blocks. In the latter case the final $W=UD{U}^T$ has positive diagonal eigenvalues by step 3.1. Hence $W^{-1}=U{D}^{-1}{U}^T$ exists, is symmetric and has $x^T{W}^{-1}x={\sum }_i{D}_{ii}^{-1}(U^{T}x{)}_i^2>0$ for every nonzero $x$. This proves every asserted property without a convergence or global-optimizer inference.