Alternatives to conjugate direction optimization for sparse solutions to geophysical problems

Results

The linear programming formulation was among our most robust techniques for estimating and tracking water-level drift in our synthetic 1-D Sea of Galilee. Below are results plotted from a sample experiment. In this case, every single data point was corrupted by a water-level drift of unknown magnitude, and water-level was allowed to vary at any time during synthetic data collection. After ten sweeps, the linear programming solver is able to nearly perfectly reconstruct the drift profile and correctly estimates the true lake depth profile (except for minor artifacts).

This problem is an example of an underconstrained inversion problem. The source data is corrupted by an unknown data drift error function, which we seek to estimate based on our approximation that it should be defined by a sparse derivative. This model approximates a boat that is sampling lake-depth while floating on an unknown water level, illustrated in Figure 1. The problem is under-constrained, because we do not know the nature of the drift function; but by assuming that its derivative is sparse, an $L_1$ or linear programming optimization problem is set up. In Figure 2, the result of the linear programming drift estimation is shown.

I conclude that linear programming yields a fairly deterministic result, even in the case of an underconstrained inversion problem. The method is stable and straightforward. The most serious drawback is that most implementations of the Simplex Algorithm require an explicit definition of the forward operator (in matrix form) - so for very large geophysical problems, this can severely limit its applicability.

lprog-data
Figure 1. The input data for the linear programming Galilee estimation. [CR]

lprog-estimated-drift
Figure 2. The estimated lake drift. [CR]

lprog-estimated-depth
Figure 3. The estimated lake depth. [CR]

Alternatives to conjugate direction optimization for sparse solutions to geophysical problems