PRECONDITIONED DATA FITTING

Iterative methods (like conjugate-directions) can sometimes be accelerated by a change of variables. The simplest change of variable is called a ``trial solution''. Formally, we write the solution as

$$\bold m \quad =\quad\bold S \bold p$$ (1)

where $\bold m$ is the map we seek, columns of the matrix $\bold S$ are ``shapes'' that we like, and coefficients in $\bold p$ are unknown coefficients to select amounts of the favored shapes. The variables $\bold p$ are often called the ``preconditioned variables''. It is not necessary that $\bold S$ be an invertible matrix, but we'll see later that invertibility is helpful. Take this trial solution and insert it into a typical fitting goal

$$\bold 0 \quad\approx\quad \bold F \bold m \ -\ \bold d$$ (2)

and get

$$\bold 0 \quad\approx\quad \bold F \bold S \bold p \ -\ \bold d$$ (3)

We pass the operator $\bold F \bold S$ to our iterative solver. After finding the best fitting $\bold p$,we merely evaluate $\bold m = \bold S \bold p$to get the solution to the original problem.

We hope this change of variables has saved effort. For each iteration, there is a little more work: Instead of the iterative application of $\bold F$ and $\bold F'$we have iterative application of $\bold F \bold S$ and $\bold S'\bold F'$.Our hope is that the number of iterations decreases because we are clever, or because we have been lucky in our choice of $\bold S$.Hopefully, the extra work of the preconditioner operator $\bold S$is not large compared to $\bold F$.If we should be so lucky that $\bold S= \bold F^{-1}$,then we get the solution immediately. Obviously we would try any guess with $\bold S\approx \bold F^{-1}$.Where I have known such $\bold S$ matrices, I have often found that convergence is accelerated, but not by much. Sometimes it is worth using $\bold F \bold S$ for a while in the beginning, but later it is cheaper and faster to use only $\bold F$.A practitioner might regard the guess of $\bold S$as prior information, like the guess of the initial model $\bold m_0$.

For a square matrix $\bold S$,the use of a preconditioner should not change the ultimate solution. Taking $\bold S$ to be a wide rectangular matrix, reduces the number of adjustable parameters, changes the solution, gets it quicker, but lower resolution.

 

• Preconditioner with a starting guess