Skip to main content
SpringerLink
Log in

A GCV based method for nonlinear ill-posed problems

  • Published:
Computational Geosciences Aims and scope Submit manuscript

Abstract

This paper discusses the inversion of nonlinear ill-posed problems. Such problems are solved through regularization and iteration and a major computational problem arises because the regularization parameter is not known a priori. In this paper we show that the regularization should be made up of two parts. A global regularization parameter is required to deal with the measurement noise, and a local regularization is needed to deal with the nonlinearity. We suggest the generalized cross validation (GCV) as a method to estimate the global regularization parameter and the damped Gauss-Newton to impose local regularization. Our algorithm is tested on the magnetotelluric problem.

In the second part of this paper we develop a methodology to implement our algorithm on large-scale problems. We show that hybrid regularization methods can successfully estimate the global regularization parameter. Our algorithm is tested on a large gravimetric problem.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. J. Altman, Smoothing data with correlated errors, Technical Report 280, Department of Statistics, Stanford University (1987).

  2. L. Armijo, Minimization of a function having Lipschitz-continuous first partial derivatives, Pacific J. Math. 16 (1966) 1-3.

    MATH  MathSciNet  Google Scholar 

  3. A. Bakushinsky and A. Goncharsky, Ill-Posed Problems: Theory and Applications (Kluwer Academic, 1994).

  4. P.N. Brown and Y. Saad, Hybrid Krylov methods for nonlinear systems of equations, SIAM J. Sci. Statist. Comput. 11 (1990) 450-481.

    Article  MATH  MathSciNet  Google Scholar 

  5. S.C. Constable, R.L. Parker and C.G. Constable, Occam's inversion: A practical algorithm for generating smooth models from electromagnetic sounding data, Geophysics 52 (1987) 289-300.

    Article  Google Scholar 

  6. R.S. Dembo, S.C. Eisenstat and T. Steihaug, Inexact Newton methods, SIAM J. Numer. Anal. 19 (1982) 400-408.

    Article  MATH  MathSciNet  Google Scholar 

  7. R.S. Dembo and T. Steihaug, Inexact Newton algorithms for large scale optimization, Math. Programming 26 (1983) 190-212.

    MATH  MathSciNet  Google Scholar 

  8. J.E. Dennis and R.B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations (SIAM, Philadelphia, PA, 1996).

    MATH  Google Scholar 

  9. L. Elden, Algorithms for the regularization of ill-conditioned least squares problems, BIT 17 (1977) 134-145.

  10. L. Elden, A weighted pseudo-inverse, generalized singular values, and constrained least squares problems, BIT 22 (1982) 487-502.

    Article  MATH  MathSciNet  Google Scholar 

  11. L. Elden, Algorithms for the computation of functions defined on the solution of a discrete ill-posed problem, BIT 30 (1990) 466-483.

    Article  MATH  MathSciNet  Google Scholar 

  12. H.W. Engl, M. Hanke and A. Neubaur, Regularization of Inverse Problems (Kluwer Academic, Dordrecht, 1996).

    MATH  Google Scholar 

  13. C.G. Farquharson and D.W. Oldenburg, Inversion of time domain electromagnetic data for a horizontally layered Earth, Geophys. J. Int. 114 (1993) 433-442.

    Google Scholar 

  14. P.E. Gill, W. Murray and M.H. Wright, Practical Optimization (Academic Press, New York, 1981).

    MATH  Google Scholar 

  15. G.H. Golub, M. Heath and G. Whaba, Generalized cross-validation as a method for choosing a good ridge parameter, Technometrics 21 (1979) 215-223.

    Article  MATH  MathSciNet  Google Scholar 

  16. G.H. Golub and C.F. Van Loan, Matrix Computations, 2nd ed. (The Johns Hopkins University Press, Baltimore, MD, 1989).

    MATH  Google Scholar 

  17. G.H. Golub and U. Von Matt, Quadratically constrained least squares and quadratic problems, Numer. Math. 59 (1991) 561-580.

    Article  MATH  MathSciNet  Google Scholar 

  18. G.H. Golub and U. VonMatt, Generalized cross-validation for large scale problems (1997), to appear.

  19. E. Haber, Numerical Strategies for the solution of inverse problems, Ph.D. thesis, The University of British Columbia (1997).

  20. M. Hanke, Regularization with differential operators: An iterative approach, Numer. Funct. Anal. Optim. 13 (1992) 523-540.

    MATH  MathSciNet  Google Scholar 

  21. M. Hanke and P.C. Hansen, Regularization methods for large scale problems, Surveys Math. Indust. 3 (1993) 253-315.

    MATH  MathSciNet  Google Scholar 

  22. P.C. Hansen, Rank deficient and ill-posed problems, Ph.D. thesis, Technical University of Denmark (1995).

  23. C.T. Kelley, Iterative Methods for Linear and Nonlinear Equations (SIAM, Philadelphia, PA, 1995).

    MATH  Google Scholar 

  24. O. Knoth, A globalization scheme for the generalized Gauss-Newton method, Numer. Math. 56(2) (1996) 591-603.

    MathSciNet  Google Scholar 

  25. D.G. Luenberger, Optimization by Vector Space Methods (Wiley, New York, 1969).

    MATH  Google Scholar 

  26. W. Menke, Geophysical Data Analysis: Discrete Inverse Theory (Academic Press, Orlando, 1984).

    Google Scholar 

  27. D.W. Oldenburg, One-dimensional inversion of natural source magnetotelluric measurements, Geophysics 44 (1979) 1218-1244.

    Article  Google Scholar 

  28. D.W. Oldenburg, P.R. McGillvary and R.G. Ellis, Generalized subspace methods for large scale inverse problems, Geophys. J. Int. 114 (1993) 12-20.

    Google Scholar 

  29. D.W. Oldenburg and Y. Li, Subspace linear inverse method, Inverse Problems 10 (1994) 915-935.

    Article  MATH  Google Scholar 

  30. D.P. O'Leary and J.A. Simmons, A bidiagonalization-regularization procedure for large scale regularization of ill-posed problems, SIAM J. Sci. Statist. Comput. 2 (1981) 474-489.

    Article  MATH  MathSciNet  Google Scholar 

  31. R.L. Parker, Geophysical Inverse Theory (Princeton University Press, Princeton, NJ, 1994).

    MATH  Google Scholar 

  32. B.N. Parlet, The Symmetric Eigenvalue Problem (Prentice-Hall, Englewood Cliffs, NJ, 1980).

    Google Scholar 

  33. Y. Saad, Iterative Methods for Sparse Linear Systems (PWS, 1996).

  34. J.A. Scales and M.L. Smith, Introductory Geophysical Inverse Theory (Samizdat, 1994).

  35. J.T. Smith and J.R. Booker, Rapid inversion of two and three dimensional magnetotelluric data, J. Geophys. Res. 96 (1991) 3905-3922.

    Article  Google Scholar 

  36. A. Tarantola and B. Valette, Generalized nonlinear inverse problems solved using the least squares criterion, Rev. Geophys. Space Phys. 20(2) (1982) 219-232.

    MathSciNet  Google Scholar 

  37. A. Tarantola, Inverse Problem Theory (Elsevier Science, Amsterdam, 1987).

    MATH  Google Scholar 

  38. A.N. Tikhonov and V.Y. Arsenin, Solutions of Ill-Posed Problems (Wiley, New York, 1977).

    MATH  Google Scholar 

  39. J.M. Varah, Pitfalls in numerical solutions of linear ill-posed problems, SIAM J. Sci. Comput. 4 (1983) 164-176.

    Article  MATH  MathSciNet  Google Scholar 

  40. G. Whaba, Practical approximate solutions to linear operator equations when the data are noisy, SIAM J. Numer Anal. 14 (1977) 651-667.

    Article  MathSciNet  Google Scholar 

  41. G. Whaba, Spline Models for Observational Data (SIAM, Philadelphia, PA, 1990).

    Google Scholar 

  42. G. Whaba and S. O'sullivan, A cross validated Bayesian retrieval algorithm for non-linear remote sensing experiments, J. Comput. Physics 59 (1985) 441-455.

    Article  Google Scholar 

  43. S.H. Ward and G.W. Hohmann, Electromagnetic theory for geophysical applications, Electromagnetic Methods Appl. Geophysics 1 (1988) 131-311.

    Google Scholar 

  44. K.P. Whittall and D.W. Oldenburg, Inversion of Magnetotelluric Data for a One Dimensional Conductivity, SEG Monograph, Vol. 5 (1992).

  45. J. Zhang, R.L. Mackie and T.R. Madden, 3-D resistivity forward modeling and inversion using conjugate gradients, Geophysics 60(5) (1995) 1313-1325.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of British Columbia, Vancouver, BC, Canada, V6T 1Z4

    Eldad Haber

  2. Department of Earth and Ocean Science, University of British Columbia, Vancouver, BC, Canada, V6T 1Z4

    Douglas Oldenburg

Authors
  1. Eldad Haber
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Douglas Oldenburg
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Haber, E., Oldenburg, D. A GCV based method for nonlinear ill-posed problems. Computational Geosciences 4, 41–63 (2000). https://doi.org/10.1023/A:1011599530422

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1011599530422

Search

Navigation