next up previous [pdf]

Next: PRECONDITIONING THE REGULARIZATION Up: PRECONDITIONED DATA FITTING Previous: Preconditioner with a starting

Guessing the preconditioner

We are tasked with coming up with ``trial solution''--a pretty vague assignment. Some kind of a scaling, smoothing, or shaping transformation $ \bold S$ of some mysterious ``preconditioned space'' $ \bold p$ should represent the model $ \bold m$ we seek. We begin by investigating how the shaper $ \bold S$ alters the gradient.

$ \bold m$ = $ \bold S\bold p$ introduces $ \bold S$ , implicitly defines $ \bold p$
$ \Delta\bold m $ = $ \bold S \Delta\bold p$ consequence of the above
$ \Delta\bold m $ = $ \bold F\T \bold r$ gradient is adjoint upon residual
$ \bold 0\approx \bold r $ = $ \bold F\bold m -\bold d $ residual in terms of $ \bold m$
$ \bold r $ = $ \bold F(\bold S\bold p) -\bold d $ residual in terms of $ \bold p$
$ \bold 0\approx \bold r $ = $ (\bold F\bold S)\bold p-\bold d$ reordering calculation
$ \Delta\bold p $ = $ (\bold F\bold S)\T \bold r $ gradient is adjoint upon residual
$ \Delta\bold p $ = $ \bold S\T\bold F\T\bold r $ reordering
$ \Delta\bold m $ = $ (\bold S\bold S\T) \bold F\T\bold r$ recalling $ \Delta\bold m=\bold S\Delta\bold p$

We may compare the gradient $ \Delta\bold m $ with and without preconditioning.

$ \Delta\bold m $ = $  \quad \quad \bold F\T \bold r$ original
$ \Delta\bold m $ = $ (\bold S\bold S\T) \bold F\T\bold r$ with preconditioning transformation
When the first vanishes, the second also vanishes. When the second vanishes, the first vanishes provided $ (\bold S\bold S\T)$ is a nonsingular matrix. As our choice of $ \bold S$ is quite arbitrary, it is marvelous the freedom we have to monkey with the gradient.

Remember that $ \bold r $ starts off being $ -\bold d$ . Compare the $ (\bold S\bold S\T)$ scaled gradient to the analytic solution.

$ \Delta\bold m $ = $ (\bold S\bold S\T) \bold F\T\bold r$ modified gradient
$ \bold m$ = $ (\bold F\T\bold F)^{-1} \bold F\T\bold d $ analytic solution
Mathematically, we see it would be delightful if $ (\bold S\bold S\T)$ were something like $ (\bold F\T\bold F)^{-1}$ , but we rarely have ideas how to arrange it. We do, however, have some understanding of the world of images, and understand where on the image we would like iterations to concentrate first, and what spatial frequencies are more relevant than others. If we cannot go all the way, as we cannot in giant imaging problems, it is important to make the important steps early.


next up previous [pdf]

Next: PRECONDITIONING THE REGULARIZATION Up: PRECONDITIONED DATA FITTING Previous: Preconditioner with a starting

2015-05-07