Band generalization of the Golub-Kahan bidiagonalization, generalized Jacobi matrices, and the core problem. (English) Zbl 1320.65057
Summary: The concept of the core problem in total least squares (TLS) problems with single right-hand side introduced in [C. C. Paige and Z. Strakos, SIAM J. Matrix Anal. Appl. 27, No. 3, 861–875 (2006; Zbl 1097.15003)] separates necessary and sufficient information for solving the problem from redundancies and irrelevant information contained in the data. It is based on orthogonal transformations such that the resulting problem decomposes into two independent parts. One of the parts has nonzero right-hand side and minimal dimensions and it always has the unique TLS solution. The other part has trivial (zero) right-hand side and maximal dimensions. Assuming exact arithmetic, the core problem can be obtained by the Golub-Kahan bidiagonalization. Extension of the core concept to the multiple right-hand sides case \(AX\approx B\) in [I. Hnětynková et al., SIAM J. Matrix Anal. Appl. 34, No. 3, 917–931 (2013; Zbl 1279.65041)], which is highly nontrivial, is based on application of the singular value decomposition. In this paper we prove that the band generalization of the Golub-Kahan bidiagonalization proposed in this context by Björck also yields the core problem. We introduce generalized Jacobi matrices and investigate their properties. They prove useful in further analysis of the core problem concept. This paper assumes exact arithmetic.
MSC:
| 65F20 | Numerical solutions to overdetermined systems, pseudoinverses |
| 15A21 | Canonical forms, reductions, classification |
| 15A06 | Linear equations (linear algebraic aspects) |
| 15A18 | Eigenvalues, singular values, and eigenvectors |
| 15A24 | Matrix equations and identities |
| 65F25 | Orthogonalization in numerical linear algebra |
Keywords:
total least squares problem; multiple right-hand sides; core problem; Golub-Kahan bidiagonalization; generalized Jacobi matricesReferences:
| [1] | J. L. Barlow, {\it Reorthogonalization for the Golub-Kahan-Lanczos bidiagonal reduction}, Numer. Math., 124 (2013), pp. 237-278. · Zbl 1272.65034 |
| [2] | \rA. Björck, {\it Bidiagonal Decomposition and Least Squares}, Presentation, Canberra, Australia, 2005. |
| [3] | \rA. Björck, {\it A Band-Lanczos Generalization of Bidiagonal Decomposition}, Presentation, Conference in Honor of G. Dahlquist, Stockholm, Sweden, 2006. |
| [4] | \rA. Björck, {\it A band-Lanczos algorithm for least squares and total least squares problems}, in Book of Abstracts of 4th Total Least Squares and Errors-in-Variables Modeling Workshop, Leuven, Katholieke Universiteit Leuven, Leuven, Belgium, 2006, pp, 22-23. |
| [5] | \rA. Björck, {\it Block Bidiagonal Decomposition and Least Squares Problems with Multiple Right-Hand Sides}, manuscript, 2008. |
| [6] | B. Bohnhorst, {\it Beiträge zur Numerischen Behandlung des Unitären Eigenwertproblems}, Ph.D. thesis, Universität Bielefeld, Bielefeld, Germany, 1993. |
| [7] | W. Gautschi, {\it Orthogonal Polynomials, Computation and Approximation}, Oxford University Press, New York, 2004. · Zbl 1130.42300 |
| [8] | A. George and J. W. H. Liu, {\it Computer Solution of Large Sparse Positive Definite Systems}, Prentice-Hall, Englewood Cliffs, NJ, 1981. · Zbl 0516.65010 |
| [9] | G. Golub and W. Kahan, {\it Calculating the singular values and pseudo-inverse of a matrix}, J. Soc. Ind. Appl. Math. Ser. B Numer. Anal., 2 (1965), pp. 205-224. · Zbl 0194.18201 |
| [10] | G. H. Golub and C. F. Van Loan, {\it An analysis of the total least squares problem}, SIAM J. Numer. Anal., 17 (1980), pp. 883-893. · Zbl 0468.65011 |
| [11] | I. Hnětynková, M. Plešinger, D. M. Sima, Z. Strakoš, and S. Van Huffel, {\it The total least squares problem in \(AX≈ B\): A new classification with the relationship to the classical works}, SIAM J. Matrix Anal. Appl., 32 (2011), pp, 748-770. · Zbl 1235.15016 |
| [12] | I. Hnětynková, M. Plešinger, and Z. Strakoš, {\it Lanczos tridiagonalization, Golub-Kahan bidiagonalization and core problem}, Proc. Appl. Math. Mech., 6 (2006), pp, 717-718. · Zbl 1320.65057 |
| [13] | I. Hnětynková, M. Plešinger, and Z. Strakoš, {\it The core problem within a linear approximation problem \(AX≈ B\) with multiple right-hand sides}, SIAM J. Matrix Anal. Appl., 34 (2013), pp, 917-931. · Zbl 1279.65041 |
| [14] | I. Hnětynková and Z. Strakoš, {\it Lanczos tridiagonalization and core problems}, Linear Algebra Appl., 421 (2007), pp, 243-251. · Zbl 1111.65041 |
| [15] | J. Liesen and Z. Strakoš, {\it Krylov Subspace Methods, Principles and Analysis}, Oxford University Press, Oxford, 2013. · Zbl 1263.65034 |
| [16] | C. C. Paige and Z. Strakoš, {\it Core problem in linear algebraic systems}, SIAM J. Matrix Anal. Appl., 27 (2005), pp, 861-875. · Zbl 1097.15003 |
| [17] | B. N. Parlett, {\it The Symmetric Eigenvalue Problem}, Classics Appl. Math. 20, SIAM, Philadelphia, 1998. · Zbl 0885.65039 |
| [18] | M. Plešinger, {\it The Total Least Squares Problem and Reduction of Data in \(AX≈ B\)}, Ph.D. thesis, Technical University of Liberec, Liberec, Czech Republic, 2008. |
| [19] | D. M. Sima, {\it Regularization Techniques in Model Fitting and Parameter Estimation}, Ph.D. thesis, Katholieke Universiteit Leuven, Leuven, Belgium, 2006. |
| [20] | D. M. Sima and S. Van Huffel, {\it Core Problems in \(AX≈ B\)}, Technical report, Department of Electrical Engineering, Katholieke Universiteit Leuven, Leuven, Belgium, 2006. |
| [21] | S. Van Huffel and J. Vandewalle, {\it The Total Least Squares Problem: Computational Aspects and Analysis}, Front. Appl. Math. 9, SIAM, Philadelphia, 1991. · Zbl 0789.62054 |
| [22] | M. Wei, {\it The analysis for the total least squares problem with more than one solution}, SIAM J. Matrix Anal. Appl., 13 (1992), pp, 746-763. · Zbl 0758.65039 |
| [23] | M. Wei, {\it Algebraic relations between the total least squares and least squares problems with more than one solution}, Numer. Math., 62 (1992), pp, 123-148. · Zbl 0761.65030 |
| [24] | J. H. Wilkinson, {\it The Algebraic Eigenvalue Problem}, Clarendon Press, Oxford, England, 1965. · Zbl 0258.65037 |
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.
