Generalized-norm conjugate direction solver

Introduction

Strict $L_1$ norm optimization has numerous applications in geophysical inversion problems. Examples include solving for sparse functions, such as those that describe blocky, layered geology. However, we find that approximations to $L_1$, or modified $L_1/L_2$ systems, are more computationally feasible than pure $L_1$ solutions. These non-strict $L_1/L_2$ norms - the Huber (Huber, 1973; Guitton, 2000) and Hybrid norms - still satisfy our desire to find sparse-functions, and are suitable for most of our geophysical needs.

For many years, SEP has relied on a single incarnation of the conjugate-direction descent solver. This code is based on work by Claerbout (2008). For some time in the 1990s, SEP also used a competing least squares approach, LSQR, developed by Paige and Saunders (1982). Because numerical optimization is such an embedded part of many geophysical algorithms, it is extremely desirable to have a backward-compatible program framework that can continue to work within these decades-old codes. For this reason, we chose to implement our solver with the same interface as the conjugate-direction $L_2$ solver (Claerbout, 2008). Our new solver implements a generalized definition of the norm used for minimization.

It should be noted that the term ``norm'' is used for convenience; whereas in fact, some of the numeric measures under consideration do not strictly satisfy the necessary mathematical criteria to be a proper norm. Notably, the Huber and Hybrid norms exhibit non-linearity with regard to a scalar multiplication (Bube and Langan, 1997). We will use this terminology for simplicity, but the cautious reader should note that these functions do not satisfy all necessary properties of a norm.

We considered many solver options in our original quest for a numeric solution to the strict $L_1$ optimization problem. We investigated a weighted-median algorithm to descend to the $L_1$-sense minimum. Early development showed that, despite the theoretical promise of the weighted-median methodology, it did not suitably achieve the desired solution on non-trivial test problems. This work led to development of a new solver, discussed below, based on theory developed in Claerbout (2009). This solver is based on a generalized plane-search using Taylor series expansion of the norm.

In this paper, we will describe our implementation of this solver framework. It is based on SEP's conjugate-direction $L_2$ solver, but it also allows us to substitute different norms, including $L_1$ and our non-strict $L_1/L_2$ norms. First we will review the available norms which can be used as the optimization criteria. Then we will discuss the mechanics of our new solver framework and describe a technique for iterative plane-search, potentially enabling faster convergence for certain classes of problems. Finally, we will reference applications which are described in other SEP reports (Li and Maysami, 2009; Wong et al., 2009).

Generalized-norm conjugate direction solver