Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

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
Similar Articles
  • Retrieve articles in Mathematics of Computation with MSC: 65F05
  • Retrieve articles in all journals with MSC: 65F05
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