# Coordinate Descent for Variance-Component Models
## 3 Parameter-Expanded CD
### Linear Mixed Model Implementation
#### 3.3.2. Woodbury Matrix Identity  
Alternatively, if \(c\) is large (say \(c>n\)) but individually \(c_{i}<n\), for \(i=1,\ldots,m\), we can use the Woodbury identity to reduce each linear system to \(c_{k}\) dimensions (instead of \(n\) dimensions) when updating the component \(\gamma_{k}\). Suppose we are in cycle \(t+1\) of either PX-CD or PXI-CD and we wish to update the parameter \(\gamma_{k}\), where \(k\
eq 0\), then we can simplify the optimization,  
\[\gamma_{k}^{(t+1)}=\operatorname*{arg\,min}_{x\geq 0}\,h_{k}(x),\qquad h_{k}(x )=H(\mathbf{\Omega}_{-k}+x\mathbf{V}_{k},\mathbf{C}),\]  
by viewing \(\mathbf{\Omega}_{-k}+x\mathbf{V}_{k}=\mathbf{\Omega}+(x-\gamma_{k}^{(t)})\mathbf{Z}_ {k}\mathbf{Z}_{k}^{\top}\) as a low-rank perturbation to the matrix \(\mathbf{\Omega}\). The Woodbury identity gives the expression for the inverse,  
\[\left[\mathbf{\Omega}+(x-\gamma_{k}^{(t)})\mathbf{Z}_{k}\mathbf{Z}_{k}^{\top} \right]^{-1}=\mathbf{\Omega}^{-1}-(x-\gamma_{k}^{(t)})\mathbf{\Omega}^{-1}\mathbf{Z}_ {k}\Big{[}\mathbf{I}_{c_{k}}+(x-\gamma_{k}^{(t)})\mathbf{Z}_{k}^{\top}\mathbf{ \Omega}^{-1}\mathbf{Z}_{k}\Big{]}^{-1}\mathbf{Z}_{k}^{\top}\mathbf{\Omega}^{-1}, \tag{20}\]  
which contains the unperturbed inverse matrix \(\mathbf{\Omega}^{-1}\) and the inverse of a smaller \(c_{k}\times c_{k}\) matrix. In this implementation of PXI-CD and PX-CD we re-compute and store the matrix \(\mathbf{\Omega}^{-1}\) after each coordinate update. Let \(\mathbf{w}:=\mathbf{Z}_{k}^{\top}\mathbf{\Omega}^{-1}\mathbf{y}\), then the line search along the \(k\)-th component (\(k\
eq 0\)) of the function \(H\) simplifies to  
\[h_{k}(x)=-(x-\gamma_{k}^{(t)})\mathbf{w}^{\top}\Big{[}\mathbf{I}_{c_{k}}+(x-\gamma _{k}^{(t)})\mathbf{Z}_{k}^{\top}\mathbf{\Omega}^{-1}\mathbf{Z}_{k}\Big{]}^{-1}\bm {w}+x\,\operatorname{tr}\Big{(}\mathbf{C}^{-1}\mathbf{Z}_{k}\mathbf{Z}_{k}^{ \top}\Big{)}+\text{const}.\]  
When implementing PXI-CD, there is no additional cost when using the Woodbury identity, as the update \(\mathbf{C}\leftarrow\mathbf{\Omega}\) is made after every coordinate update and the trace term in the line search can be evaluated cheaply because \(\mathbf{\Omega}^{-1}\) is known. We can now implement [PERSON]'s method to find the minimum of \(h_{k}(x)\). Let  
\[\mathbf{B}:=\mathbf{Z}_{k}^{\top}\mathbf{\Omega}^{-1}\mathbf{Z}_{k},\qquad\mathbf{ M}:=\mathbf{I}_{c_{k}}+(x-\gamma_{k}^{(t)})\mathbf{B}.\]  
If we then solve the \(c_{k}\)-dimensional linear systems \(\mathbf{M}\mathbf{d}=\mathbf{w}\) and \(\mathbf{M}\mathbf{f}=\mathbf{B}\mathbf{d}\) with CG and store the solution in the vectors \(\mathbf{d}\) and \(\mathbf{f}\), respectively, we can evaluate the first and second derivatives of \(h_{k}(x)\) as  
\[h_{k}^{\prime}(x)=-\mathbf{w}^{\top}\mathbf{d}+(x-\gamma_{k}^{(t)})\mathbf{d}^{\top} \mathbf{B}\mathbf{d}+\operatorname{tr}(\mathbf{B}),\qquad h_{k}^{\prime\prime}(x)= 2\mathbf{d}^{\top}\mathbf{B}\mathbf{d}+2(x-\gamma_{k}^{(t)})\mathbf{d}^{\top}\mathbf{B} \mathbf{f}, \tag{21}\]  
and implement the Newton steps (14). The derivation of these derivative expressions are provided in Appendix B. After each coordinate \(k\) is updated we evaluate and store the updated inverse covariance matrix,  
\[\mathbf{\Omega}^{-1}\leftarrow\Big{[}\mathbf{\Omega}+(\gamma_{k}^{(t+1)}-\gamma_{k}^{ (t)})\mathbf{Z}_{k}\mathbf{Z}_{k}^{\top}\Big{]}^{-1},\]  
using (20), where we invert a smaller \(c_{k}\times c_{k}\) matrix only. When \(k=0\), no reduction in complexity can be made as the perturbation to \(\mathbf{\Omega}\) is full-rank and we update \(\gamma_{0}\) as we did in Section 3.1. If \(c=\sum_{i=1}^{m}c_{i}<n\), then we can use an alternate form of the Woodbury identity,  
\[\mathbf{\Omega}^{-1}=\gamma_{0}^{-1}\Big{[}\mathbf{I}-\mathbf{W}(\gamma_{0}\mathbf{ I}+\mathbf{W}^{\top}\mathbf{W})^{-1}\mathbf{W}^{\top}\Big{]},\]  
where \(\mathbf{W}:=\mathbf{Z}\mathbf{\Sigma}^{1/2}\) to update \(\mathbf{\Omega}^{-1}\) after \(\gamma_{0}\) has been updated.