Condition numbers and perturbation analysis for the Tikhonov regularization of discrete ill-posed problems. (English) Zbl 1249.65084
The authors consider Tikhonov regularization for discrete ill-posed problems of the form
\[
\min _{x}\{\| Ax-b\| _2^2+\lambda ^2\| Lx \| _2^{2}\}, \quad A\in \mathbb {R}^{m\times n},\quad L\in \mathbb {R}^{p\times n},
\]
where the regularization parameter \(\lambda \) controls the weight given to the minimization of \(\| Lx\| _2\) relative to the minimization of the residual \(\| Ax-b\| _2\). The general case, when both the coefficient matrix \(A\) and the right-hand side \(b\) are perturbed, is studied. The authors define the normwise, mixed and componentwise condition numbers of Tikhonov regularization, and present formulas for computing these numbers. New perturbation results corresponding to the componentwise errors in \(A\) and \(b\) are derived. Numerical examples compare the new perturbation bounds with some well-known results by P. C. Hansen and A. N. Malyshev.
Reviewer: Petr Tichý (Praha)
MSC:
| 65F22 | Ill-posedness and regularization problems in numerical linear algebra |
| 65F20 | Numerical solutions to overdetermined systems, pseudoinverses |
| 65F35 | Numerical computation of matrix norms, conditioning, scaling |
Keywords:
Tikhonov regularization; perturbation analysis; condition number; discrete ill-posed problems; numerical examplesReferences:
| [1] | Tikhonov, Solution of incorrectly formulated problems and the regularization method, Soviet Mathematics-Doklady 4 pp 1035– (1963) · Zbl 0141.11001 |
| [2] | Engl, Regularization methods for the stable solution of inverse problems, Surveys on Mathematics for Industry 3 pp 71– (1993) · Zbl 0776.65043 |
| [3] | Engl, Regularization of Inverse Problems (1996) · doi:10.1007/978-94-009-1740-8 |
| [4] | Groetsch, Research Notes in Mathematics, in: The Theory of Tikhonov Regularization for Fredholm Equations of the First Kind (1984) · Zbl 0545.65034 |
| [5] | Groetsch, Inverse Problems in the Mathematical Sciences (1993) · doi:10.1007/978-3-322-99202-4 |
| [6] | Hanke, Regularization methods for large-scale problems, Surveys on Mathematics for Industry 3 pp 253– (1993) · Zbl 0805.65058 |
| [7] | Calvetti, Tikhonov regularization of large linear problems, BIT 43 pp 263– (2003) · Zbl 1038.65048 · doi:10.1023/A:1026083619097 |
| [8] | Calvetti, Tikhonov regularization of large symmetric problems, Numerical Linear Algebra with Applications 12 pp 127– (2005) · Zbl 1164.65377 · doi:10.1002/nla.402 |
| [9] | Eldén, Algorithms for the regularization of ill-conditioned least squares problems, BIT 17 pp 134– (1977) · Zbl 0362.65105 · doi:10.1007/BF01932285 |
| [10] | Golub, Workshop on Scientific Computing pp 3– (1997) |
| [11] | Gulliksson, Perturbation theory for generalized and constrained linear least squares, Numerical Linear Algebra with Applications 7 pp 181– (2000) · Zbl 1051.65043 · doi:10.1002/1099-1506(200005)7:4<181::AID-NLA193>3.0.CO;2-D |
| [12] | Gulliksson, Perturbation identities for regularized Tikhonov inverses and weighted pseudoinverses, BIT 40 pp 513– (2000) · Zbl 0965.65063 · doi:10.1023/A:1022319830134 |
| [13] | Björck, Numerical Methods for Least Squares Problems (1996) · doi:10.1137/1.9781611971484 |
| [14] | Malyshev, A unified theory of conditioning for linear least squares and Tikhonov regularization solutions, SIAM Journal on Matrix Analysis and Applications 24 pp 1186– (2003) · Zbl 1036.65044 · doi:10.1137/S0895479801389564 |
| [15] | Higham, A survey of componentwise perturbation theory in numerical linear algebra, Proceedings of Symposia in Applied Mathematics 48 pp 49– (1994) · Zbl 0815.65062 · doi:10.1090/psapm/048/1314843 |
| [16] | Higham, Accuracy and Stability of Numerical Algorithms (2002) · Zbl 1011.65010 · doi:10.1137/1.9780898718027 |
| [17] | Gohberg, Mixed compontwise, and structured conditon numbers, SIAM Journal on Matrix Analysis and Applications 14 pp 688– (1993) · Zbl 0780.15004 · doi:10.1137/0614049 |
| [18] | Skeel, Scaling for numerical stability in Gaussian elimination, Journal of Association for Computing Machinery 26 pp 167– (1979) · Zbl 0435.65035 · doi:10.1145/322139.322148 |
| [19] | Rohn, New condition numbers for matrices and linear systems, Computing 41 pp 167– (1989) · Zbl 0665.65042 · doi:10.1007/BF02238741 |
| [20] | Björck, Componentwise perturbation analysis and error bounds for linear least squares solutions, BIT 31 pp 238– (1991) · Zbl 0732.65043 |
| [21] | Cucker, On mixed and componentwise condition numbers for Moore-Penrose inverse and linear least squares problems, Mathematics of Computation 78 (258) pp 947– (2007) · Zbl 1115.15004 · doi:10.1090/S0025-5718-06-01913-2 |
| [22] | Demmel, Extra-precise iterative refinement for overdetermined least squares problems, ACM Transactions on Mathematical Software 35 (4) (2009) · doi:10.1145/1462173.1462177 |
| [23] | Arioli, On the augmented system approach to sparse least squares problems, Numerische Mathematik 55 pp 667– (1989) · Zbl 0678.65024 · doi:10.1007/BF01389335 |
| [24] | Baboulin, Computing the conditioning of the components of a linear least-squares solution, Numerical Linear Algebra with Applications 16 pp 517– (2009) · Zbl 1224.65104 · doi:10.1002/nla.627 |
| [25] | Ben-Israel, Generalized Inverses: Theory and Applications (2003) |
| [26] | Wang, Generalized Inverses: Theory and Computations (2004) |
| [27] | Gratton, On the condition number of linear least squares problems in a weighted Frobenius norm, BIT 36 pp 523– (1996) · Zbl 0878.65030 · doi:10.1007/BF01731931 |
| [28] | Rice, A theory of condition, SIAM Journal on Numerical Analysis 3 pp 175– (1996) |
| [29] | Bauer, Genauigkeitsfragen bei der Losung linearer Gleichungssysteme, Zeitschrift für Angewandte Mathematik und Mechanik 46 pp 409– (1966) · Zbl 0148.39101 · doi:10.1002/zamm.19660460702 |
| [30] | Hansen, Regularization Tools version 4.0 for Matlab 7.3, Numerical Algorithms 46 pp 189– (2007) · Zbl 1128.65029 · doi:10.1007/s11075-007-9136-9 |
| [31] | Hansen, Regularization GSVD and truncated GSVD, BIT 29 pp 491– (1989) · Zbl 0682.65021 · doi:10.1007/BF02219234 |
| [32] | Hansen, Perturbation bounds for discrete Tikhonov regularization, Inverse Problems 5 pp 41– (1989) · Zbl 0695.65022 · doi:10.1088/0266-5611/5/4/002 |
| [33] | Hansen, Truncated SVD solutions to discrete ill-posed problems with ill-determined numerical rank, SIAM Journal on Scientific and Statistical Computing 11 pp 503– (1990) · Zbl 0699.65029 · doi:10.1137/0911028 |
| [34] | Van Loan, Generalizing the singular value decomposition, SIAM Journal on Numerical Analysis 13 pp 76– (1976) · Zbl 0338.65022 · doi:10.1137/0713009 |
| [35] | Hanke, Conjugate Gradient Type Methods for Ill-posed Problems (1995) · Zbl 0830.65043 |
| [36] | Phillips, A technique for the numerical solution of certain integral equations of the first kind, Journal of Association for Computing Machinery 9 pp 84– (1962) · Zbl 0108.29902 · doi:10.1145/321105.321114 |
| [37] | Hansen, Analysis of discrete ill-posed problems by means of the L-curve, SIAM Review 34 pp 561– (1992) · Zbl 0770.65026 · doi:10.1137/1034115 |
| [38] | Morozov, Methods for Solving Incorrectly Posed Problems (1984) · doi:10.1007/978-1-4612-5280-1 |
| [39] | Wahba, CBMS-NSF Regional Conference Series in Applied Mathematics, in: Spline Models for Observational Data (1990) · doi:10.1137/1.9781611970128 |
| [40] | Shaw, Improvements of the resolution of an instrument by numerical solution of an integral equation, Journal of Mathematical Analysis and Applications 37 pp 83– (1972) · Zbl 0237.65086 · doi:10.1016/0022-247X(72)90259-4 |
| [41] | Hansen, Rank-deficient and Discrete Ill-posed Problems (1997) · Zbl 0890.65037 |
| [42] | Wing, A Primer on Integral Equations of the First Kind (1991) · doi:10.1137/1.9781611971675 |
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.
