Let us visualize W by showing it alongside S, our empirical covariance matrix: $$\mathrm{W}=\left( \begin{array}{ll}{W_{11}} & {W_{12}} \\ {W_{12}^{T}} & {W_{22}}\end{array}\right), \quad \mathrm{S}=\left( \begin{array}{ll}{S_{11}} & {S_{12}} \\ {S_{12}^{T}} & {S_{22}}\end{array}\right).$$ Remember W and S are both p*p symmetric matrices. Then as partitioned above, \(W_{11}\) represents the upper left (p-1)*(p-1) block, \(W_{12}\) represents the p-1 vector, and \(W_{22}\) a scalar on the diagonal, similarly for S. You will find this view of the matrix handy when we get into the Graphical Lasso algorithm itself. \(\\\) So how do we estimate W properly? The approach actually taken by the Graphical Lasso is to ignore the diagonal elements namely \(W_{22}\) here and focus on the vector \(W_{12}\); so more accurately, we should say that Graphical Lasso estimates all the off-diagonal elements of W (leaving the diagonal elements as when W is initiated, e.g., using the diagonal elements of S). \(\\\) Basically, it goes over all dimensions 1 to p one at a time, during which it updates the estimate for \(W_{12}\). There are indeed research papers out there trying to estimate diagonal elements, but those are less of a concern here because we are more interested in finding out about the off-diagonal elements anyway. \(\\\) Let us say that now we are trying to update \(W_{12}\) for dimension p; how shall we proceed then? Let us review the goal function: $$\arg \max _{W}\left(\log \operatorname{det}(W) :\|W-S\|_{\infty} \leq \lambda\right).$$ Let us try break it down and try expose terms like \(W_{12}\). \(\\\) Note we have such a property for determinant of matrix: $$\operatorname{det} \left( \begin{array}{ll}{A} & {B} \\ {C} & {D}\end{array}\right)=\left(D-C A^{-1} B\right) \operatorname{det}(A).$$ Making use of the partition of W above, we have: $$\operatorname{det}(W)=\left(W_{22}-W_{12}^{T} W_{11}^{-1} W_{12}\right) \operatorname{det}\left(W_{11}\right).$$ Plugging in, seeing \(W_{11}\) being fixed and removing unnecessary terms, we have our goal function as: $$\arg \min _{W_{12}}\left(W_{12}^{T} W_{11}^{-1} W_{12} :\left\|W_{12}-S_{12}\right\|_{\infty} \leq \lambda\right).$$ This looks great as it is a quadratic function which we are quite familiar with and have many tools to work on it. The only thing not so sweet seems to be the infinity norm; let us try get rid of it then, by transforming the problem to its dual form. Let us set Z = \(W_{12}-S_{12}\), now we have our problem with two constraints: $$\arg \min _{W_{12}}\left(W_{12}^{T} W_{11}^{-1} W_{12} :\|Z\|_{\infty} \leq \lambda \text { and } Z-W_{12}+S_{12}=0\right).$$ Constructing the Lagrangian based on the equality constraint and rewriting our problem, we have: $$\inf _{W_{12}, Z}\left(W_{12}^{T} W_{11}^{-1} W_{12}+X^{T}\left(Z-W_{12}+S_{12}\right) :| | Z| |_{\infty} \leq \lambda\right).$$ The above can be further split into: $$\inf _{W_{12}}\left(W_{12}^{T} W_{11}^{-1} W_{12}-X^{T} W_{12}\right)-\lambda \sup _{Z}\left((-X)^{T} \frac{1}{\lambda} Z :| | \frac{1}{\lambda} Z| |_{\infty} \leq 1\right)+X^{T} S_{12}.$$ Note the second term is exactly the textbook form for the dual norm of L1 norm, which equals to \(\lambda\|X\|_{1}\). The first term can be solved taking gradient with regards to \(W_{12}\) and plugging the result back in. \(\\\) So now we have the goal function as below: $$\arg \min _{X}\left(\frac{1}{4} X^{T} W_{11} X-X^{T} S_{12}+\lambda| | X\left\|_{1}\right)\right..$$ Note the original Graphical Lasso papers seem to have dropped the 1/4 coefficient for ease of computation, which seems reasonable as it does not affect the solution much and brings us the nice form of the good old lasso problem by using square-completing trick: $$\underset{X}{\operatorname{argmin}}\left(\frac{1}{2}| | W_{11}^{\frac{1}{2}} X-W_{11}^{-\frac{1}{2}} S_{12}| |_{2}^{2}+\rho\|X\|_{1}\right).$$ This is definitely something that we have a ready-made solution of. Now we can have a good sleep, resting assured that there is a solution. 