×

Discrete ill-posed least-squares problems with a solution norm constraint. (English) Zbl 1237.65039

Summary: The straightforward solution of discrete ill-posed least-squares problems with error-contaminated data does not, in general, give meaningful results, because propagated error destroys the computed solution. Error propagation can be reduced by imposing constraints on the computed solution. A commonly used constraint is the discrepancy principle, which bounds the norm of the computed solution when applied in conjunction with Tikhonov regularization. Another approach, which recently has received considerable attention, is to explicitly impose a constraint on the norm of the computed solution. For instance, the computed solution may be required to have the same Euclidean norm as the unknown solution of the error-free least-squares problem. We compare these approaches and discuss numerical methods for their implementation, among them a new implementation of the Arnoldi – Tikhonov method. Also solution methods which use both the discrepancy principle and a solution norm constraint are considered.

MSC:

65F22 Ill-posedness and regularization problems in numerical linear algebra
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Calvetti, D.; Lewis, B.; Reichel, L., On the choice of subspace for iterative methods for linear discrete ill-posed problems, Int. J. Appl. Math. Comput. Sci., 11, 1069-1092 (2001) · Zbl 0994.65043
[2] Calvetti, D.; Lewis, B.; Reichel, L.; Sgallari, F., Tikhonov regularization with nonnegativity constraint, Electron. Trans. Numer. Anal., 18, 153-173 (2004) · Zbl 1069.65047
[3] Calvetti, D.; Reichel, L., Tikhonov regularization with a solution constraint, SIAM J. Sci. Comput., 26, 224-239 (2004) · Zbl 1081.65033
[4] Chan, T. F.; Jackson, K. R., Nonlinearly preconditioned Krylov subspace methods for discrete Newton algorithms, SIAM J. Sci. Statist. Comput., 5, 533-542 (1984) · Zbl 0574.65043
[5] Eldén, L., A weighted pseudoinverse, generalized singular values, and constrained least squares problems, BIT, 22, 487-501 (1982) · Zbl 0509.65019
[6] Gander, W., Least squares with a quadratic constraint, Numer. Math., 36, 291-307 (1991) · Zbl 0437.65031
[7] Golub, G. H.; von Matt, U., Quadratically constrained least squares and quadratic problems, Numer. Math., 59, 561-580 (1991) · Zbl 0745.65029
[8] Groetsch, C. W., The Theory of Tikhonov Regularization for Fredholm Equations of the First Kind (1984), Pitman: Pitman Boston · Zbl 0545.65034
[9] Hansen, P. C., Rank-Deficient and Discrete Ill-Posed Problems (1998), SIAM: SIAM Philadelphia
[10] Hansen, P. C., Regularization tools version 4.0 for Matlab 7.3, Numer. Algorithms, 46, 189-194 (2007) · Zbl 1128.65029
[11] Kirsch, A., An Introduction to the Mathematical Theory of Inverse Problems (1996), Springer: Springer New York · Zbl 0865.35004
[12] Lampe, J.; Rojas, M.; Sorensen, D.; Voss, H., Accelerating the LSTRS algorithm, SIAM J. Sci. Comput., 33, 175-194 (2011) · Zbl 1368.65096
[13] Lampe, J.; Voss, H., A fast algorithm for solving regularized total least squares problems, Electron. Trans. Numer. Anal., 31, 12-24 (2008) · Zbl 1171.15305
[14] Lewis, B.; Reichel, L., Arnoldi-Tikhonov regularization methods, J. Comput. Appl. Math., 226, 92-102 (2009) · Zbl 1166.65016
[15] Li, R.-C.; Ye, Q., A Krylov subspace method for quadratic matrix polynomials with application to constrained least squares problems, SIAM J. Matrix Anal. Appl., 25, 405-428 (2003) · Zbl 1050.65038
[16] Morigi, S.; Reichel, L.; Sgallari, F., Orthogonal projection regularization operators, Numer. Algorithms, 44, 99-114 (2007) · Zbl 1124.65043
[17] A. Neuman, L. Reichel, H. Sadok, Implementations of range restricted iterative methods for linear discrete ill-posed problems, Linear Algebra Appl., in press, doi:10.1016/j.laa.2010.08.033; A. Neuman, L. Reichel, H. Sadok, Implementations of range restricted iterative methods for linear discrete ill-posed problems, Linear Algebra Appl., in press, doi:10.1016/j.laa.2010.08.033 · Zbl 1241.65045
[18] Reichel, L.; Ye, Q., Simple square smoothing regularization operators, Electron. Trans. Numer. Anal., 33, 63-83 (2009) · Zbl 1171.65033
[19] Reinsch, C. H., Smoothing by spline functions, Numer. Math., 10, 177-183 (1967) · Zbl 0161.36203
[20] Reinsch, C. H., Smoothing by spline functions II, Numer. Math., 16, 451-454 (1971) · Zbl 1248.65020
[21] Rojas, M.; Sorensen, D. C., A trust-region approach to regularization of large-scale discrete forms of ill-posed problems, SIAM J. Sci. Comput., 23, 1842-1860 (2002) · Zbl 1006.86004
[22] Rojas, M.; Steihaug, T., An interior-point trust-region-based method for large-scale non-negative regularization, Inverse Problems, 18, 1291-1307 (2002) · Zbl 1015.90062
[23] Rutishauser, H., (Gutknecht, M., Lectures on Numerical Mathematics (1990), Birkhäuser: Birkhäuser Basel)
[24] Saad, Y., Iterative Methods for Sparse Linear Systems (2003), SIAM: SIAM Philadelphia · Zbl 1002.65042
[25] Stammberger, M.; Voss, H., On an unsymmetric eigenvalue problem governing free vibrations of fluid-solid structures, Electron. Trans. Numer. Anal., 36, 113-125 (2010) · Zbl 1237.74028
[26] Voss, H., An Arnoldi method for nonlinear eigenvalue problems, BIT, 44, 387-401 (2004) · Zbl 1066.65059
[27] Wendland, H., Scattered Data Approximation (2005), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1075.65021
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.