Preconditioning

OPPORTUNITIES FOR SMART DIRECTIONS

Recall the fitting goals (18)

$$\begin{array}{llllllcl} \bold 0 &\approx& \bold r_d &=& \bold... ...\bold r_m &=& \bold A \bold m &=& \bold I & \bold p \end{array}$$ (18)

Without preconditioning we have the search direction

$$\Delta \bold m_{\rm bad} \quad =\quad \left[ \begin{array}{cc} \b... ...ray} \right] \left[ \begin{array}{c} \bold r_d \\ \bold r_m \end{array} \right]$$ (19)

and with preconditioning we have the search direction

$$\Delta \bold p_{\rm good} \quad =\quad \left[ \begin{array}{cc} (... ...ray} \right] \left[ \begin{array}{c} \bold r_d \\ \bold r_m \end{array} \right]$$ (20)

The essential feature of preconditioning is not that we perform the iterative optimization in terms of the variable $\bold p$ . The essential feature is that we use a search direction that is a gradient with respect to $\bold p\T$ not $\bold m\T$ . Using $\bold A\bold m=\bold p$ we have $\bold A\Delta \bold m=\Delta \bold p$ . This enables us to define a good search direction in model space.

$$\Delta \bold m_{\rm good} \quad =\quad \bold A^{-1} \Delta \bold ... ...quad \bold A^{-1} (\bold A^{-1})\T \bold F\T \bold r_d + \bold A^{-1} \bold r_m$$ (21)

Define the gradient by $\bold g=\bold F\T\bold r_d$ and notice that $\bold r_m=\bold p$ .

$$\Delta \bold m_{\rm good} \quad =\quad \bold A^{-1} (\bold A^{-1})\T \ \bold g + \bold m$$ (22)

The search direction (22) shows a positive-definite operator scaling the gradient. Each component of any gradient vector is independent of each other. All independently point a direction for descent. Obviously, each can be scaled by any positive number. Now we have found that we can also scale a gradient vector by a positive definite matrix and we can still expect the conjugate-direction algorithm to descend, as always, to the ``exact'' answer in a finite number of steps. This is because modifying the search direction with $\bold A^{-1} (\bold A^{-1})\T$ is equivalent to solving a conjugate-gradient problem in $\bold p$ .

Preconditioning