# Coordinate Descent for Variance-Component Models
## 3 Parameter-Expanded CD
Minimizing \(H\) with respect to the \(k\)-th component of the original parameter \(\boldsymbol{\gamma}\) yields a function of the form:  
\[h_{k}(x):=H(\mathbf{\Omega}_{-k}+x\mathbf{V}_{k},\mathbf{C})=\boldsymbol{y}^{ \top}(\mathbf{\Omega}_{-k}+x\mathbf{V}_{k})^{-1}\boldsymbol{y}+x\operatorname{ tr}\Bigl{(}\mathbf{C}^{-1}\mathbf{V}_{k}\Bigr{)}+\text{const.},\ \ \ x\geq 0. \tag{10}\]  
One of the main advantages of the PX-CD procedure over the basic coordinate descent in Algorithm 1 is that the optimization along each coordinate has a unique minimum. **Lemma 1**. : \(h_{k}(x)\) _has a unique minimizer for \(x\geq 0\)._  
Proof. : We now show that on \([0,\infty)\), the function \(h_{k}(x)\) is either strictly convex or a linear function with a strictly positive gradient. We first consider the case where \(\mathbf{\Omega}_{-k}\) is invertible. From [13], we have the GEV decomposition: \((\mathbf{V}_{k},\mathbf{\Omega}_{-k})\to(\mathbf{D}_{k},\mathbf{U}_{k})\) where \(\mathbf{D}_{k}\in\mathbb{R}^{n\times n}\) is a diagonal matrix with non-negative entries and \(\mathbf{U}_{k}\in\mathbb{R}^{n\times n}\) is invertible. In a similar fashion to the simplified basic CD expression (7), let \(\mathbf{\alpha}_{k}=\mathbf{U}_{k}^{\top}\mathbf{y}\) and \(\mathbf{d}_{k}=\operatorname{diag}(\mathbf{D}_{k})\). Then, \(h_{k}(x)\) can be simplified to,  
\[h_{k}(x)=\sum_{j=1}^{n}\frac{\alpha_{k,j}^{2}}{d_{k,j}x+1}+x\operatorname{tr} \left(\mathbf{C}^{-1}\mathbf{V}_{k}\right)+\text{const}. \tag{11}\]  
We then obtain the first and second derivatives,  
\[h_{k}^{\prime}(x)=-\sum_{j=1}^{n}\frac{\alpha_{k,j}^{2}d_{k,j}}{(d_{kj}x+1)^{ 2}}+\operatorname{tr}\left(\mathbf{C}^{-1}\mathbf{V}_{k}\right),\qquad h_{k} ^{\prime\prime}(x)=\sum_{j=1}^{n}\frac{2\alpha_{k,j}^{2}d_{k,j}^{2}}{(d_{kj} x+1)^{3}}. \tag{12}\]  
where \(d_{j}\geq 0\). If there exists \(j\) such that \(\alpha_{k,j}d_{k,j}\
eq 0\), then \(h^{\prime\prime}(x)>0\) for \(x\geq 0\). Then, \(h\) is strictly convex and attains a unique global minimizer \(x^{*}\in[0,\infty)\). Suppose that \(\alpha_{k,j}d_{k,j}=0\) for \(j=1,\ldots,n\) then \(h_{k}^{\prime}(x)=\operatorname{tr}\left(\mathbf{C}^{-1}\mathbf{V}_{k}\right)\). If we can show that \(\operatorname{tr}\left(\mathbf{C}^{-1}\mathbf{V}_{k}\right)>0\), then \(h_{k}(x)\) is strictly increasing on \([0,\infty)\), and \(x^{*}=0\) is the unique global minimizer for \(x\in[0,\infty)\). We note that the matrix \(\mathbf{C}^{-1}\) is positive-definite since \(\mathbf{C}=\sum_{l=0}^{m}\hat{\gamma}_{1}\mathbf{V}_{l}\) is invertible and positive semi-definite. Therefore, the symmetric square root factorization, \(\mathbf{C}^{-1}=\mathbf{C}^{-1/2}\mathbf{C}^{-1/2}\) exists, and  
\[\operatorname{tr}\left(\mathbf{C}^{-1}\mathbf{V}_{k}\right)=\operatorname{tr} \left(\mathbf{C}^{-1/2}\mathbf{V}_{k}\mathbf{C}^{-1/2}\right),\]  
due to the invariant cyclic nature of the trace. The matrix \(\mathbf{C}^{-\frac{1}{2}}\mathbf{V}_{k}\mathbf{C}^{-\frac{1}{2}}\) is positive semi-definite as \(\mathbf{z}^{\top}\mathbf{C}^{-1/2}\mathbf{V}_{k}\mathbf{C}^{-1/2}\mathbf{z}=\|\mathbf{ V}_{k}^{1/2}\mathbf{C}^{-1/2}\mathbf{z}\|_{2}^{2}\geq 0\) for all \(\mathbf{z}\in\mathbb{R}^{n}\). Since \(\mathbf{C}^{-\frac{1}{2}}\mathbf{V}_{k}\mathbf{C}^{-\frac{1}{2}}\) is a non-zero matrix and positive-semi-definite, \(\operatorname{tr}\left(\mathbf{C}^{-1}\mathbf{V}_{k}\right)>0\) and \(h_{k}(x)\) has a strictly positive slope, which implies that \(x^{*}=0\) is the unique global minimizer for \(x\in[0,\infty)\). Consider the case \(\dim(\operatorname{span}\{\mathbf{V}_{1},\ldots,\mathbf{V}_{m}\})=r<n\). Assuming \(\gamma_{0}>0\), then \(\mathbf{\Omega}_{-k}\) will be invertible except when \(k=0\). When \(\mathbf{\Omega}_{-0}\) is singular, a simplified expression in the form of (11) may be difficult to find. Instead, we take the singular value decomposition (SVD) of the symmetric matrix \(\mathbf{\Omega}_{-0}\),  
\[\mathbf{\Omega}_{-0}=\mathbf{Q}^{\top}\mathbf{\Lambda}\mathbf{Q},\quad\mathbf{ \Lambda}=