Preconditioning

Next: Monkeying with the gradient Up: Preconditioning Previous: Preconditioning

# 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

 (1)

where is the map we seek, columns of the matrix are shapes'' that we like, and coefficients in are unknown coefficients to select amounts of the favored shapes. The variables are often called the preconditioned variables''. It is not necessary that 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

 (2)

and get

 (3)

We pass the operator to our iterative solver. After finding the best fitting , we merely evaluate 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 and we have iterative application of and .

Our hope is that the number of iterations decreases because we are clever, or because we have been lucky in our choice of . Hopefully, the extra work of the preconditioner operator is not large compared to . If we should be so lucky that , then we get the solution immediately. Obviously we would try any guess with . Where I have known such matrices, I have often found that convergence is accelerated, but not by much. Sometimes it is worth using for a while in the beginning, but later it is cheaper and faster to use only . A practitioner might regard the guess of as prior information, like the guess of the initial model .

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

Subsections
 Preconditioning

Next: Monkeying with the gradient Up: Preconditioning Previous: Preconditioning

2011-08-20