next up previous [pdf]

Next: Problem statement Up: Hennenfent et al.: Pareto Previous: Hennenfent et al.: Pareto

Introduction

Many geophysical inverse problems are ill posed (Parker, 1994)--their solutions are not unique or are acutely sensitive to changes in the data. To solve this kind of problem stably, additional information must be introduced. This technique is called regularization (see, e.g., Ti-khonov, 1963; Phil-lips, 1962).

Specifically, when the solution of an ill-posed problem is known to be (almost) sparse, Oldenburg et al. (1983) and others have observed that a good approximation to the solution can be obtained by using one-norm regularization to promote sparsity. More recently, results in information theory have breathed new life into the idea of promoting sparsity to regularize ill-posed inverse problems. These results establish that, under certain conditions, the sparsest solution of a (severely) underdetermined linear system can be exactly recovered by seeking the minimum one-norm solution (Donoho, 2006; Candès et al., 2006; Rauhut, 2007). This has led to tremendous activity in the newly established field of compressed sensing. Several new one-norm solvers have appeared in response (see, e.g., van den Berg and Friedlander, 2008; Daubechies et al., 2004, and references therein). In the context of geophysical applications, it is a challenge to evaluate and compare these solvers against more standard approaches such as iteratively reweighted least-squares (IRLS - Gersztenkorn et al., 1986), which uses a quadratic approximation to the one-norm regularization function.

In this letter, we propose an approach to understand the behavior of algorithms for solving one-norm regularized problems. The approach consists of tracking on a graph the data misfit versus the one norm of successive iterates. The Pareto curve traces the optimal tradeoff in the space spanned by these two axes and gives a rigorous yardstick for measuring the quality of the solution path generated by an algorithm. In the context of the two-norm--i.e., Tikhonov--regularization, the Pareto curve is often plotted on a log-log scale and is called the L-curve (Lawson and Hanson, 1974). We draw on the work of van den Berg and Friedlander (2008) who examine the theoretical properties of the one-norm Pareto curve. Our goal is to understand the compromises implicitly accepted when an algorithm is given a limited number of iterations.


next up previous [pdf]

Next: Problem statement Up: Hennenfent et al.: Pareto Previous: Hennenfent et al.: Pareto

2008-03-27