Model fitting by least squares

Next: Why steepest descent is Up: KRYLOV SUBSPACE ITERATIVE METHODS Previous: Sign convention

## Method of random directions and steepest descent

Let us minimize the sum of the squares of the components of the residual vector given by:

 (50) (51)

A contour plot is based on an altitude function of space. The altitude is the dot product . By finding the lowest altitude, we are driving the residual vector as close as we can to zero. If the residual vector reaches zero, then we have solved the simultaneous equations . In a two-dimensional world, the vector has two components, . A contour is a curve of constant in -space. These contours have a statistical interpretation as contours of uncertainty in , with measurement errors in .

Let us see how a random search-direction can be used to reduce the residual . Let be an abstract vector with the same number of components as the solution , and let contain arbitrary or random numbers. We add an unknown quantity of vector to the vector , and thereby create :

 (52)

The new gives a new residual:
 (53) (54) (55)

which defines .

Next, we adjust to minimize the dot product:

 (56)

Set to zero its derivative with respect to :
 (57)

which says that the new residual is perpendicular to the fitting function'' . Solving gives the required value of .
 (58)

A computation template'' for the method of random directions is:



iterate {

}

A nice thing about the method of random directions is that you do not need to know the adjoint operator .

In practice, random directions are rarely used. It is more common to use the gradient direction than a random direction. Notice that a vector of the size of is:

 (59)

Recall this vector can be found by taking the gradient of the size of the residuals:
 (60)

Choosing to be the gradient vector is called the method of steepest descent.''

Starting from a model (which may be zero), the following is a template of pseudocode for minimizing the residual by the steepest-descent method:



iterate {

}


Good science and engineering is finding something unexpected. Look for the unexpected both in data space and in model space. In data space, you look at the residual . In model space, you look at the residual projected there . What does it mean? It is simply , the changes you need to make to your model. It means more in later chapters, where the operator is a column vector of operators that are fighting with one another to grab the data.

 Model fitting by least squares

Next: Why steepest descent is Up: KRYLOV SUBSPACE ITERATIVE METHODS Previous: Sign convention

2014-12-01