Method of random directions and steepest descent

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

$$\ \it\hbox{residual} \eq \ \it\hbox{data space} \ \ -\ \ \ \it\hbox{transform} \ \ \ \ \it\hbox{model space}$$ (30)

 

$$\left[ \matrix { \matrix { \cr \cr R \cr \cr \cr } } \right]... ...\ \ \ \left[ \matrix { \matrix { \cr x \cr \cr } } \right]$$ (31)

Fourier-transformed variables are often capitalized. Here we capitalize vectors transformed by the $\bold A$ matrix. A matrix such as $\bold A$ is denoted by boldface print.

A contour plot is based on an altitude function of space. The altitude is the dot product $R \cdot R$.By finding the lowest altitude we are driving the residual vector R as close as we can to zero. If the residual vector R reaches zero, then we have solved the simultaneous equations $Y= \bold A x$.In a two-dimensional world the vector x has two components, (x₁ , x₂ ). A contour is a curve of constant $R \cdot R$ in (x₁ , x₂ )-space. These contours have a statistical interpretation as contours of uncertainty in (x₁ , x₂ ), given measurement errors in Y.

Starting from $R=Y-\bold A x$, let us see how a random search direction can be used to try to reduce the residual. Let g be an abstract vector with the same number of components as the solution x, and let g contain arbitrary or random numbers. Let us add an unknown quantity $\alpha$ of vector g to vector x, thereby changing x to $x+\alpha g$.The new residual R+dR becomes

$$\begin{eqnarray} R+dR &=& Y-\bold A ( x+\alpha g) \ &=& Y-\bold A x - \alpha \bold A g \ &=& R-\alpha G\end{eqnarray}$$ (32) (33) (34)

We seek to minimize the dot product  

$$(R+dR)\cdot (R+dR) \eq (R- \alpha G) \cdot (R- \alpha G )$$ (35)

Setting to zero the derivative with respect to $\alpha$ gives

$$\alpha \eq { (R \cdot G ) \over ( G \cdot G ) }$$ (36)

Geometrically and algebraically the new residual $R_+ = R - \alpha G$ is perpendicular to the ``fitting function'' G. (We confirm this by substitution leading to $R_+ \cdot G=0.)$

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

$$g \eq \bold A' R$$ (37)

Notice also that this vector can be found by taking the gradient of the size of the residuals:

$${\partial \over \partial x' } \ R \cdot R \eq {\partial \ove... ...\ x' \, \bold A' ) \, ( Y \ -\ \bold A \, x ) \eq -\bold A' \ R$$ (38)

Descending by use of the gradient vector is called ``the method of steepest descent."