The effects of several nonlinear regularization techniques are discussed in the framework of 3D seismic tomography. Traditional, linear, $ell_2$ penalties are compared to so-called sparsity promoting $ell_1$ and $ell_0$ penalties, and a total variation penalty. Which of these algorithms is judged optimal depends on the specific requirements of the scientific experiment. If the correct reproduction of model amplitudes is important, classical damping towards a smooth model using an $ell_2$ norm works almost as well as minimizing the total variation but is much more efficient. If gradients (edges of anomalies) should be resolved with a minimum of distortion, we prefer $ell_1$ damping of Daubechies-4 wavelet coefficients. It has the additional advantage of yielding a noiseless reconstruction, contrary to simple $ell_2$ minimization (`Tikhonov regularization) which should be avoided. In some of our examples, the $ell_0$ method produced notable artifacts. In addition we show how nonlinear $ell_1$ methods for finding sparse models can be competitive in speed with the widely used $ell_2$ methods, certainly under noisy conditions, so that there is no need to shun $ell_1$ penalizations.
We propose a new gradient projection algorithm that compares favorably with the fastest algorithms available to date for $ell_1$-constrained sparse recovery from noisy data, both in the compressed sensing and inverse problem frameworks. The method exploits a line-search along the feasible direction and an adaptive steplength selection based on recent strategies for the alternation of the well-known Barzilai-Borwein rules. The convergence of the proposed approach is discussed and a computational study on both well-conditioned and ill-conditioned problems is carried out for performance evaluations in comparison with five other algorithms proposed in the literature.
Regularization of ill-posed linear inverse problems via $ell_1$ penalization has been proposed for cases where the solution is known to be (almost) sparse. One way to obtain the minimizer of such an $ell_1$ penalized functional is via an iterative soft-thresholding algorithm. We propose an alternative implementation to $ell_1$-constraints, using a gradient method, with projection on $ell_1$-balls. The corresponding algorithm uses again iterative soft-thresholding, now with a variable thresholding parameter. We also propose accelerat
