next up previous print clean
Next: Iteratively Reweighted Least Squares Up: Ji: Conjugate Guided Gradient Previous: Ji: Conjugate Guided Gradient

CG method for LS and IRLS Inversion

Most inversion problems start by formulating the forward problem, which describes the forward operator, $\bold L$, that transforms the model vector $\bold m$ to the data vector $\bold d$ :

\bold d = \bold L \bold m .\end{displaymath} (1)
In general, the measured data $\bold d$ may be inexact, and the forward operator $\bold L$ may be ill-conditioned. In that case, instead of solving the above equation directly, different approaches are used to find an optimum solution $\bold m$ for a given data $\bold d$.The most popular method is finding a solution that minimizes the misfit between the data $\bold d$ and the modeled data $\bold L\bold m$.The misfit, or the residual vector, $\bold r$, is described as follows:

\bold r = \bold L\bold m - \bold d .\end{displaymath} (2)
In least-squares inversion, the solution $\bold m$ is the one that minimizes the squares of the residual vector as follows:

min_m (\bold r \cdot \bold r) = min_m{(\bold L\bold m - \bold d)^T(\bold L\bold m - \bold d)} .\end{displaymath} (3)

Iterative solvers for the LS problem search the solution space for a better solution in each iteration step, along the gradient direction (in steepest-descent algorithms), or on the plane made by the current gradient vector and the previous descent-step vector (in conjugate-gradient algorithms). Following Claerbout 1992, a conjugate-gradient algorithm for the LS solution can be summarized as follows:

		 		 $\bold r \quad\longleftarrow\quad\bold L \bold m - \bold d$ 
		 iterate { 
		 		  $\Delta\bold m \quad\longleftarrow\quad\bold L^T\ \bold r$ 
		 		  $\Delta\bold r\ \quad\longleftarrow\quad\bold L \ \Delta \bold m$ 
		 		  $(\bold m,\bold r) \quad\longleftarrow\quad{\rm cgstep}
 (\bold m,\bold r, \Delta\bold m,\Delta\bold r )$ 
		 		 } , 
where the subroutine cgstep() remembers the previous iteration descent vector, $\Delta \bold s = \bold m_i - \bold m_{i-1}$, where i is the iteration step, and determines the step size by minimizing the quadrature function composed from $\Delta \bold r$ (the conjugate gradient) and $\Delta \bold s$ (the previous iteration descent vector), as follows Claerbout (1992):

Q(\alpha,\beta) = (\bold r-\alpha \Delta \bold r -\beta \Del...
 ...d s)^T
 (\bold r-\alpha \Delta \bold r -\beta \Delta \bold s) .\end{displaymath}

Notice that the gradient vector ($\Delta \bold m$) in the CG method for LS solution is the gradient of the squared residual and is determined by taking the derivative of the squared residual (i.e. the L2-norm of the residual, $\bold r \cdot \bold r$, with respect to the model $\bold m^T$):

\Delta \bold m = 
{\partial \over \partial \bold m^T }
 ...old m -\bold d)^T(\bold L\bold m -\bold d)
= \bold L^T\bold r .\end{displaymath} (4)