I.3.3.2: Multiple-block Least Squares.

Now suppose there are multiple blocks. We minimize the loss function $$f(x)=\mathbf{SSQ}(b-\sum_{j=1}^m A_jx_j).$$ Block relaxation in this case is Gauss-Seidel iteration.

The update formula for the Gauss-Seidel method is $$\beta_j^{(k+1)}=X_j'\left(y-\sum_{\ell=1}^{j-1}X_\ell^{\ }\beta_\ell^{(k+1)}-\sum_{\ell=j+1}^{m}X_\ell^{\ }\beta_\ell^{(k)}\right).$$ Define $C_L$ to be the block triangular matrix with the blocks $X_j'X_\ell^{\ }$ with $j>\ell$ of $C$ below the diagonal, and $C_U$ the block triangular matrix with the upper diagonal blocks $X_j'X_\ell^{\ }$ with $j<\ell$. Thus $C_L+C_U+I=C$ and $C_L=C_U'$. Now $$\beta^{(k+1)}=X'y-C_L\beta^{(k+1)}-C_U\beta^{(k)},$$ and thus $$\beta^{(k+1)}=(I+C_L)^{-1}X'y-(I+C_L)^{-1}C_U\beta^{(k)}.$$ The least squares estimate $\hat\beta$ satisfies $$\hat\beta=(I+C_L)^{-1}X'y-(I+C_L)^{-1}C_U\hat\beta,$$ and thus $$\beta^{(k+1)}-\hat\beta=-(I+C_L)^{-1}C_U(\beta^{(k)}-\hat\beta),$$ or $$\beta^{(k)}-\hat\beta=\left[-(I+C_L)^{-1}C_U\right]^k(\beta^{(0)}-\hat\beta).$$