Ex. 9.2

Let $A$ be a known $k \times k$ matrix, $b$ be a matrix known $k$ -vector, and $z$ be an unknown $k$ -vector. A Gauss-Seidel algorithm for solving the linear system of equations $A z = b$ works by successively solving for element $z_{j}$ in the $j$ th equation, fixing all other $z_{j}$ 's at their current guesses. This process is repeated for $j = 1, 2, . . ., k, 1, 2, . . ., k, . . .,$ until convergence (Matrix computations).

(a)

Consider an additive model with $N$ observations and $p$ terms, with the $j$ th term to be fit by a linear smoother $S_{j}$ . Consider the following system of equations:

(\begin{matrix} I & S_{1} & S_{1} & \dots & S_{1} \\ S_{2} & I & S_{2} & \dots & S_{2} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ S_{p} & S_{p} & S_{p} & \dots & I \end{matrix}) (\begin{matrix} f_{1} \\ f_{2} \\ ⋮ \\ f_{p} \end{matrix}) = (\begin{matrix} S_{1} y \\ S_{2} y \\ ⋮ \\ S_{p} y \end{matrix}) .

Here each $f_{j}$ is an $N$ -vector of evaluations of the $j$ th function at the data points, and $y$ is an $N$ -vector of the response values. Show that backfitting is a blockwise Gauss-Seidel algorithm for solving system of equations.

(b)

Let $S_{1}$ and $S_{2}$ be symmetric smoothing operators (matrices) with eigenvalues in $[0, 1)$ . Consider a backfitting algorithm with response vector $y$ and smoothers $S_{1}$ , $S_{2}$ . Show that with any starting values, the algorithm converges and give a formula for the final iterates.

Soln. 9.2

(a)

For $j$ -th equation, we have

S_{j} f_{1} + . . . S_{j} f_{j - 1} + f_{j} + . . . + S_{j} f_{p} = S_{j} y,

so that

f_{j} = S_{j} (y - \sum_{k \neq j} f_{k})

which has the same as the second step in Algorithm 9.1. Therefore we can regard backfitting as a blockwise Gauss-Seidel algorithm.

(b)

Denote $f_{1} (k)$ and $f_{2} (k)$ as the value for the $k$ -th iteration with initial values $f_{1} (0)$ and $f_{2} (0)$ , we have

\begin{array}{rcl} f_{1} (k) & = & S_{1} (y - f_{2} (k - 1)) \\ f_{2} (k) & = & S_{2} (y - f_{1} (k - 1)) . \end{array}

Therefore it's easy to derive

\begin{array}{rcl} f_{2} (k) & = & S_{2} S_{1} f_{2} (k - 1) + S_{2} y - S_{2} S_{1} y \\ = & (S_{2} S_{1})^{2} f_{2} (k - 2) + (S_{2} S_{1} + I) (S_{2} y - S_{2} S_{1} y) \\ = & \dots \\ = & (S_{2} S_{1})^{k} f_{2} (0) + [(S_{2} S_{1})^{k - 1} + \dots + S_{2} S_{1} + I] (S_{2} y - S_{2} S_{1} y) . \end{array}

Thus, as $k \to \infty$ , we have $f_{2} (k)$ converges to

(I - S_{2} S_{1})^{- 1} (S_{2} - S_{2} S_{1}) y .

Similarly for $f_{1} (k)$ , it converges to

(I - S_{1} S_{2})^{- 1} (S_{1} - S_{1} S_{2}) y .