# zbMATH — the first resource for mathematics

An implicit shift bidiagonalization algorithm for ill-posed systems. (English) Zbl 0821.65023
Iterative methods based on Lanczos bidiagonalization (LBD) with full reorthogonalization are considered for solving large scale discrete ill- posed linear least squares problems of the form $$\min_ x \| Ax - b \|_ 2$$. Section 1 discusses the use of generalized cross-validation to estimate the optimal regularization of an LBD solution when the noise level is unknown. Section 4 studies the implicitly restarted LBD method. Section 5 explores the use of implicit restarts in the context of determining regularization parameters for the LBD, and presents some numerical examples to demonstrate their efficiency.

##### MSC:
 65F20 Numerical solutions to overdetermined systems, pseudoinverses 65F10 Iterative numerical methods for linear systems
##### Software:
eigs; LSQR; Regularization tools
Full Text:
##### References:
 [1] Å. Björck,A bidiagonalization algorithm for solving large and sparse ill-posed systems of linear equations, BIT, 28 (1988), pp. 659–670. · Zbl 0658.65041 · doi:10.1007/BF01941141 [2] Å. Björck,Numerical Methods for Least Squares Methods, Frontier in Applied Mathematics series. SIAM, Philadelphia, to appear. · Zbl 0847.65023 [3] H. Brakhage,On ill-posed problems and the method of conjugate gradients, in Inverse and Ill-posed Problems, H. W. Engl, C. W. Groetsch, eds., Academic Press, Boston, New York, London, 1987, pp. 165–175. · Zbl 0642.65042 [4] D. Calvetti, L. Reichel, and D. C. Sorenson,An implicitly restarted Lanczos method for large symmetric eigenvalue problems, Elect. Trans. Numer. Anal., 2 (1994), pp. 1–21. · Zbl 0809.65030 [5] J. Demmel and W. Kahan,Accurate singular values of bidiagonal matrices, SIAM J. Sci. Statist. Comput., 11 (1990), pp. 873–912. · Zbl 0705.65027 · doi:10.1137/0911052 [6] D. A. Girard,A fast ’Monte-Carlo Cross-Validation’ procedure for large least squares problems with noisy data, Numer. Math. 56 (1989), pp. 1–23. · Zbl 0665.65010 · doi:10.1007/BF01395775 [7] G. H. Golub, M. T. Heath, and G. Wahba,Generalized cross-validation as a method for choosing a good ridge parameter, Technometrics, 21 (1979), pp. 215–223. · Zbl 0461.62059 · doi:10.2307/1268518 [8] G. H. Golub and W. Kahan,Calculating the singular values and pseudo-inverse of a matrix, SIAM J. Numer Anal. Ser. B, 2 (1965), pp. 205–224. · Zbl 0194.18201 · doi:10.1137/0702016 [9] G. H. Golub, F. T. Luk, and M. L. Overton,A block Lanczos method for computing the singular values and singular vectors of a matrix, ACM Trans. on Math. Soft., 7 (1981), pp. 149–169. · Zbl 0466.65022 · doi:10.1145/355945.355946 [10] G. H. Golub and C. F. Van Loan,Matrix Computations, The Johns Hopkins University Press, Baltimore, second edition, 1989. · Zbl 0733.65016 [11] M. Hanke,Accelerated Landweber iterations for the solution of ill-posed equations, Numer. Math. 60 (1991), pp. 341–373. · Zbl 0745.65038 · doi:10.1007/BF01385727 [12] M. Hanke and P. C. Hansen,Regularization methods for large-scale problems, Surveys on Mathematics for Industry, 3 (1994), pp. 253–315. · Zbl 0805.65058 [13] P. C. Hansen,Analysis of discrete ill-posed problems by means of the L-curve, SIAM Review, 34 (1992), pp. 561–580. · Zbl 0770.65026 · doi:10.1137/1034115 [14] P. C. Hansen,Regularization tools: a MATLAB package for analysis and solution of discrete ill-posed problems, Numerical Algorithms, 6 (1994), pp. 1–36. · Zbl 0789.65029 · doi:10.1007/BF02149761 [15] A. K. Louis,Convergence of the conjugate gradient method for compact operators, in Inverse and Ill-Posed Problems, H. W. Engl, C. W. Groetsch, eds., Academic Press, Boston, New York, London, 1987, pp. 177–183. [16] D. P. O’Leary and J. A. Simmons,A bidiagonalization-regularization porcedure for large scale discretizations of ill-posed problems, SIAM J. Sci. Statist. Comput., 2 (1981), pp. 474–489. · Zbl 0469.65089 · doi:10.1137/0902037 [17] C. C. Paige,Error analysis of the Lanczos algorithm for tridiagonalizing a symmetric matrix, J. Inst. Math. Applics., 18 (1976), pp. 341–349. · Zbl 0347.65018 · doi:10.1093/imamat/18.3.341 [18] C. C. Paige and M. A. Saunders,LSQR an algorithm for sparse linear equations and sparse least squares, ACM Trans. Math. Software, 8 (1982), pp. 43–71. · Zbl 0478.65016 · doi:10.1145/355984.355989 [19] D. Sorenson,Implicit application of polynomial filters in a k-step Arnoldi method, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 357–385. · Zbl 0763.65025 · doi:10.1137/0613025 [20] C. R. Vogel and J. G. Wade,Iterative SVD-based methods for ill-posed problems, SIAM J. Sci. Statist. Comput., 15 (1994), pp. 736–754. · Zbl 0802.65070 · doi:10.1137/0915047 [21] G. Wahba,Spline Models for Observational Data, SIAM, CBMS 59, 1990. · Zbl 0813.62001 [22] J. M. Varah,A practical examination of some numerical methods for linear discrete ill-posed problems, SIAM Review, 21 (1979), pp. 100–111. · Zbl 0406.65015 · doi:10.1137/1021007
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.