Graphical Lassoの解がなぜ正定値になるのか

スパース推定の 5.2節にあるgraphical lassoの解が非負定値になるのかというご質問をいただきました。研究者でも理解している人がほとんどいない問題です。難しいと感じた方は、遠慮なくご質問ください。

$W$は最初サンプル共分散行列$S$であり($W=S+\lambda I$で始める方法もある)、正定値行列の逆行列は正定値ですから、$W$が最後まで非負定値であることを示せればよいことになります。すなわち、毎回の$W$の更新が非負定値を非負定値に変換するものであれば良いことになります。まず、$$ \det \left[ \begin{array}{ll}W_{11}&w_{12}\\w_{21}&w_{22}\end{array}\right]=\det \left[ \begin{array}{ll}W_{11}&w_{12}\\0&w_{22}-w_{21}W_{11}^{-1}w_{12}\end{array}\right]$$となることに注意します。更新前に$W$が非負定値なら$,W_{11}$も非負定値であり、$W_{11}$は更新しないので、右辺の右下の成分が減少しなければ、更新後も非負定値です。以下では、$w_{21}W^{-1}w_{12}$が増加しないことを示します。(5.11)は、$$\frac{1}{2}\beta^TW_{11}^{-1}\beta-\beta^{T}s_{12}+\lambda\|\beta\|_1$$の最小化になります。$\beta=W^{^1}_{11}(s_{12}+\lambda\psi_{12})$を代入すると、$\beta_j\not=0, =0$によらず$|\beta_j|=-\lambda\psi_{12,j}\beta_j$となり($\psi_{12,j}$は$\psi_{12}$の第$j$成分)、$\|\beta\|_1=-\lambda\psi_{12}^T\beta$となる。したがって、
$$-\frac{1}{2}(s_{12}+\lambda\psi_{12})^TW_{11}^{-1}(s_{12}+\lambda\psi_{12})$$となるので、双対問題である$\|\gamma\|_\infty\leq \lambda$のもとでの
$$-\frac{1}{2}(s_{12}+\gamma)^TW_{11}^{-1}(s_{12}+\gamma)$$の最大化になり、その最適解$\gamma$を用いて、$\psi_{12}=\gamma/\lambda$および $w_{12}=s_{12}+\lambda\psi_{12}$((5.9)式)が得られます。そして、次回($p$回後)回ってきたときに$W_{11}$の値は変わっていますが、$W$と$W_{11}$の正定値性は維持されます。更新によって、$w_{12}$の値はより良い値となるので、$w_{21}W^{-1}_{11}w_{12}$の値はより小さくなり、正定値性が維持されます。

参考文献: R. Mazumder and T. Hastie, “The graphical lasso: New insights and alternatives”, Electronic Journal of Statistics. Vol 6, pp 2125-2149 (2012)