TABLE OF CONTENTS When a traveler reaches a fork in the road, the ? 1-norm tells him to take either one way or the other, but the ? 2-norm instructs him to head off into the bushes.
John F.Claerbout and Francis Muir, 1973
Because of its simplicity, the least-squares criterion ( ? 2-norm criterion) is widely used for the resolution of inverse problems, even if its basic underlying hypothesis (Gaussian uncertainties) is not always satisfied. Between least-squares and general problems there is a limited class of problems that remain simple to formulate: those based on an ? p-norm (1 ? p ? ?).
As suggested in chapter 1, when outliers are suspected in a data set, long-tailed [55] probability density functions should be used to model uncertainties (see Problem 7.7). A typical long-tailed probability density is the Laplace function, i.e., the symmetric exponential function exp( ? x). It has the advantage of leading to results intimately related to the concept of the ? 1-norm, so that relatively simple mathematics is available for solving the problem. The results obtained using the minimum ? 1-norm (least-absolute-values) criterion are known to be sufficiently insensitive to outliers (i.e., to be robust).
The ? ?-norm criterion arises when we use boxcar functions to model the probability density for uncertainties. This assumes a strict control on errors, as for instance when they are due to rounding the last digit used (see Problem 7.4).
[55]
