Rankrevealing factorizations and the singular value decomposition
Authors:
Y. P. Hong and C.T. Pan
Journal:
Math. Comp. 58 (1992), 213232
MSC:
Primary 65F05
MathSciNet review:
1106970
Fulltext 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 rankrevealing 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 rankone 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 wellknown result.
 [1]
N. Anderson and I. Karasalo, On computing bounds for the least singular value of a triangular matrix, BIT 15 (1975), 14.
 [2]
Christian
H. Bischof and Per
Christian Hansen, Structurepreserving and rankrevealing
𝑄𝑅factorizations, SIAM J. Sci. Statist. Comput.
12 (1991), no. 6, 1332–1350. MR 1129650
(92i:65080), http://dx.doi.org/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
(31 #862)
 [4]
Tony
F. Chan, Deflated decomposition of solutions of nearly singular
systems, SIAM J. Numer. Anal. 21 (1984), no. 4,
738–754. MR
749368 (86a:65029), http://dx.doi.org/10.1137/0721050
 [5]
, Alternative to the SVD: rank revealing QRfactorizations, 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
(88c:15011), http://dx.doi.org/10.1016/00243795(87)901030
 [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
(91e:65059), http://dx.doi.org/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
(87f:65052), http://dx.doi.org/10.1016/00243795(86)901151
 [9]
G.
Golub, Numerical methods for solving linear 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 TR456, 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
(90d:65055)
 [12]
Charles
L. Lawson and Richard
J. Hanson, Solving least squares problems, PrenticeHall Inc.,
Englewood Cliffs, N.J., 1974. PrenticeHall Series in Automatic
Computation. MR
0366019 (51 #2270)
 [13]
Roger
A. Horn and Charles
R. Johnson, Matrix analysis, Cambridge University Press,
Cambridge, 1985. MR 832183
(87e:15001)
 [14]
W. Kahan, Numerical linear algebra, Canad. Math. Bull. 9 (1966), 757801.
 [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
(58 #3372)
 [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
(82m:65042), http://dx.doi.org/10.1137/0902027
 [17]
E. Ng, A scheme for handling rank deficiency in the solution of sparse linear least squares problems, Report ORNL/TM10980, 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
(82f:65030), http://dx.doi.org/10.1137/0902011
 [19]
G.
W. Stewart, Rank degeneracy, SIAM J. Sci. Statist. Comput.
5 (1984), no. 2, 403–413. MR 740857
(85h:65086), http://dx.doi.org/10.1137/0905030
 [20]
, Incremental condition calculation and column selection, Report CSTR2495, 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 (89c:65051), http://dx.doi.org/10.1016/03770427(87)902019
 [1]
 N. Anderson and I. Karasalo, On computing bounds for the least singular value of a triangular matrix, BIT 15 (1975), 14.
 [2]
 C. H. Bischof and P. C. Hansen, Structurepreserving and rankrevealing QR factorizations, Report MCSP1000989, 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), 269276. MR 0176590 (31:862)
 [4]
 T. F. Chan, Deflated decomposition of solutions of nearly singular systems, SIAM J. Numer. Anal. 21 (1984), 738754. MR 749368 (86a:65029)
 [5]
 , Alternative to the SVD: rank revealing QRfactorizations, 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), 6782. MR 882441 (88c:15011)
 [7]
 T. F. Chan and P. C. Hansen, Computing truncated singular value decomposition least squares solutions by rank revealing QRfactorizations, SIAM J. Sci. Statist. Comput. 11 (1990), 519530. MR 1047209 (91e:65059)
 [8]
 L. Foster, Rank and null space calculations using matrix decomposition without column interchanges, Linear Algebra Appl. 74 (1986), 4771. MR 822139 (87f:65052)
 [9]
 G. H. Golub, Numerical methods for solving least squares problems, Numer. Math. 7 (1965), 206216. MR 0181094 (31:5323)
 [10]
 G. H. Golub, V. Klema, and G. W. Stewart, Rank degeneracy and least squares problems, Report TR456, 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, PrenticeHall, 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), 757801.
 [15]
 I. Karasalo, A criterion for truncation of the QRdecomposition algorithm for the singular linear least squares problem, BIT 14 (1974), 156166. 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), 335348. MR 632904 (82m:65042)
 [17]
 E. Ng, A scheme for handling rank deficiency in the solution of sparse linear least squares problems, Report ORNL/TM10980, 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), 136140. MR 622710 (82f:65030)
 [19]
 , Rank degeneracy, SIAM J. Sci. Statist. Comput. 5 (1984), 403413. MR 740857 (85h:65086)
 [20]
 , Incremental condition calculation and column selection, Report CSTR2495, 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), 313330. 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
DOI:
http://dx.doi.org/10.1090/S00255718199211069704
PII:
S 00255718(1992)11069704
Keywords:
Singular value decomposition,
rankrevealing QR factorization,
numerical rank,
numerical null space
Article copyright:
© Copyright 1992 American Mathematical Society
