Alternatives to conjugate direction optimization for sparse solutions to geophysical problems

Introduction

Part of our objective in this summer's study of the $L_1$ optimization criteria was motivated by new theoretical ideas for the conjugate direction solver (Claerbout, 2009), and its corresponding implementation (Maysami and Moussa, 2009). In addition to this new technique, we also extensively investigated the basic theory of convex optimization, motivated by our ultimate desire to find the most generally applicable toolkit for geophysical inversion on sparse or ``blocky'' models. Optimization theory has been subject to much research at Stanford across many fields. Prior art that is directly applicable to $L_1$ minimization spans the departments of Geophysics (Claerbout, 2008; Guitton, 2000), Computer Science (Golub and Van Loan, 1996), Operations Research, Management Science & Engineering (Paige and Saunders, 1982), and Electrical Engineering (Boyd and Vandenberghe, 2009). The enormous wealth of prior research across so many different disciplines has produced numerous algorithms and mathematical techniques which superficially bear no resemblence to each other - but all share the same final goal, which is the minimization of a generalized convex objective function. For the case of conventional geophysical inversion, this objective is some measure of the error between modeled- and recorded- data.

This broad-based investigation brought attention to techniques, such as linear programming, which are well-developed and widely used in other fields. However, these tools were rarely utilized by SEP (and presumably in the geophysical inversion community outside Stanford). Our efforts have developed a formulation of these techniques to convert a standard form geophysical data-fitting and inversion problem ( ${\bf L m = d}$) into a linear programming problem.

I demonstrate in the following sections the efforts to construct a pure $L_1$ solver, and its associated numerical difficulties. Next is our foray into the realm of linear programming - a well-developed toolset that has seen little application in geophysical inversion.

Alternatives to conjugate direction optimization for sparse solutions to geophysical problems