I.3.3.1: Two-block Least Squares.

Suppose we have a linear least squares problems with two sets of predictors $A_1$ and $A_2,$ and outcome vector $b$. Matrices $A_1$ and $A_2$ are $m\times n_1$ and $m\times n_2$, and the vector of regressions coefficients $x=(x_1\mid x_2)$ is of length $n=n_1+n_2.$ Without loss of generality we assume $n_1\leq n_2$.

Minimizing $f(x)=(b-A_1x_1-A_2x_2)'(b-A_1x_1-A_2x_2)$ is then conveniently done by block relaxation, alternating the two steps $$\begin{align*} x_1^{(k+1)}&=A_1^+(b-A_2x_2^{(k)}),\\ x_2^{(k+1)}&=A_2^+(b-A_1x_1^{(k+1)}). \end{align*}$$ Here $A_1^+$ and $A_2^+$ are Moore-Penrose inverses.

Define $$\begin{align*} c&\mathop{=}\limits^{\Delta}A_1^+b,\\ d&\mathop{=}\limits^{\Delta}A_2^+b,\\ R&\mathop{=}\limits^{\Delta}A_1^+A_2^{\ },\\ S&\mathop{=}\limits^{\Delta}A_2^+A_1^{\ }. \end{align*}$$ Then the iterations are $$\begin{align} x_1^{(k+1)}&=c-Rx_2^{(k)},\\ x_2^{(k+1)}&=d-Sx_1^{(k+1)}. \end{align}$$ A solution $(\hat x_1,\hat x_2)$ of the least squares problem satisfies $$\begin{align} \hat x_1&=c-R\hat x_2,\\ \hat x_2&=s-S\hat x_1, \end{align}$$ and thus $$\begin{align*} (x_1^{(k+1)}-\hat x_1)&=R(x_2^{(k)}-\hat x_2),\\ (x_2^{(k+1)}-\hat x_2)&=S(x_1^{(k+1)}-\hat x_1), \end{align*}$$ and $$\begin{align*} (x_2^{(k+1)}-\hat x_2)&=SR(x_2^{(k)}-\hat x_2),\\ (x_1^{(k+1)}-\hat x_1)&=RS(x_1^{(k)}-\hat x_1). \end{align*}$$ The matrices $SR=A_2^+A_1^{\ }A_1^+A_2^{\ }$ and $RS=A_1^+A_2^{\ }A_2^+A_1^{\ }$ have the same eigenvalues $\lambda_s$, equal to $\rho_s^2$, the squares of the canonical correlations of $A_1$ and $A_2$. Consequently $0\leq\lambda_s\leq 1$ for all $s$. Specifically there exists a non-singular $K$ of order $n_1$ and a non-singular $L$ of order $n_2$ such that $$\begin{align*} K'A_1'A_1^{\ }K&=I_1,\\ L'A_2'A_2^{\ }L&=I_2,\\ K'A_1'A_2^{\ }L&=D. \end{align*}$$ Here $I_1$ and $I_2$ are diagonal, with the $n_1$ and $n_2$ leading diagonal elements equal to one and all other elements zero. $D$ is a matrix with the non-zero canonical correlations in non-increasing order along the diagonal and zeroes everywhere else. This implies $R=KDL^{-1}$ and $S=LD'K^{-1}$, and consequently $RS=KDD'K^{-1}$ and $SR=LD'DL^{-1}$.

Let us look at the convergence speed of the $x_1^{(k)}$. The results for $x_2^{(k)}$ will be basically the same. Define $$\delta^{(k)}\mathop{=}\limits^{\Delta}K^{-1}(x_1^{(k)}-\hat x_1^{\ })$$ It follows, using $RS=KDD'K^{-1}$, that $\delta^{(k)}=\Lambda^k\delta^{(0)}$, with the squared canonical correlations on the diagonal of $\Lambda=DD'.$ If $\lambda_+\mathop{=}\limits^{\Delta}\max_i\lambda_i>0$ and $\mathcal{I}=\left\{i\mid\lambda_i=\lambda_+\right\}$ then $$\frac{\delta^{(k)}_i}{\lambda_+^k}\rightarrow\begin{cases} \delta^{(0)}_i&\text{ if }i\in\mathcal{I},\\ 0&\text{ otherwise} \end{cases}$$ and thus $$\frac{\|\delta^{(k+1)}\|}{\|\delta^{(k)}\|}\rightarrow\lambda^+.$$ This implies $$\frac{\|x_1^{(k)}-\hat x_1^{\ }\|}{\lambda^k}\rightarrow\|\sum_{i\in\mathcal{I}}\delta_i^{(0)}k_i^{\ }\|$$ where the $k_i$ are columns of $K$. In turn this implies $$\frac{\|x_1^{(k+1)}-\hat x_1^{\ }\|}{\|x_1^{(k)}-\hat x_1^{\ }\|}\rightarrow\lambda.$$