Rank-revealing $QR$ factorizations and the singular value decomposition
HTML articles powered by AMS MathViewer
- by Y. P. Hong and C.-T. Pan PDF
- Math. Comp. 58 (1992), 213-232 Request permission
Abstract:
T. Chan has noted that, even when the singular value decomposition of a matrix A is known, it is still not obvious how to find a rank-revealing QR factorization (RRQR) of A if A has numerical rank deficiency. This paper offers a constructive proof of the existence of the RRQR factorization of any matrix A of size $m \times n$ with numerical rank r. The bounds derived in this paper that guarantee the existence of RRQR are all of order $\sqrt {nr}$, in comparison with Chanβs $O({2^{n - r}})$. It has been known for some time that if A is only numerically rank-one deficient, then the column permutation $\Pi$ of A that guarantees a small ${r_{nn}}$ in the QR factorization of $A\Pi$ can be obtained by inspecting the size of the elements of the right singular vector of A corresponding to the smallest singular value of A. To some extent, our paper generalizes this well-known result.References
-
N. Anderson and I. Karasalo, On computing bounds for the least singular value of a triangular matrix, BIT 15 (1975), 1-4.
- Christian H. Bischof and Per Christian Hansen, Structure-preserving and rank-revealing $\textrm {QR}$-factorizations, SIAM J. Sci. Statist. Comput. 12 (1991), no.Β 6, 1332β1350. MR 1129650, DOI 10.1137/0912073
- Peter Businger and Gene H. Golub, Handbook series linear algebra. Linear least squares solutions by Householder transformations, Numer. Math. 7 (1965), 269β276. MR 176590, DOI 10.1007/BF01436084
- Tony F. Chan, Deflated decomposition of solutions of nearly singular systems, SIAM J. Numer. Anal. 21 (1984), no.Β 4, 738β754. MR 749368, DOI 10.1137/0721050 β, Alternative to the SVD: rank revealing QR-factorizations, Advanced Algorithms and Architectures for Signal Processing (J. M. Speiser, ed.), SPIE Proceedings, vol. 696, 1986.
- Tony F. Chan, Rank revealing $QR$ factorizations, Linear Algebra Appl. 88/89 (1987), 67β82. MR 882441, DOI 10.1016/0024-3795(87)90103-0
- Tony F. Chan and Per Christian Hansen, Computing truncated singular value decomposition least squares solutions by rank revealing $QR$-factorizations, SIAM J. Sci. Statist. Comput. 11 (1990), no.Β 3, 519β530. MR 1047209, DOI 10.1137/0911029
- Leslie V. Foster, Rank and null space calculations using matrix decomposition without column interchanges, Linear Algebra Appl. 74 (1986), 47β71. MR 822139, DOI 10.1016/0024-3795(86)90115-1
- G. Golub, Numerical methods for solving linear least squares problems, Numer. Math. 7 (1965), 206β216. MR 181094, DOI 10.1007/BF01436075 G. H. Golub, V. Klema, and G. W. Stewart, Rank degeneracy and least squares problems, Report TR-456, Dept. of Computer Science, Univ. of Maryland, 1976.
- Gene H. Golub and Charles F. Van Loan, Matrix computations, 2nd ed., Johns Hopkins Series in the Mathematical Sciences, vol. 3, Johns Hopkins University Press, Baltimore, MD, 1989. MR 1002570
- Charles L. Lawson and Richard J. Hanson, Solving least squares problems, Prentice-Hall Series in Automatic Computation, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1974. MR 0366019
- Roger A. Horn and Charles R. Johnson, Matrix analysis, Cambridge University Press, Cambridge, 1985. MR 832183, DOI 10.1017/CBO9780511810817 W. Kahan, Numerical linear algebra, Canad. Math. Bull. 9 (1966), 757-801.
- Ilkka Karasalo, A criterion for truncation of the $QR$-decomposition algorithm for the singular linear least squares problem, Nordisk Tidskr. Informationsbehandling (BIT) 14 (1974), 156β166. MR 483361, DOI 10.1007/bf01932945
- Thomas A. Manteuffel, An interval analysis approach to rank determination in linear least squares problems, SIAM J. Sci. Statist. Comput. 2 (1981), no.Β 3, 335β348. MR 632904, DOI 10.1137/0902027 E. Ng, A scheme for handling rank deficiency in the solution of sparse linear least squares problems, Report ORNL/TM-10980, Mathematics Division, Oak Ridge National Laboratory, 1988.
- G. W. Stewart, On the implicit deflation of nearly singular systems of linear equations, SIAM J. Sci. Statist. Comput. 2 (1981), no.Β 2, 136β140. MR 622710, DOI 10.1137/0902011
- G. W. Stewart, Rank degeneracy, SIAM J. Sci. Statist. Comput. 5 (1984), no.Β 2, 403β413. MR 740857, DOI 10.1137/0905030 β, Incremental condition calculation and column selection, Report CS-TR-2495, Dept. of Computer Science, Univ. of Maryland, 1990.
- Sabine Van Huffel, Joos Vandewalle, and Ann Haegemans, An efficient and reliable algorithm for computing the singular subspace of a matrix, associated with its smallest singular values, J. Comput. Appl. Math. 19 (1987), no.Β 3, 313β330. MR 907802, DOI 10.1016/0377-0427(87)90201-9
Additional Information
- © Copyright 1992 American Mathematical Society
- Journal: Math. Comp. 58 (1992), 213-232
- MSC: Primary 65F05
- DOI: https://doi.org/10.1090/S0025-5718-1992-1106970-4
- MathSciNet review: 1106970