Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Rank-revealing $ QR$ factorizations and the singular value decomposition

Authors: Y. P. Hong and C.-T. Pan
Journal: Math. Comp. 58 (1992), 213-232
MSC: Primary 65F05
MathSciNet review: 1106970
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] N. Anderson and I. Karasalo, On computing bounds for the least singular value of a triangular matrix, BIT 15 (1975), 1-4.
  • [2] C. H. Bischof and P. C. Hansen, Structure-preserving and rank-revealing QR factorizations, Report MCS-P100-0989, Mathematics and Computer Science Division, Argonne National Laboratory, 1989. (To appear in SIAM J. Sci. Statist. Comput.) MR 1129650 (92i:65080)
  • [3] P. Businger and G. H. Golub, Linear least squares solutions by Householder transformations, Numer. Math. 1 (1965), 269-276. MR 0176590 (31:862)
  • [4] T. F. Chan, Deflated decomposition of solutions of nearly singular systems, SIAM J. Numer. Anal. 21 (1984), 738-754. MR 749368 (86a:65029)
  • [5] -, Alternative to the SVD: rank revealing QR-factorizations, Advanced Algorithms and Architectures for Signal Processing (J. M. Speiser, ed.), SPIE Proceedings, vol. 696, 1986.
  • [6] -, Rank revealing QR factorizations, Linear Algebra Appl. 88/89 (1987), 67-82. MR 882441 (88c:15011)
  • [7] T. F. Chan and P. C. Hansen, Computing truncated singular value decomposition least squares solutions by rank revealing QR-factorizations, SIAM J. Sci. Statist. Comput. 11 (1990), 519-530. MR 1047209 (91e:65059)
  • [8] L. Foster, Rank and null space calculations using matrix decomposition without column interchanges, Linear Algebra Appl. 74 (1986), 47-71. MR 822139 (87f:65052)
  • [9] G. H. Golub, Numerical methods for solving least squares problems, Numer. Math. 7 (1965), 206-216. MR 0181094 (31:5323)
  • [10] 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.
  • [11] G. H. Golub and C. F. Van Loan, Matrix computations, 2nd ed., John Hopkins Univ. Press, 1989. MR 1002570 (90d:65055)
  • [12] R. J. Hanson and C. L. Lawson, Solving least squares problems, Prentice-Hall, 1974. MR 0366019 (51:2270)
  • [13] R. A. Horn and C. A. Johnson, Matrix analysis, Cambridge Univ. Press, 1985. MR 832183 (87e:15001)
  • [14] W. Kahan, Numerical linear algebra, Canad. Math. Bull. 9 (1966), 757-801.
  • [15] I. Karasalo, A criterion for truncation of the QR-decomposition algorithm for the singular linear least squares problem, BIT 14 (1974), 156-166. MR 0483361 (58:3372)
  • [16] T. Manteuffel, An interval analysis approach to rank determination in linear least squares problems, SIAM J. Sci. Statist. Comput. 2 (1981), 335-348. MR 632904 (82m:65042)
  • [17] 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.
  • [18] G. W. Stewart, On the implicit deflation of nearly singular systems of linear equations, SIAM J. Sci. Statist. Comput. 2 (1981), 136-140. MR 622710 (82f:65030)
  • [19] -, Rank degeneracy, SIAM J. Sci. Statist. Comput. 5 (1984), 403-413. MR 740857 (85h:65086)
  • [20] -, Incremental condition calculation and column selection, Report CS-TR-2495, Dept. of Computer Science, Univ. of Maryland, 1990.
  • [21] S. Van Huffel, J. Vandewalle, and A. 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), 313-330. MR 907802 (89c:65051)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65F05

Retrieve articles in all journals with MSC: 65F05

Additional Information

Keywords: Singular value decomposition, rank-revealing QR factorization, numerical rank, numerical null space
Article copyright: © Copyright 1992 American Mathematical Society

American Mathematical Society