next up previous print clean
Next: Conditioning the gradient Up: ITERATIVE METHODS Previous: ITERATIVE METHODS

Method of random directions and steepest descent

Let us minimize the sum of the squares of the components of the residual vector given by
\begin{displaymath}
\ \it\hbox{residual} \eq \ \it\hbox{data space} \ \ -\ \ \ \it\hbox{transform} \ \ \ \ \it\hbox{model space}\end{displaymath} (30)
 
 \begin{displaymath}
\left[
\matrix { \matrix { \cr \cr R \cr \cr \cr } }
\right]...
 ...\ \ \ 
\left[
 \matrix {
 \matrix { \cr x \cr \cr }
 }
 \right]\end{displaymath} (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, (x1 , x2 ). A contour is a curve of constant $R \cdot R$ in (x1 , x2 )-space. These contours have a statistical interpretation as contours of uncertainty in (x1 , x2 ), 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  
 \begin{displaymath}
(R+dR)\cdot (R+dR) \eq
(R- \alpha G) \cdot (R- \alpha G )\end{displaymath} (35)
Setting to zero the derivative with respect to $\alpha$ gives
\begin{displaymath}
\alpha \eq { (R \cdot G ) \over ( G \cdot G ) }\end{displaymath} (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
\begin{displaymath}
g \eq \bold A' R\end{displaymath} (37)
Notice also that this vector can be found by taking the gradient of the size of the residuals:
\begin{displaymath}
{\partial \over \partial x' } \ R \cdot R
\eq
{\partial \ove...
 ...\ x' \, \bold A' ) \,
( Y \ -\ \bold A \, x )
\eq
-\bold A' \ R\end{displaymath} (38)
Descending by use of the gradient vector is called ``the method of steepest descent."


next up previous print clean
Next: Conditioning the gradient Up: ITERATIVE METHODS Previous: ITERATIVE METHODS
Stanford Exploration Project
10/21/1998