Rank-revealing factorizations and the singular value decomposition

Authors:
Y. P. Hong and C.-T. Pan

Journal:
Math. Comp. **58** (1992), 213-232

MSC:
Primary 65F05

DOI:
https://doi.org/10.1090/S0025-5718-1992-1106970-4

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 with numerical rank *r*. The bounds derived in this paper that guarantee the existence of RRQR are all of order , in comparison with Chan's . It has been known for some time that if *A* is only numerically rank-one deficient, then the column permutation of *A* that guarantees a small in the QR factorization of 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.

**[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)**

Retrieve articles in *Mathematics of Computation*
with MSC:
65F05

Retrieve articles in all journals with MSC: 65F05

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1992-1106970-4

Keywords:
Singular value decomposition,
rank-revealing QR factorization,
numerical rank,
numerical null space

Article copyright:
© Copyright 1992
American Mathematical Society