Finite-budget block and cyclic-coordinate graphical-lasso procedure

Input an integer $p\ge 2$, a real symmetric positive-semidefinite matrix $S\in {\mathbb{S}}_{+}^p$, a real $\lambda >0$, and positive integers $R,K$. The output is either failure or a matrix $\mathrm{\Theta }\in {\mathbb{S}}_{++}^p$. Let $I_p$ be the $p\times p$ identity, $t_{+}=\max (t,0)$, $\mathrm{sign}(t)=1$ for $t>0$, $0$ for $t=0$, and $-1$ for $t<0$, and $\mathsf{S}\mathsf{o}\mathsf{f}\mathsf{t}(t,\lambda )=\mathrm{sign}(t)(\mathrm{\mid }t\mathrm{\mid }-\lambda {)}_{+}$. Initialize $W=S+\lambda I_p$.

For each outer sweep $r=1,\dots ,R$, and within it for each original-coordinate index $j=1,\dots ,p$, use the temporary coordinate order ${\pi }_j=(1,\dots ,j-1,j+1,\dots ,p,j)$. Form the same reindexing of both matrices, $S_{ab}^{(j)}=S_{{\pi }_j(a),{\pi }_j(b)}$ and $W_{ab}^{(j)}=W_{{\pi }_j(a),{\pi }_j(b)}$, for $1\le a,b\le p$. Set $V=(W_{ab}^{(j)}{)}_{a,b<p}$, $s=(S_{a,p}^{(j)}{)}_{a<p}$, and $d=W_{pp}^{(j)}$. Initialize $\beta =0\in {\mathbb{R}}^{p-1}$. For each of $K$ inner sweeps, update coordinates $\mathrm{\ell }=1,\dots ,p-1$ in increasing order: if $V_{\mathrm{\ell }\mathrm{\ell }}\le 0$, return failure; otherwise set ${\beta }_{\mathrm{\ell }}\leftarrow \frac{\mathsf{S}\mathsf{o}\mathsf{f}\mathsf{t}\text{\hspace{0.17em}⁣}(s_{\mathrm{\ell }}-{\sum }_{\begin{array}{c}1\le k<p\\ k\mathrm{\ne }\mathrm{\ell }\end{array}}{V}_{\mathrm{\ell }k}{\beta }_k,\lambda )}{V_{\mathrm{\ell }\mathrm{\ell }}}\mathrm{.}$

After the inner sweeps, form ${\tilde{W}}^{(j)}=\left(\begin{array}{cc}V& V\beta \\ (V\beta {)}^T& d\end{array}\right)$. Restore original indexing by forming the candidate matrix $W^{\mathrm{c}\mathrm{a}\mathrm{n}\mathrm{d}}$ with $W_{{\pi }_j(a),{\pi }_j(b)}^{\mathrm{c}\mathrm{a}\mathrm{n}\mathrm{d}}={\tilde{W}}_{ab}^{(j)}$ for all $1\le a,b\le p$. Compute a symmetric eigendecomposition of $W^{\mathrm{c}\mathrm{a}\mathrm{n}\mathrm{d}}$; if any eigenvalue is nonpositive, return failure. Otherwise set $W=W^{\mathrm{c}\mathrm{a}\mathrm{n}\mathrm{d}}$ before proceeding to the next original-coordinate index $j$. After all $R$ sweeps, return $\mathrm{\Theta }=W^{-1}$. This bounded truncation of the coupled block and lasso updates makes no convergence or optimizer claim.

The Elements of Statistical Learning, §17.3.2

Friedman, Hastie and Tibshirani, §§2–3