×
Loris, I.; Douma, H.; Nolet, G.; Daubechies, I.; Regone, C.

Nonlinear regularization techniques for seismic tomography. (English) Zbl 1182.86003

J. Comput. Phys. 229, No. 3, 890-905 (2010).
Summary: 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.

Cited in 4 Documents

MSC:

86A15 Seismology (including tsunami modeling), earthquakes
86A22 Inverse problems in geophysics
42C40 Nontrigonometric harmonic analysis involving wavelets and other special systems

Keywords:

inverse problem; one-norm; sparsity; tomography; wavelets; regularization

Software:

TwIST; SPGL1; DT-CWT
PDFBibTeX XMLCite
\textit{I. Loris} et al., J. Comput. Phys. 229, No. 3, 890--905 (2010; Zbl 1182.86003)
Full Text: DOI arXiv

References:

[1] Backus, G.; Gilbert, J., Numerical applications of a formalism for geophysical inverse problems, Geophysical Journal of the Royal Astronomical Society, 13, 247-276 (1967)
[2] Backus, G.; Gilbert, J., Uniqueness on the inversion of inaccurate gross Earth data, Philosophical Transactions of the Royal Society of London, A266, 123-192 (1970)
[3] Loris, I.; Nolet, G.; Daubechies, I.; Dahlen, F. A., Tomographic inversion using \(\ell_1\)-norm regularization of wavelet coefficients, Geophysical Journal International, 170, 1, 359-370 (2007)
[4] Blumensath, T.; Davies, M., Iterative thresholding for sparse approximations, Journal of Fourier Analysis and Applications, 14, 5, 629-654 (2008) · Zbl 1175.94060
[5] Blumensath, T.; Davies, M. E., Iterative hard thresholding for compressed sensing, Applied and Computational Harmonic Analysis, 27, 3, 265-274 (2009) · Zbl 1174.94008
[6] Chevrot, S.; Zhao, L., Multiscale finite frequency Rayleigh wave tomography of the Kaapvaal craton, Geophysical Journal International, 169, 201-215 (2007)
[7] Scales, J.; Gersztenkorn, A.; Treitel, S., Fast \(\ell_p\) solutions of large sparse linear systems: application to seismic travel time tomography, Journal of Computational Physics, 75, 314-333 (1988) · Zbl 0637.65035
[8] Nolet, G., Seismic wave propagation and seismic tomography, (Nolet, G., Seismic Tomography (1987), Reidel: Reidel Dordrecht), 1-23
[9] Taylor, H. L.; Banks, S. C.; McCoy, J. F., Deconvolution with the \(\ell_1\) norm, Geophysics, 44, 39-52 (1979)
[10] Oldenburg, D.; Scheuer, T.; Levy, S., Recovery of the acoustic impedance from reflection seismograms, Geophysics, 48, 1318-1337 (1983)
[11] Santosa, F.; Symes, W. W., Linear inversion of band-limited reflection seismograms, SIAM Journal on Scientific and Statistical Computing, 7, 1307-1330 (1986) · Zbl 0602.73113
[12] Sacchi, M. D.; Ulrych, T. J.; Walker, C., Interpolation and extrapolation using a high-resolution discrete Fourier transform, IEEE Transactions on Signal Processing, 46, 31-38 (1998)
[13] Candès, E. J.; Romberg, J. K.; Tao, T., Stable signal recovery from incomplete and inaccurate measurements, Communications on Pure and Applied Mathematics, 59, 8, 1207-1223 (2006) · Zbl 1098.94009
[14] Donoho, D., Compressed sensing, IEEE Transactions on Information Theory, 52, 4, 1289-1306 (2006) · Zbl 1288.94016
[15] Donoho, D. L., For most large underdetermined systems of linear equations the minimal \(\ell_1\)-norm solution is also the sparsest solution, Communications on Pure and Applied Mathematics, 59, 797-829 (2006) · Zbl 1113.15004
[16] Herrmann, F. J.; Hennenfent, G., Non-parametric seismic data recovery with curvelet frames, Geophysical Journal International, 173, 1, 233-248 (2008)
[17] Hennenfent, G.; van den Berg, E.; Friedlander, M. P.; Herrmann, F. J., New insights into one-norm solvers from the Pareto curve, Geophysics, 73, 4, A23-A26 (2008)
[18] van den Berg, E.; Friedlander, M. P., Probing the Pareto frontier for basis pursuit solutions, SIAM Journal on Scientific Computing, 31, 2, 890-912 (2008) · Zbl 1193.49033
[19] Favier, N.; Chevrot, S., Sensitivity kernels for shear wave splitting in transverse isotropic media, Geophysical Journal International, 153, 213-228 (2003)
[20] Nolet, G., A Breviary of Seismic Tomography (2008), Cambridge University Press · Zbl 1166.86001
[21] Dahlen, F. A., Resolution limit of traveltime tomography, Geophysical Journal International, 157, 1, 315-331 (2004)
[22] Tikhonov, A., Solution of incorrectly formulated problems and the regularization method, Soviet Mathematics - Doklady, 4, 1035-1038 (1963) · Zbl 0141.11001
[23] Daubechies, I.; Defrise, M.; De Mol, C., An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Communications on Pure and Applied Mathematics, 57, 11, 1413-1457 (2004) · Zbl 1077.65055
[24] I. Daubechies, Ten Lectures on Wavelets, Society for Industrial and Applied Mathematics, 1992.; I. Daubechies, Ten Lectures on Wavelets, Society for Industrial and Applied Mathematics, 1992. · Zbl 0776.42018
[25] Beck, A.; Teboulle, M., A fast iterative shrinkage-threshold algorithm for linear inverse problems, SIAM Journal on Imaging Sciences, 2, 183-202 (2009) · Zbl 1175.94009
[26] Nesterov, Y. E., A method for solving the convex programming problem with convergence rate \(O(1 / k^2)\), Doklady Academii Nauk SSSR, 269, 543-547 (1983), (in Russian)
[27] Nesterov, Y. E., A method for solving a convex programming problem with convergence rate \(O(1 / k^2)\), Soviet Mathematics - Doklady, 27, 372-376 (1983) · Zbl 0535.90071
[28] Nesterov, Y., Introductory Lectures on Convex Optimization (2004), Kluwer Academic Publishers · Zbl 1086.90045
[29] Oliveira, J.; Bioucas-Dias, J.; Figueiredo, M., Adaptive total variation image deblurring: a majorization-minimization approach, Signal Processing, 89, 9, 1683-1693 (2009) · Zbl 1178.94029
[30] Bect, J.; Blanc-Féraud, L.; Aubert, G.; Chambolle, A., A \(\ell^1\)-unified variational framework for image restoration, (Pajdla, T.; Matas, J., Proceedings of the Eighth European Conference on Computer Vision, vol. IV (2004), Springer Verlag), 1-13 · Zbl 1098.68728
[31] Bioucas-Dias, J.; Figueiredo, M., A new TwIST: two-step iterative shrinkage/thresholding algorithms for image restoration, IEEE Transactions on Image processing, 16, 2980-2991 (2007)
[32] Haar, A., Zur Theorie der orthogonalen Funktionensysteme, Mathematische Annalen, 69, 331-371 (1910) · JFM 41.0469.03
[33] Cohen, A.; Daubechies, I.; Jawerth, B.; Vial, P., Multiresolution analysis, wavelets and fast algorithms on the interval, Comptes Rendus de l’Académie des Sciences Paris, 316, 417-421 (1992) · Zbl 0768.42015
[34] Cohen, A.; Daubechies, I.; Vial, P., Wavelets on the interval and fast wavelet transforms, Journal for Applied and Computational Harmonic Analysis, 1, 54-81 (1993) · Zbl 0795.42018
[35] Kingsbury, N., Image processing with complex wavelets, Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 357, 1760, 2543-2560 (1999) · Zbl 0976.68527
[36] Kingsbury, N., Complex wavelets for shift invariant analysis and filtering of signals, Applied and Computational Harmonic Analysis, 10, 234-253 (2001) · Zbl 0990.94005
[37] D. Labate, W. Lim, G. Kutyniok, G. Weiss, Sparse multidimensional representation using shearlets, in: SPIE Proc. 5914, SPIE, Bellingham, WA, 2005, pp. 254-262, Wavelets XI (San Diego, CA, 2005).; D. Labate, W. Lim, G. Kutyniok, G. Weiss, Sparse multidimensional representation using shearlets, in: SPIE Proc. 5914, SPIE, Bellingham, WA, 2005, pp. 254-262, Wavelets XI (San Diego, CA, 2005).
[38] Kutyniok, G.; Labate, D., Construction of regular and irregular shearlets, Journal of Wavelet Theory and Applications, 1, 1-10 (2007)
[39] Candes, E. J.; Demanet, L.; Ying, D. L.D. L., Fast discrete curvelet transforms, SIAM Multiscale Modeling and Simulation, 5, 3, 861-899 (2006) · Zbl 1122.65134
[40] M.A.T. Figueiredo, R.D. Nowak, S.J. Wright, Gradient projection for sparse reconstruction: application to compressed sensing and other inverse problems, IEEE Journal of Selected Topics in Signal Processing (Special Issue on Convex Optimization Methods for Signal Processing) 1 (2007) 586-598. doi:10.1109/JSTSP.2007.910281.; M.A.T. Figueiredo, R.D. Nowak, S.J. Wright, Gradient projection for sparse reconstruction: application to compressed sensing and other inverse problems, IEEE Journal of Selected Topics in Signal Processing (Special Issue on Convex Optimization Methods for Signal Processing) 1 (2007) 586-598. doi:10.1109/JSTSP.2007.910281.
[41] Elad, M.; Matalon, B.; Zibulevsky, M., Coordinate and subspace optimization methods for linear least squares with non-quadratic regularization, Applied and Computational Harmonic Analysis, 23, 3, 346-367 (2007) · Zbl 1133.65022
[42] Kim, S.-J.; Koh, K.; Lustig, M.; Boyd, S.; Gorinevsky, D., An interior-point method for large-scale \(\ell_1\)-regularized least squares, IEEE Journal of Selected Topics in Signal Processing, 1, 4, 606-617 (2007)
[43] Hale, E.; Yin, W.; Zhang, Y., Fixed-point continuation for \(\ell_1\)-minimization: methodology and convergence, Siam Journal on Optimization, 19, 3, 1107-1130 (2008) · Zbl 1180.65076
[44] Yin, W.; Osher, S.; Goldfarb, D.; Darbon, J., Bregman iterative algorithms for \(\ell_1\)-minimization with applications to compressed sensing, SIAM Journal on Imaging Sciences, 1, 1, 143-168 (2008) · Zbl 1203.90153
[45] Loris, I., On the performance of algorithms for the minimization of \(\ell_1\)-penalized functionals, Inverse Problems, 25, 035008 (2009) · Zbl 1162.65333
[46] Defrise, M.; De Mol, C., A note on stopping rules for iterative regularization methods and filtered SVD, (Sabatier, P. C., Inverse Problems: An interdisciplinary Study (1987), Academic Press), 261-268
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.