×

On the Lanczos and Golub-Kahan reduction methods applied to discrete ill-posed problems. (English) Zbl 1413.65120

Summary: The symmetric Lanczos method is commonly applied to reduce large-scale symmetric linear discrete ill-posed problems to small ones with a symmetric tridiagonal matrix. We investigate how quickly the nonnegative subdiagonal entries of this matrix decay to zero. Their fast decay to zero suggests that there is little benefit in expressing the solution of the discrete ill-posed problems in terms of the eigenvectors of the matrix compared with using a basis of Lanczos vectors, which are cheaper to compute. Similarly, we show that the solution subspace determined by the LSQR method when applied to the solution of linear discrete ill-posed problems with a nonsymmetric matrix often can be used instead of the solution subspace determined by the singular value decomposition without significant, if any, reduction of the quality of the computed solution.

MSC:

65F22 Ill-posedness and regularization problems in numerical linear algebra
65F10 Iterative numerical methods for linear systems
65F35 Numerical computation of matrix norms, conditioning, scaling
Full Text: DOI

References:

[1] SaadY. Iterative Methods for Sparse Linear Systems (2nd edn). SIAM: Philadelphia, 2003. · Zbl 1031.65046
[2] SaadY. Numerical Methods for Large Eigenvalue Problems, Revised Edition. SIAM: Philadelphia, 2011. · Zbl 1242.65068
[3] EnglHW, HankeM, NeubauerA. Regularization of Inverse Problems. Kluwer: Dordrecht, 1996. · Zbl 0859.65054
[4] HansenPC. Rank‐deficient and Discrete Ill‐posed Problems. SIAM: Philadelphia, 1998.
[5] GazzolaS, NovatiP, RussoMR. Embedded techniques for choosing the parameter in Tikhonov regularization. Numerical Linear Algebra with Applications2014; 21:796-812. · Zbl 1340.65068
[6] GazzolaS, NovatiP, RussoMR. On Krylov projection methods and Tikhonov regularization method. Electronic Transactions on Numerical Analysis2015; 44:83-123. · Zbl 1312.65065
[7] NovatiP, RussoMR. A GCV based Arnoldi-Tikhonov regularization method. BIT Numerical Mathematics2014; 54:501-521. · Zbl 1317.65104
[8] TrefethenLN, EmbreeM. Spectra and Pseudospectra: The Behavior of Nonnormal Matrices and Operators. Princeton University Press: Princeton, 2005. · Zbl 1085.15009
[9] BaglamaJ, CalvettiD, ReichelL. IRBL: an implicitly restarted block Lanczos method for large‐scale Hermitian eigenproblems. SIAM Journal on Scientific Computing2003; 24:1650-1677. · Zbl 1044.65027
[10] CalvettiD, LewisB, ReichelL. On the choice of subspace for iterative methods for linear discrete ill‐posed problems. International Journal of Applied Mathematics and Computer Science2001; 11:1069-1092. · Zbl 0994.65043
[11] DykesL, MarcellánF, ReichelL. The structure of iterative methods for symmetric linear discrete ill‐posed problems. BIT Numerical Mathematics2014; 54:129-145. · Zbl 1290.65034
[12] NeumanA, ReichelL, SadokH. Implementations of range restricted iterative methods for linear discrete ill‐posed problems. Linear Algebra and Its Applications2012; 436:3974-3990. · Zbl 1241.65045
[13] GolubGH, Van LoanCF. Matrix Computations (4th ed.) Johns Hopkins University Press: Baltimore, 2013. · Zbl 1268.65037
[14] PaigeCC, SaundersMA. An algorithm for sparse linear equations and sparse least squares. ACM Transactions on Mathematical Software1982; 8:43-71. · Zbl 0478.65016
[15] BaglamaJ, ReichelL. Augmented implicitly restarted Lanczos bidiagonalization methods. SIAM Journal on Scientific Computing2005; 27:19-42. · Zbl 1087.65039
[16] BaglamaJ, ReichelL. An implicitly restarted block Lanczos bidiagonalization method using Leja shifts. BIT Numerical Mathematics2013; 53:285-310. · Zbl 1269.65038
[17] HansenPC. Regularization tools version 4.0 for Matlab 7.3. Numerical Algorithms2007; 46:189-194. · Zbl 1128.65029
[18] HankeM. On Lanczos based methods for the regularization of discrete ill‐posed problems. BIT Numerical Mathematics2001; 41:1008-1018.
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.