×

Robust inversion, dimensionality reduction, and randomized sampling. (English) Zbl 1254.90112

Summary: We consider a class of inverse problems in which the forward model is the solution operator to linear ODEs or PDEs. This class admits several dimensionality-reduction techniques based on data averaging or sampling, which are especially useful for large-scale problems. We survey these approaches and their connection to stochastic optimization. The data-averaging approach is only viable, however, for a least-squares misfit, which is sensitive to outliers in the data and artifacts unexplained by the forward model. This motivates us to propose a robust formulation based on the Student’s t-distribution of the error. We demonstrate how the corresponding penalty function, together with the sampling approach, can obtain good results for a large-scale seismic inverse problem with 50 % corrupted data.

MSC:

90C06 Large-scale problems in mathematical programming
49N45 Inverse problems in optimal control
90C15 Stochastic programming

Software:

SDaA
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aravkin, A.: Robust methods with applications to Kalman smoothing and Bundle adjustment. PhD thesis, University of Washington, Seattle (2010)
[2] Aravkin, A., van Leeuwen, T., Friedlander, M.P.: Robust inversion via semistochastic dimensionality reduction. In: Proceedings of ICASSP, IEEE (2012) · Zbl 1254.90112
[3] Aravkin, A., van Leeuwen, T., Herrmann, F.: Robust full waveform inversion with students t-distribution. In: Proceedings of the SEG, Society for Exploration Geophysics, San Antonio, Texas (2011)
[4] Avron H., Toledo S.: Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix. J. ACM 58, 8–1834 (2011) · Zbl 1327.68331
[5] Bertsekas D., Tsitsiklis J.: Neuro-dynamic Programming. Athena Scientific, Belmont (1996) · Zbl 0924.68163
[6] Bertsekas D.P., Tsitsiklis J.N.: Gradient convergence in gradient methods with errors. SIAM J. Optim. 10, 627–642 (2000) · Zbl 1049.90130 · doi:10.1137/S1052623497331063
[7] Brossier R., Operto S., Virieux J.: Which data residual norm for robust elastic frequency-domain full waveform inversion?. Geophysics 75, R37–R46 (2010) · doi:10.1190/1.3379323
[8] Bube K.P., Langan R.T.: Hybrid 1/ 2 minimization with applications to tomography. Geophysics 62, 1183–1195 (1997) · doi:10.1190/1.1444219
[9] Bube K.P., Nemeth T.: Fast line searches for the robust solution of linear systems in the hybrid 1/ 2 and huber norms. Geophysics 72, A13–A17 (2007) · doi:10.1190/1.2431639
[10] Byrd R.H., Chin G.M., Neveitt W., Nocedal J.: On the use of stochastic hessian information in optimization methods for machine learning. SIAM J. Optim. 21, 977–995 (2011) · Zbl 1245.65062 · doi:10.1137/10079923X
[11] Cochran W.G.: Sampling Techniques. 3rd edn. Wiley, New York (1977) · Zbl 0353.62011
[12] Fahrmeir L., Kunstler R.: Penalized likelihood smoothing in robust state space models. Metrika 49, 173–191 (1998) · Zbl 1093.62572 · doi:10.1007/s001840050007
[13] Farquharson C.G., Oldenburg D.W.: Non-linear inversion using general measures of data misfit and model structure. Geophys. J. Intern. 134, 213–227 (1998) · doi:10.1046/j.1365-246x.1998.00555.x
[14] Friedlander, M.P., Schmidt, M.: Hybrid deterministic-stochastic methods for data fitting. Technical report, University of British Columbia, April 2011, revised September 2011 (2011) · Zbl 1262.90090
[15] Golub G.H., von Matt U.: Quadratically constrained least squares and quadratic problems. Numer. Math. 59, 561–580 (1991) · Zbl 0745.65029 · doi:10.1007/BF01385796
[16] Guitton A., Symes W.W.: Robust inversion of seismic data using the huber norm. Geophysics 68, 1310–1319 (2003) · doi:10.1190/1.1598124
[17] Haber, E., Chung, M., Herrmann, F.J.: An effective method for parameter estimation with pde constraints with multiple right hand sides. Technical report TR-2010-4, UBC-Earth and Ocean Sciences Department. SIAM J. Optim. (2010, to appear) · Zbl 1253.35220
[18] Hampel, F.R., Ronchetti, E.M., Rousseeuw, P.J., Stahel, W.A.: Robust Statistics: The Approach Based on Influence Functions. Wiley (1986) · Zbl 0593.62027
[19] Herrmann, F., Friedlander, M.P., Yılmaz, O.: Fighting the curse of dimensionality: compressive sensing in exploration seismology. IEEE Signal Proc. Magazine 29(3), 88–100 (2012)
[20] Huber P.J.: Robust Statistics. Wiley, New York (1981) · Zbl 0536.62025
[21] Huber P.J., Ronchetti E.M.: Robust Statistics. 2nd edn. Wiley, New York (2009) · Zbl 1276.62022
[22] Hutchinson M.: A stochastic estimator of the trace of the influence matrix for laplacian smoothing splines. Commun. Stat. Simul. Computation 19, 433–450 (1990) · Zbl 0718.62058 · doi:10.1080/03610919008812866
[23] Kaczmarz S.: Angenäherte auflösung von systemen linearer gleichungen. Bull. Int. Acad. Polon. Sci. A 355, 357 (1937) · Zbl 0017.31703
[24] Krebs J.R., Anderson J.E., Hinkley D., Neelamani R., Lee S., Baumstein A., Lacasse M.-D.: Fast full-wavefield seismic inversion using encoded sources. Geophysics 74, WCC177–WCC188 (2009) · doi:10.1190/1.3230502
[25] Lange K.L., Little K.L., Taylor J.M.G.: Robust statistical modeling using the t distribution. J. Am. Stat. Assoc. 84, 881–896 (1989)
[26] Lohr S.L.: Sampling: Design and Analysis. Duxbury Press, Pacific Grove (1999) · Zbl 0967.62005
[27] Maronna, R.A., Martin, D., Yohai: Robust Statistics. Wiley, New York (2006)
[28] Nedic, A., Bertsekas, D.: Convergence rate of incremental subgradient algorithms. In: Uryasev, S., Pardalos, P.M. (eds.) Stochastic optimization: algorithms and applications, pp. 263–304. Kluwer Academic Publishers, Dordrecht (2000)
[29] Nemirovski, A.: Efficient methods in convex programming, Lecture notes (1994) · Zbl 0820.68058
[30] Nemirovski A., Juditsky A., Lan G., Shapiro A.: Robust stochastic approximation approach to stochastic programming. SIAM J. Optim. 19, 1574–1609 (2009) · Zbl 1189.90109 · doi:10.1137/070704277
[31] Nocedal J., Wright S.J.: Numerical Optimization. Springer, Berlin (1999) · Zbl 0930.65067
[32] Pratt R., Worthington M.: Inverse theory applied to multi-source cross-hole tomography. Part I: acoustic wave-equation method. Geophys. Prospect. 38, 287–310 (1990) · doi:10.1111/j.1365-2478.1990.tb01846.x
[33] Prékopa A.: Logarithmic concave measures with application to stochastic programming. Acta Sci. Math. (Szeged) 32, 301–316 (1971) · Zbl 0235.90044
[34] Rockafellar R.T.: Convex Analysis. Priceton Landmarks in Mathematics. Princeton University Press, Princeton (1970)
[35] Shevlyakov G., Morgenthaler S., Shurygin A.: Redescending m-estimators. J. Stat. Plan. Inference 138, 2906–2917 (2008) · Zbl 1213.62036 · doi:10.1016/j.jspi.2007.11.008
[36] Solodov M.: Incremental gradient algorithms with stepsizes bounded away from zero. Comput. Optim. Appl. 11, 23–35 (1998) · Zbl 0915.65061 · doi:10.1023/A:1018366000512
[37] Strohmer T., Vershynin R.: A randomized Kaczmarz algorithm with exponential convergence. J. Fourier Anal. Appl. 15, 262–278 (2009) · Zbl 1169.68052 · doi:10.1007/s00041-008-9030-4
[38] Tarantola A.: Inversion of seismic reflection data in the acoustic approximation. Geophysics 49, 1259–1266 (1984) · doi:10.1190/1.1441754
[39] Tseng P.: An incremental gradient(-projection) method with momentum term and adaptive stepsize rule. SIAM J. Optim. 8, 506–531 (1998) · Zbl 0922.90131 · doi:10.1137/S1052623495294797
[40] van den Doel, K., Ascher, U.M.: Adaptive and stochastic algorithms for electrical impedance tomography and dc resistivity problems with piecewise constant solutions and many measurements. SIAM J. Sci. Comput. 34, A185–A205 (2012) · Zbl 1241.65095
[41] van Leeuwen, T., Aravkin, A., Herrmann, F.: Seismic waveform inversion by stochastic optimization. Int. J. Geophys. (2011), (p. ID 689041)
[42] Virieux J., Operto S.: An overview of full-waveform inversion in exploration geophysics. Geophysics 74, 127–152 (2009) · doi:10.1190/1.3238367
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.