Truncated singular value decomposition (TSVD) and Golub-Kahan diagonalization are two elementary techniques for solving a least squares problem from a linear discrete ill-posed problems. For small to medium sized ill-posed problems, we propose a novel Modified Truncated Singular Value Decomposition (NMTSVD) based on the MTSVD method. This method presents three approaches to select truncation indices, leading to three approximate matrices of the coefficient matrix
. And the relationships of these approximate matrices are established in terms of the spectral condition number. For large-scale unstable discrete ill-posed problems, we propose a truncated Reorthogonalized Golub-Kahan Bidiagonalization (RGKB) method by integrating the Golub-Kahan bidiagonalization process, truncation index, and the Gram-Schmidt reorthogonalization procedure. Numerical experiments are presented to illustrate the effectiveness of the methods NMTSVD and RGKB.
References
[1]
Björck, Å. (1988) A Bidiagonalization Algorithm for Solving Large and Sparse Ill-Posed Systems of Linear Equations. BIT, 28, 659-670. https://doi.org/10.1007/bf01941141
[2]
Lawson, C.L. and Hanson, R.J. (1974) Solving Least Squares Problems, Classics in Applied Mathematics, Series Number 15. Prentice-Hall Inc.
[3]
Noschese, S. and Reichel, L. (2016) Some Matrix Nearness Problems Suggested by Tikhonov Regularization. LinearAlgebraanditsApplications, 502, 366-386. https://doi.org/10.1016/j.laa.2015.04.008
[4]
Golub, G.H., Hansen, P.C. and O'Leary, D.P. (1999) Tikhonov Regularization and Total Least Squares. SIAMJournalonMatrixAnalysisandApplications, 21, 185-194. https://doi.org/10.1137/s0895479897326432
[5]
Hansen, P.C. (1990) Truncated Singular Value Decomposition Solutions to Discrete Ill-Posed Problems with Ill-Determined Numerical Rank. SIAMJournalonScientificandStatisticalComputing, 11, 503-518. https://doi.org/10.1137/0911028
[6]
Bauer, F. and Lukas, M.A. (2011) Comparingparameter Choice Methods for Regularization of Ill-Posed Problems. MathematicsandComputersinSimulation, 81, 1795-1841. https://doi.org/10.1016/j.matcom.2011.01.016
[7]
Calvetti, D., Lewis, B. and Reichel, L. (2002) GMRES, L-Curves, and Discrete Ill-Posed Problems. BITNumericalMathematics, 42, 44-65. https://doi.org/10.1023/a:1021918118380
[8]
Golub, G.H., Heath, M. and Wahba, G. (1979) Generalized Cross-Validation as a Method for Choosing a Good Ridge Parameter. Technometrics, 21, 215-223. https://doi.org/10.1080/00401706.1979.10489751
[9]
Kilmer, M.E. and O'Leary., D.P. (2001) Choosing Regularization Parameters in Iterative Methods for Ill-Posed Problems. SIAMJournalonMatrixAnalysisandApplications, 22, 1204-1221. https://doi.org/10.1137/s0895479899345960
[10]
Brezinski, C., Redivo-Zaglia, M., Rodriguez, G. and Seatzu, S. (1998) Extrapolation Techniques for Ill-Conditioned Linear Systems. NumerischeMathematik, 81, 1-29. https://doi.org/10.1007/s002110050382
[11]
Reichel, L. and Shyshkov, A. (2008) A New Zero-Finder for Tikhonov Regularization. BITNumericalMathematics, 48, 627-643. https://doi.org/10.1007/s10543-008-0179-7
[12]
Reichel, L. and Rodriguez, G. (2012) Old and New Parameter Choice Rules for Discrete Ill-Posed Problems. NumericalAlgorithms, 63, 65-87. https://doi.org/10.1007/s11075-012-9612-8
[13]
Li, Z., Huang, H. and Wei, Y. (2011) Ill-Conditioning of the Truncated Singular Value Decomposition, Tikhonov Regularization and Their Applications to Numerical Partial Differential Equations. NumericalLinearAlgebrawithApplications, 18, 205-221. https://doi.org/10.1002/nla.766
[14]
Hansen, P.C. (1990) The Discrete Picard Condition for Discrete Ill-Posed Problems. BIT, 30, 658-672. https://doi.org/10.1007/bf01933214
[15]
Morigi, S., Reichel, L. and Sgallari, F. (2007) A Truncated Projected SVD Method for Linear Discrete Ill-Posed Problems. NumericalAlgorithms, 43, 197-213. https://doi.org/10.1007/s11075-006-9053-3
[16]
Noschese, S. and Reichel, L. (2014) A Modified Truncated Singular Value Decomposition Method for Discrete Ill-Posed Problems. NumericalLinearAlgebrawithApplications, 21, 813-822. https://doi.org/10.1002/nla.1938
[17]
Jia, Z. and Yang, Y. (2018) Modified Truncated Randomized Singular Value Decomposition (MTRSVD) Algorithms for Large Scale Discrete Ill-Posed Problems with General-Form Regularization. InverseProblems, 34, Article ID: 055013. https://doi.org/10.1088/1361-6420/aab92d
[18]
Hanke, M. and Groetsch, C.W. (1998) Nonstationary Iterated Tikhonov Regularization. JournalofOptimizationTheoryandApplications, 98, 37-53. https://doi.org/10.1023/a:1022680629327
[19]
Hansen, P.C. and O’Leary, D.P. (1993) The Use of the L-Curve in the Regularization of Discrete Ill-Posed Problems. SIAMJournalonScientificComputing, 14, 1487-1503. https://doi.org/10.1137/0914086
[20]
Huang, G., Reichel, L. and Yin, F. (2015) On the Choice of Solution Subspace for Nonstationary Iterated Tikhonov Regularization. NumericalAlgorithms, 72, 1043-1063. https://doi.org/10.1007/s11075-015-0079-2
[21]
Novati, P. and Russo, M.R. (2013) A GCV Based Arnoldi-Tikhonov Regularization Method. BITNumericalMathematics, 54, 501-521. https://doi.org/10.1007/s10543-013-0447-z
[22]
Gazzola, S., Novati, P. and Russo, M.R. (2015) On Krylov Projection Methods and Tikhonov Regularization. Electronic Transactions on Numerical Analysis, 44, 83-123.
[23]
Gazzola, S. (2014) Regularization Techniques Based on Krylov Methods for Ill-Posed Linear Systems. Ph.D. Thesis, University of Padua.
Daniel, J.W., Gragg, W.B., Kaufman, L. and Stewart, G.W. (1976) Reorthogonalization and Stable Algorithms for Updating the Gram-Schmidt QR Factorization. MathematicsofComputation, 30, 772-795. https://doi.org/10.1090/s0025-5718-1976-0431641-8
[26]
Paige, C.C. (1971) The Computation of Eigenvalues and Eigenvectors of Very Large Sparse Matrices. Ph.D. Thesis, University of London.
[27]
Parlett, B.N. and Scott, D.S. (1979) The Lanczos Algorithm with Selective Orthogonalization. MathematicsofComputation, 33, 217-238. https://doi.org/10.1090/s0025-5718-1979-0514820-3
[28]
Barlow, J.L. (2013) Reorthogonalization for the Golub-Kahan-Lanczos Bidiagonal Reduction. NumerischeMathematik, 124, 237-278. https://doi.org/10.1007/s00211-013-0518-8
[29]
Alqahtani, A., Ramlau, R. and Reichel, L. (2022) Error Estimates for Golub-Kahan Bidiagonalization with Tikhonov Regularization for Ill-Posed Operator Equations. InverseProblems, 39, Article ID: 025002. https://doi.org/10.1088/1361-6420/aca754
[30]
Bianchi, D. and Donatelli, M. and Furchi, D. and Reichel, L. (2025) The Iterated Golub-Kahan-Tikhonov Method. arXiv: 2507.12307.
[31]
Hansen, P.C. (2007) Regularization Tools Version 4.0 for Matlab 7.3. NumericalAlgorithms, 46, 189-194. https://doi.org/10.1007/s11075-007-9136-9
