next up previous [pdf]

Next: The meaning of the Up: Preconditioning Previous: THE PRECONDITIONED SOLVER

OPPORTUNITIES FOR SMART DIRECTIONS

Recall the fitting goals (10) with weights $ \bold W$ being absorbed into the operator $ \bold F$ and the data $ \bold d$ .

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

Without preconditioning, we have the search direction:

$\displaystyle \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]$ (18)

and with preconditioning, we have the search direction:

$\displaystyle \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]$ (19)

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$ , which enables us to define a good search direction in $ \bold m$ space.

$\displaystyle \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$ (20)

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

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

The search direction (21) shows a positive-definite operator scaling the gradient. Each component of any gradient vector is independent of each other. All independently point (negatively) to 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. The reason is that modifying the search direction with $ \bold A^{-1} (\bold A^{-1})\T$ is equivalent to solving a conjugate-gradient problem in $ \bold p$ . We'll see in Chapter [*], that our specifying $ \bold A^{-1} (\bold A^{-1})\T$ amounts to us specifying a prior expectation of the spectrum of the model $ \bold m$ .



Subsections
next up previous [pdf]

Next: The meaning of the Up: Preconditioning Previous: THE PRECONDITIONED SOLVER

2015-05-07