×

On the computation of a truncated SVD of a large linear discrete ill-posed problem. (English) Zbl 1368.65063

Summary: The singular value decomposition (SVD) is commonly used to solve linear discrete ill-posed problems of small to moderate size. This decomposition not only can be applied to determine an approximate solution but also provides insight into properties of the problem. However, large-scale problems generally are not solved with the aid of the singular value decomposition, because its computation is considered too expensive. This paper shows that a truncated singular value decomposition, made up of a few of the largest singular values and associated right and left singular vectors, of the matrix of a large-scale linear discrete ill-posed problems can be computed quite inexpensively by an implicitly restarted Golub-Kahan bidiagonalization method. Similarly, for large symmetric discrete ill-posed problems a truncated eigendecomposition can be computed inexpensively by an implicitly restarted symmetric Lanczos method.

MSC:

65F20 Numerical solutions to overdetermined systems, pseudoinverses
65F22 Ill-posedness and regularization problems in numerical linear algebra
Full Text: DOI

References:

[1] Abdel-Rehim, A. M., Morgan, R. B., Wilcox, W.: Improved seed methods for symmetric positive definite linear equations with multiple right-hand sides. Numer. Linear Algebra Appl. 21, 453-471 (2014) · Zbl 1340.65041 · doi:10.1002/nla.1892
[2] Baart, M. L.: The use of auto-correlation for pseudo-rank determination in noisy ill-conditioned linear least-squares problems. IMA J. Numer. Anal. 2, 241-247 (1982) · Zbl 0484.65021 · doi:10.1093/imanum/2.2.241
[3] Baglama, J., Calvetti, D., Reichel, L.: Irbl: An implicitly restarted block Lanczos method for large-scale Hermitian eigenproblems. SIAM J. Sci. Comput. 24, 1650-1677 (2003) · Zbl 1044.65027 · doi:10.1137/S1064827501397949
[4] Baglama, J., Calvetti, D., Reichel, L.: Algorithm 827: irbleigs: a MATLAB program for computing a few eigenpairs of a large sparse Hermitian matrix. ACM Trans. Math. Software 29, 337-348 (2003) · Zbl 1070.65529 · doi:10.1145/838250.838257
[5] Baglama, J., Reichel, L.: Augmented implicitly restarted Lanczos bidiagonalization methods. SIAM J. Sci. Comput. 27, 19-42 (2005) · Zbl 1087.65039 · doi:10.1137/04060593X
[6] Baglama, J., Reichel, L.: Restarted block Lanczos bidiagonalization methods. Numer. Algorithms 43, 251-272 (2006) · Zbl 1110.65027 · doi:10.1007/s11075-006-9057-z
[7] Baglama, J., Reichel, L.: An implicitly restarted block Lanczos bidiagonalization method using Leja shifts. BIT Numer. Math. 53, 285-310 (2013) · Zbl 1269.65038
[8] Baglama, J., Reichel, L., Lewis, B.: irbla: Fast partial SVD by implicitly restarted Lanczos bidiagonalization. R package, version 2.0.0; see https://cran.r-project.org/package=irlba · Zbl 1340.65070
[9] Bai, Z.-Z., Buccini, A., Hayami, K., Reichel, L., Yin, J.-F., Zheng, N.: A modulus-based iterative method for constrained Tikhonov regularization. J. Comput. Appl. Math. in press · Zbl 1360.65112
[10] Björck, Å: Numerical Methods in Matrix Computation. Springer, New York (2015) · Zbl 1322.65047 · doi:10.1007/978-3-319-05089-8
[11] Breuer, A.: New filtering strategies for implicitly restarted Lanczos iteration. Electron. Trans. Numer. Anal. 45, 16-32 (2016) · Zbl 1382.65098
[12] Calvetti, D., Reichel, L.: Tikhonov regularization of large linear problems. BIT 43, 263-283 (2003) · Zbl 1038.65048 · doi:10.1023/A:1026083619097
[13] Calvetti, D., Reichel, L., Sorensen, D. C.: An implicitly restarted Lanczos method for large symmetric eigenvalue problems. Electron. Trans. Numer. Anal. 2, 1-21 (1994) · Zbl 0809.65030
[14] Dykes, L., Reichel, L.: A family of range restricted iterative methods for linear discrete ill-posed problems. Dolomites Research Notes on Approximation 6, 27-36 (2013) · Zbl 1291.65117
[15] Engl, H. W., Hanke, M., Neubauer, A.: Regularization of Inverse Problems. Kluwer, Dordrecht (1996) · Zbl 0859.65054 · doi:10.1007/978-94-009-1740-8
[16] Fenu, C., Reichel, L., Rodriguez, G.: GCV For Tikhonov regularization via global Golub-Kahan decomposition. Numer. Linear Algebra Appl. 23, 467-484 (2016) · Zbl 1374.65064 · doi:10.1002/nla.2034
[17] Fenu, C., Reichel, L., Rodriguez, G., Sadok, H.: GCV for Tikhonov regularization by partial SVD. Submitted for publication · Zbl 1386.65118
[18] Fox, L., Goodwin, E. T.: The numerical solution of non-singular linear integral equations. Philos. Trans. Roy. Soc. Lond. Ser. A, Math. Phys. Eng. Sci. 245:902, 501-534 (1953) · Zbl 0050.12902 · doi:10.1098/rsta.1953.0005
[19] Gazzola, S., Novati, P., Russo, M. R.: On Krylov projection methods and Tikhonov regularization method. Electron. Trans. Numer. Anal. 44, 83-123 (2015) · Zbl 1312.65065
[20] Gazzola, S., Onunwor, E., Reichel, L., Rodriguez, G.: On the Lanczos and Golub-Kahan reduction methods applied to discrete ill-posed problems. Numer. Linear Algebra Appl. 23, 187-204 (2016) · Zbl 1413.65120 · doi:10.1002/nla.2020
[21] Golub, G. H., Van Loan, C. F.: Matrix Computations, 4th ed. Johns Hopkins University Press, Baltimore (2013) · Zbl 1268.65037
[22] Hanke, M.: Conjugate Gradient Type Methods for Ill-Posed Problems. Longman, Harlow (1995) · Zbl 0830.65043
[23] Hansen, P. C.: Rank-Deficient and Discrete Ill-Posed Problems. SIAM, Philadelphia (1998) · Zbl 0890.65037 · doi:10.1137/1.9780898719697
[24] Hansen, P. C.: Regularization tools version 4.0 for Matlab 7.3. Numer. Algorithms 46, 189-194 (2007) · Zbl 1128.65029 · doi:10.1007/s11075-007-9136-9
[25] Jia, Z., Niu, D.: A refined harmonic Lanczos bidiagonalization method and an implicitly restarted algorithm for computing the smallest singular triplets of large matrices. SIAM J. Sci. Comput. 32, 714-744 (2010) · Zbl 1215.65072 · doi:10.1137/080733383
[26] Kindermann, S.: Convergence analysis of minimization-based noise level-free parameter choice rules for linear ill-posed problems. Electron. Trans. Numer. Anal. 38, 233-257 (2011) · Zbl 1287.65043
[27] Martin, D. R., Reichel, L.: Minimization of functionals on the solution of a large-scale discrete ill-posed problem. BIT Numer. Math. 53, 153-173 (2013) · Zbl 1262.65053 · doi:10.1007/s10543-012-0396-y
[28] Morikuni, K., Hayami, K.: Convergence of inner-iteration GMRES methods for rank-deficient least squares problems. SIAM J. Matrix Anal. Appl. 36, 225-250 (2015) · Zbl 1315.65041 · doi:10.1137/130946009
[29] Morikuni, K., Reichel, L., Hayami, K.: FGMRES for linear discrete ill-posed problems. Appl. Numer. Math. 75, 175-187 (2014) · Zbl 1302.65081 · doi:10.1016/j.apnum.2013.08.004
[30] Neuman, A., Reichel, L., Sadok, H.: Implementations of range restricted iterative methods for linear discrete ill-posed problems. Linear Algebra Appl. 436, 3974-3990 (2012) · Zbl 1241.65045 · doi:10.1016/j.laa.2010.08.033
[31] Noschese, S., Reichel, L.: A modified TSVD method for discrete ill-posed problems. Numer. Linear Algebra Appl. 21, 813-822 (2014) · Zbl 1340.65070 · doi:10.1002/nla.1938
[32] O’Leary, D. P., Simmons, J. A.: A bidiagonalization-regularization procedure for large scale discretizations of ill-posed problems. SIAM J. Sci. Statist. Comput. 2, 474-489 (1981) · Zbl 0469.65089 · doi:10.1137/0902037
[33] Phillips, D. L.: A technique for the numerical solution of certain integral equations of the first kind. J. ACM 9, 84-97 (1962) · Zbl 0108.29902 · doi:10.1145/321105.321114
[34] Reichel, L., Rodriguez, G.: Old and new parameter choice rules for discrete ill-posed problems. Numer. Algorithms 63, 65-87 (2013) · Zbl 1267.65045 · doi:10.1007/s11075-012-9612-8
[35] Saad, Y.: On the Lanczos method for solving symmetric linear systems with several right-hand sides. Math. Comp. 48, 651-662 (1987) · Zbl 0615.65038
[36] Saad, Y.: Numerical Methods for Large Eigenvalue Problems, Revised Edition. SIAM, Philadelphia (2011) · Zbl 1242.65068 · doi:10.1137/1.9781611970739
[37] Shaw Jr., C. B.: Improvements of the resolution of an instrument by numerical solution of an integral equation. J. Math. Anal. Appl. 37, 83-112 (1972) · Zbl 0237.65086 · doi:10.1016/0022-247X(72)90259-4
[38] Soodhalter, K. M.: Two recursive GMRES-type methods for shifted linear systems with general preconditioning. Electron. Trans. Numer. Anal. 45, 499-523 (2016) · Zbl 1355.65055
[39] Sorensen, D. C.: Implicit application of polynomial filters in a k-step Arnoldi method. SIAM J. Matrix Anal. Appl. 13, 357-385 (1992) · Zbl 0763.65025 · doi:10.1137/0613025
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.