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

MathSciNet review:
1106970

Full-text PDF Free Access

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]**Christian H. Bischof and Per Christian Hansen,*Structure-preserving and rank-revealing 𝑄𝑅-factorizations*, SIAM J. Sci. Statist. Comput.**12**(1991), no. 6, 1332–1350. MR**1129650**, 10.1137/0912073**[3]**Peter Businger and Gene H. Golub,*Handbook series linear algebra. Linear least squares solutions by Householder transformations*, Numer. Math.**7**(1965), 269–276. MR**0176590****[4]**Tony F. Chan,*Deflated decomposition of solutions of nearly singular systems*, SIAM J. Numer. Anal.**21**(1984), no. 4, 738–754. MR**749368**, 10.1137/0721050**[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]**Tony F. Chan,*Rank revealing 𝑄𝑅 factorizations*, Linear Algebra Appl.**88/89**(1987), 67–82. MR**882441**, 10.1016/0024-3795(87)90103-0**[7]**Tony F. Chan and Per Christian Hansen,*Computing truncated singular value decomposition least squares solutions by rank revealing 𝑄𝑅-factorizations*, SIAM J. Sci. Statist. Comput.**11**(1990), no. 3, 519–530. MR**1047209**, 10.1137/0911029**[8]**Leslie V. Foster,*Rank and null space calculations using matrix decomposition without column interchanges*, Linear Algebra Appl.**74**(1986), 47–71. MR**822139**, 10.1016/0024-3795(86)90115-1**[9]**G. Golub,*Numerical methods for solving linear least squares problems*, Numer. Math.**7**(1965), 206–216. MR**0181094****[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]**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****[12]**Charles L. Lawson and Richard J. Hanson,*Solving least squares problems*, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1974. Prentice-Hall Series in Automatic Computation. MR**0366019****[13]**Roger A. Horn and Charles R. Johnson,*Matrix analysis*, Cambridge University Press, Cambridge, 1985. MR**832183****[14]**W. Kahan,*Numerical linear algebra*, Canad. Math. Bull.**9**(1966), 757-801.**[15]**Ilkka Karasalo,*A criterion for truncation of the 𝑄𝑅-decomposition algorithm for the singular linear least squares problem*, Nordisk Tidskr. Informationsbehandling (BIT)**14**(1974), 156–166. MR**0483361****[16]**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**, 10.1137/0902027**[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), no. 2, 136–140. MR**622710**, 10.1137/0902011**[19]**G. W. Stewart,*Rank degeneracy*, SIAM J. Sci. Statist. Comput.**5**(1984), no. 2, 403–413. MR**740857**, 10.1137/0905030**[20]**-,*Incremental condition calculation and column selection*, Report CS-TR-2495, Dept. of Computer Science, Univ. of Maryland, 1990.**[21]**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**, 10.1016/0377-0427(87)90201-9

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