×

Regularization tools: A Matlab package for analysis and solution of discrete ill-posed problems. (English) Zbl 0789.65029

The underlying theory on regularization methods for analysis and solution of discrete ill-posed problems is dealt with and an overview of the package of 54 Matlab routines for this analysis is presented. Such problems involve arbitrarily large perturbations caused by small perturbations. A Fredholm integral equation of the first kind is an example.
Systems of linear equations and linear least squares problems \(\min_ x \| Ax - b\|_ 2\), \(A\in \mathbb{R}^{m\times n}\), \(m > n\) arising from discretization of ill-posed problems (i.e. the singular values of \(A\) decay gradually to zero and the ratio between the largest and the smallest nonzero singular value is large) are analyzed. The purpose of the regularization is to stabilize the problem and to single out a stable solution.
An analysis of the singular value decomposition (SVD) and the generalized SVD, the Picard condition, the discrete Picard condition, filter factors, a graphical analysis by the \(L\)-curve, the transformation of regularization problems by direct and iterative methods to standard form, methods for choosing the regularization parameter \(\lambda\) are discussed. 54 regularization routines are given and characterized. A complete manual of these routines can be obtained.
Reviewer: V.Burjan (Praha)

MSC:

65F20 Numerical solutions to overdetermined systems, pseudoinverses
65R30 Numerical methods for ill-posed problems for integral equations
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65R20 Numerical methods for integral equations
65F30 Other matrix algorithms (MSC2010)
45B05 Fredholm integral equations
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R.C. Allen, Jr., W.R. Boland, V. Faber and G.M. Wing, Singular values and condition numbers of Galerkin matrices arising from linear integral equations of the first kind, J. Math. Anal. Appl. 109 (1985) 564–590. · Zbl 0584.65086
[2] R.S. Anderssen and P.M. Prenter, A formal comparison of methods proposed for the numerical solution of first kind integral equations, J. Austral. Math. Soc. (Series B) 22 (1981) 488–500. · Zbl 0471.65094
[3] C.T.H. Baker, Expansion methods, chapter 7 in [18].
[4] C.T.H. Baker,The Numerical Treatment of Integral Equations (Clarendon Press, Oxford, 1977). · Zbl 0373.65060
[5] C.T.H. Baker and M.J. Miller (eds.),Treatment of Integral Equations by Numerical Methods (Academic Press, New York, 1982).
[6] D.M. Bates, M.J. Lindstrom, G. Wahba and B.S. Yandell, GCVPACK – routines for generalized cross validation, Commun. Statist.-Simul. 16 (1987) 263–297. · Zbl 0618.62004
[7] M. Bertero, C. De Mol and E.R. Pike, Linear inverse problems with discrete data: II. Stability and regularization, Inverse Problems 4 (1988) 573–594. · Zbl 0653.65042
[8] Å. Björck, A bidiagonalization algorithm for solving large and sparse ill-posed systems of linear equations, BIT 28 (1988) 659–670. · Zbl 0658.65041
[9] Å. Björck, Least squares methods, in:Handbook of Numerical Analysis, Vol. 1, eds. P.G. Ciarlet and J.L. Lions (Elsevier, Amsterdam, 1990).
[10] Å. Björck and L. Eldén, Methods in numerical algebra for ill-posed problems, Report LiTH-MAT-R33-1979, Dept. of Mathematics, Linköping University (1979).
[11] H. Brakhage, On ill-possed problems and the method of conjugate gradients, in:Inverse and Ill-Posed Problems, eds. H.W. Engl and C.W. Groetsch (Academic Press, Boston, 1987). · Zbl 0642.65042
[12] T.F. Chan and P.C. Hansen, Some applications of the rank revealing QR factorization, SIAM J. Sci. Stat. Comp. 13 (1992) 727–741. · Zbl 0756.65032
[13] J.A. Cochran,The Analysis of Linear Integral Equations (McGraw-Hill, New York, 1972). · Zbl 0233.45002
[14] D. Colton and R. Kress,Integral Equation Methods for Scattering Theory (Wiley, New York, 1983). · Zbl 0522.35001
[15] L.J.D. Craig and J.C. Brown,Inverse Problems in Astronomy (Adam Hilger, Bristol, 1986). · Zbl 0666.35001
[16] J.J.M. Cuppen, A numerical soluiton of the inverse problem of electrocardiology, Ph.D. Thesis, Dept. of Mathematics, Univ. of Amsterdam (1983). · Zbl 0517.65017
[17] L.M. Delves and J.L. Mohamed,Computational Methods for Integral Equations (Cambridge University Press, Cambridge, 1985). · Zbl 0592.65093
[18] L.M. Delves and J. Walsh (eds.),Numerical Soluution of Integral Equations (Clarendon Press, Oxford, 1974).
[19] J.B. Drake, ARIES: a computer program for the solution of first kind integral equations with noisy data, Report K/CSD/TM43, Dept. of Computer Science, Oak Ridge National Laboratory (October 1983).
[20] M.P. Ekstrom and R.L. Rhodes, On the application of eigenvector expansions to numerical deconvolution, J. Comp. Phys. 14 (1974) 319–340. · Zbl 0279.65107
[21] L. Eldén, A program for interactive regularization, Report LiTH-MAT-R-79-25, Dept. of Mathematics, Linköping University, Sweded (1979).
[22] L. Eldén, Algorithms for regularization of ill-conditioned least-squares problems, BIT 17 (1977) 134–145. · Zbl 0362.65105
[23] L. Eldén, A weighted pseudoinverse, generalized singular values, and constrained least squares problems, BIT 22 (1982) 487–501. · Zbl 0509.65019
[24] L. Eldén, A note on the computation of the genralized cross-validation function for illconditioned least squares problems, BIT 24 (1984) 467–472. · Zbl 0554.65029
[25] H.W. Engl and J. Gfrerer, A posteriori parameter choice for general regularization methods for solving linear ill-posed problems, Appl. Numer. Math. 4 (1988) 395–417. · Zbl 0647.65038
[26] R.D. Fierro and J.R. Bunch, Collinearity and total least squares, Report, Dept. of Mathematics, Univ. of California, San Diego (1991), to appear in SIAM J. Matrix Anal. Appl. · Zbl 0805.65042
[27] R.D. Fierro, P.C. Hansen and D.P. O’Leary, Regularization and total least squares, manuscript in preparation for SIAM J. Sci. Comp.
[28] R. Fletcher,Practical Optimization Methods. vol. 1, 2nd ed. (Wiley, Chichester, 1987). · Zbl 0905.65002
[29] G.H. Golub and C.F. Van Loan,Matrix Computations, 2nd ed. (Johns Hopkins, Baltimore, 1989). · Zbl 0733.65016
[30] G.H. Golub and U. von Matt, Quadratically constrained least squares and quadratic problems, Numer. Mathematik 59 (1991) 561–580. · Zbl 0745.65029
[31] C.W. Groetsch,The Theory of Tikhonov Regularization for Fredholm Equations of the First Kind (Pitman, Boston, 1984). · Zbl 0545.65034
[32] C.W. Groetsch,Inverse Problems in the Mathematical Sciences (Vieweg Verlag, Wiesbaden), to be published. · Zbl 0779.45001
[33] C.W. Groetsch and C.R. Vogel, Asymptotic theory of filtering for linear operator equations with discrete noisy data, Math. Comp. 49 (1987) 499–506. · Zbl 0687.65122
[34] J. Hadamard,Lectures on Cauchy’s Problem in Linear Differential Equations (Yale University Press, New Haven, 1923). · JFM 49.0725.04
[35] M. Hanke, Regularization with differential operators. An interative approach, J. Numer. Funct. Anal. Optim. 13 (1992) 523–540. · Zbl 0769.65027
[36] M. Hanke, Iterative solution of undertermined linear systems by transformation to standard form, submitted to J. Num. Lin. Alg. Appl.
[37] M. Hanke and P.C. Hansen, Regularization methods for large-scale problems, Report UNIC-92-04, UNI.C (August 1992), to appear in Surveys Math. Ind. · Zbl 0805.65058
[38] P.C. Hansen, The truncated SVD as a method for regularization, BIT 27 (1987) 543–553. · Zbl 0633.65041
[39] P.C. Hansen, Computation of the singular value expansion, Computing 40 (1988) 185–199. · Zbl 0631.65133
[40] P.C. Hansen, Perturbation bounds for discrete Tikhonov regularization, Inverse Problems 5 (1989) L41-L44. · Zbl 0695.65022
[41] P.C. Hansen, Regularization, GSVD and truncated GSVD, BIT 29 (1989) 491–504. · Zbl 0682.65021
[42] P.C. Hansen, Truncated SVD solutions to discrete ill-posed problems with ill-determined numerical rank, SIAM J. Sci. Statist. Comp. 11 (1990) 503–518. · Zbl 0699.65029
[43] P.C. Hansen, Relations between SVD and GSVD of discrete regularization problems in standard and general form, Lin. Alg. Appl. 141 (1990) 165–176. · Zbl 0717.65024
[44] P.C. Hansen, The discrete Picard condition for discrete ill-posed problems, BIT 30 (1990) 658–672. · Zbl 0723.65147
[45] P.C. Hansen, Analysis of discrete ill-posed problems by means of the L-curve, SIAM Rev. 34 (1992) 561–580. · Zbl 0770.65026
[46] P.C. Hansen, Numerical tools for analysis and solution of Fredhold integral equations of the first kind, Inverse Problems 8 (1992) 849–872. · Zbl 0782.65153
[47] P.C. Hansen, Regularization Tools, a Matlab package for analysis and solution of discrete ill-posed problems; Version 2.0 for Matlab 4.0, Report UNIC-92-03 (March 1993). Available in PostScript form by e-mail via netlib (netlib@research.att.com) from the library NUMERALGO.
[48] P.C. Hansen and D.P. O’Leary, The use of the L-curve in the regularization of discrete ill-posed problems, Report CS-TR-2781, Dept. of Computer Science, Univ. of Maryland (1991), to appear in SIAM J. Sci. Comp.
[49] P.C. Hansen, D.P. O’Leary and G.W. Stewart, Regularizing properties of conjugate gradient iterations, work in progress.
[50] P.C. Hansen, T. Sekii and H. Shibahashi, The modified truncate SVD method for regularization is general form, SIAM J. Sci. Statist. Comp. 13 (1992) 1142–1150. · Zbl 0760.65044
[51] B. Hofmann,Regularization for Applied Inverse and Ill-Posed Problems (Teubner, Leipzig, 1986). · Zbl 0606.65038
[52] T. Kitagawa, A deterministic approach to optimal regularization – the finite dimensional case, Japan J. Appl. Math. 4 (1987) 371–391. · Zbl 0632.65062
[53] R. Kress,Linear Integral Equations (Springer, Berlin, 1989). · Zbl 0671.45001
[54] C.L. Lawson and R.J. Hanson,Solving Least Squares Problems (Prentice-Hall, Englewood Cliffs, 1974). · Zbl 0860.65028
[55] P. Linz, Uncertainty in the solution of linear operator equations, BIT 24 (1984) 92–101. · Zbl 0546.65036
[56] Matlab Reference Guide (The Math Works, MA, 1992).
[57] K. Miller, Least squares methods for ill-posed problems with a prescribed bound, SIAM J. Math. Anal. 1 (1970) 52–74. · Zbl 0214.14804
[58] V.A. Morozov,Methods for Solving Incorrectly Posed Problems (Springer, New York, 1984).
[59] F. Natterer,The Mathematics of Computerized Tomography (Wiley, New York, 1986). · Zbl 0617.92001
[60] F. Natterer, Numerical treatment of ill-posed problems, in –. · Zbl 0605.65086
[61] D.P. O’Leary and J.A. Simmons, A bidiagonalization-regularization procedure for large scale discretizations of ill-posed problems, SIAM J. Sci. Stat. Comp. 2 (1981) 474–489. · Zbl 0469.65089
[62] C.C. Paige and M.A. Saunders, LSQR: an algorithm for sparse linear equations and sparse least squares, ACM Trans. Math. Software 8 (1982) 43–71. · Zbl 0478.65016
[63] R.L. Parker, Understanding inverse theory, Ann. Rev. Earth Planet Sci. 5 (1977), 35–64.
[64] D.L. Phillips, A technique for the numerical solution of certain integral equations of the first kind, J. ACM 9 (1962) 84–97. · Zbl 0108.29902
[65] F. Santosa, Y.-H. Pao, W.W. Symes and C. Holland (eds.),Inverse Problems of Acoustic and Elastic Waves (SIAM, Philadelphia, 1984). · Zbl 0618.00011
[66] C. Ray Smith and W.T. Grandy, Jr. (eds.),Maximum-Entropy and Bayesian Methods in Inverse Problems (Reidel, Boston, 1985).
[67] G. Talenti,Inverse Problems, Lecture Notes in Mathematics, 1225 (Springer, Berlin, 1986). · Zbl 0595.00010
[68] H.J.J. te Tiele, A program for solving first kind Fredholm integral equations by means of regularization, Comp. Phys. Comm. 36 (1985) 423–432. · Zbl 0578.65137
[69] A.N. Tikhonov, Solution of incorrectly formulated problems and the regularization method, Dokl. Adak. Nauk. SSSR 151 (1963) 501–504 [Soviet Math. Dokl. 4 (1963) 1035–1038]. · Zbl 0141.11001
[70] A.N. Tikhonov and V.Y. Arsenin,Solutions of Ill-Posed Problems (Winston, Washington, DC, 1977).
[71] A.N. Tikhonov and A.V. Goncharsky,Ill-Posed Problems in the Natural Sciences (MIR, Moscow, 1987).
[72] A. van der Sluis, The convergence behavior of conjugate gradients and Ritz values in various circumstances, in:Iterative Methods in Linear Algebra, eds. R. Bauwens and P. de Groen (North-Holland, Amsterdam, 1992). · Zbl 0785.65040
[73] A. van der Sluis and H.A. van der Vorst, SIRT- and CG-type methods for iterative solution of sparse linear least-squares problems, Lin. Alg. Appl. 130 (1990) 257–302. · Zbl 0702.65042
[74] J.M. Varah, On the numerical solution of ill-conditioned linear systems with applications to illposed problems, SIAM J. Numer. Anal. 10 (1973) 257–267. · Zbl 0261.65034
[75] J.M. Varah, A practical examination of some numerical methods for linear discrete ill-posed problems, SIAM Rev. 21 (1979) 100–111. · Zbl 0406.65015
[76] J.M. Varah, Pitfalls in the numerical solution of linear ill-possed problems, SIAM J. Sci. Statist. Comp. 4 (1983) 164–176. · Zbl 0533.65082
[77] C.R. Vogel, Optimal choice of a truncationlevel for the standard SVD solutio of linear first kind integral equations when data are noisy, SIAM J. Numer. Anal. 23 (1986) 109–117. · Zbl 0593.65091
[78] C.R. Vogel, Solving ill-conditioned linear systems using the conjugate gradient method, Report, Dept. of Mathematical Sciences, Montana State University (1987).
[79] G. Wahba,Spline Models for Observational Data, CBMS-NSF Regional Conference Series in Applied Mathematics, Vol. 59 (SIAM, Philidelphia, 1990). · Zbl 0813.62001
[80] G.M. Wing, Condition numbers of matrices arising from the numerical solution of linear integral equations of the first kind, J. Integral Equations 9 (Suppl.) (1985) 191–204. · Zbl 0578.65134
[81] G.M. Wing and J.D. Zahrt,A Primer on Integral Equations of the First Kind (SIAM, Philidelphia, 1991).
[82] H. Zha and P.C. Hansen, Regularization and the general Gauss-Markov linear model, Math. Comp. 55 (1990) 613–624. · Zbl 0722.65020
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.