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 .$$ (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 .$$ (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)} .$$ (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) .$$

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 L²-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 } (\bol... ...old m -\bold d)^T(\bold L\bold m -\bold d) = \bold L^T\bold r .$$ (4)

 

• Iteratively Reweighted Least Squares (IRLS)