New insights into one-norm solvers from the Pareto curve

Practical considerations

In geophysical applications, problem sizes are large and there is a severe computational constraint. We can use the technique outlined above to understand the robustness of a given solver that is limited by a maximum number of iterations or matrix-vector products that can be performed.

Figure 3 shows the Pareto curve and the solution paths of the various solvers where the maximum number of iterations is fixed. This roughly equates to using the same number of matrix-vector products for each solver. Whereas SPG$\ell _1$ continues to provide a fairly accurate approximation to the BP$_0$ solution, those computed by IST, ISTc, and IRLS suffer from larger errors. IST stops before the effect of the one-norm regularization kicks in; hence the data misfit at the candidate solution is small but the one norm is completely incorrect. ISTc and IRLS accumulate small errors along their paths because there are not enough iterations to solve each subproblem to sufficient accuracy. Note that both solvers accumulate errors along both axes.

plotLim
Figure 3. Pareto curve and optimization paths (same, limited number of iterations) of four solvers for a BP$_0$ problem (see Figure 2 for legend).

New insights into one-norm solvers from the Pareto curve