New insights into one-norm solvers from the Pareto curve

Geophysical example

As a concrete example of the use of the Pareto curve in the geophysical context, we study the problem of wavefield reconstruction with sparsity-promoting inversion in the curvelet domain (CRSI - Herrmann and Hennenfent, 2008). The simulated acquired data, shown in Figure 4(a), corresponds to a shot record with 35% of the traces missing. The interpolated result, shown in Figure 4(b), is obtained by solving BP$_0$ using SPG$\ell _1$ . This problem has more than half a million unknowns and forty-two thousand data points.

The points in Figure 5 are samples of the corresponding Pareto curve. The regularity of these points strongly indicates that the underlying curve--which we know to be convex--is smooth and well behaved, and empirically supports our earlier claim. However problems of practical interest are often significantly larger, and it may be prohibitively expensive to compute a similarly fine sampling of the curve.

Because the curve is well behaved, we can leverage its smoothness and use a small set of samples to obtain a good interpolation. The solid line in Figure 5 shows an interpolation based only on information from the circled samples. The interpolated curve closely matches the samples that were not included in the interpolation. The figure also plots the iterates taken by SPG$\ell _1$ in order to obtain the reconstruction shown in Figure 4(b). The plot shows that the iterates remain to the Pareto curve and that they convergence towards the BP$_0$ solution.

data,interp
Figure 4. CRSI on synthetic data. (a) Input and (b) interpolated data using CRSI with SPG$\ell _1$ .

res
Figure 5. Pareto curve and SPG$\ell _1$ solution path for a CRSI problem. The symbols + represent a fine, accurate sampling of the Pareto curve. The solid (--) line is an approximation to the Pareto curve using the few, circled points, the chain (- $\cdot$ -) line the solution path of SPG$\ell _1$ .

New insights into one-norm solvers from the Pareto curve