Geophysical applications of a novel and robust L1 solver |

The hybrid norm is defined as

where is the residual, and is the corresponding threshold. In the limit, the hybrid norm (1) becomes:

It is obvious that when is small, the hybrid norm (1) reduces to L1 norm; when is big, it becomes the L2 norm. Therefore, threshold behaves as the turning point where the objective function changes smoothly from L2 to L1.

The Conjugate Direction method is commonly used for solving immense linear regressions in exploration geophysics. The idea of the CD method is to search the plane determined by the gradient and the previous step for the best step direction and length, instead of moving along the gradient direction. The best direction in that plane is the linear combination of the gradient and previous step vector that decreases the measure of the residual the most. Traditionally, the measure is chosen to be L2, for its simplicity; however, we generalize the CD method for any arbitrary convex measure . Readers can determine which measure to use to satisfy their own objectives.

Now let us examine the generalization of the CD method in detail. At each iteration, we have the residual vector , the gradient and the previous step . Therefore, the updated residual can be written as:

(3) |

where and are scalars controlling the relative weights of these two directions. To determine these two scaling parameters, we need to minimize the measure of the residual:

The system given by directly setting the partial derivatives of (4) to zero is transcendental, thus difficult to solve. Therefore, we use Taylor's expansion to approximate the original objective function. The polynomial estimation of (4) is given as follows:

Now, taking the derivatives of the parabolic function in (5) with respect to and and setting them to zero, we end up with a linear system of and :

(6) |

where refer to a Taylor expansion of about .

Then we can obtain
by simply solving a set of *2
2* linear equations.

Notice that the we get here is minimizing the approximated function (5), not the original objective function. Therefore, it is necessary to solve for multiple times within each CD iteration. By doing this relatively cheap plane-search loop, we expect to save the number of iterations for the outer loop (Conjugate Direction), which is usually much more computational intensive (requiring application of both the forward and adjoint operator).

Geophysical applications of a novel and robust L1 solver |

2010-05-19