The DOI matches its Crossref record; 24 of the 24 references it cites were found in a registry or an index.
Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
Abstract
Given an $m \times n$ matrix M with $m \geqslant n$, it is shown that there exists a permutation $\Pi $ and an integer k such that the QR factorization \[ M\Pi = Q\left( {\begin{array}{*{20}c} {A_k } & {B_k } \\ {} & {C_k } \\ \end{array} } \right) \] reveals the numerical rank of M: the $k \times k$ upper-triangular matrix $A_k $ is well conditioned, $\|C_k \|_2 $ is small, and $B_k $is linearly dependent on $A_k $ with coefficients bounded by a low-degree polynomial in n. Existing rank-revealing QR (RRQR) algorithms are related to such factorizations and two algorithms are presented for computing them. The new algorithms are nearly as efficient as QR with column pivoting for most problems and take $O(mn^2 )$ floating-point operations in the worst case.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Horn, R. A., & Johnson, C. R. (1991) · Cambridge University Press eBooks · doi:10.1017/cbo9780511840371 · Cited by 9,319
Solving Least Squares Problems
Lawson, C. L., & Hanson, R. J. (1995) · doi:10.1137/1.9781611971217 · Cited by 7,103
Wold, S., Ruhe, A., Wold, H., & Dunn, III (1984) · SIAM Journal on Scientific and Statistical Computing · doi:10.1137/0905052 · Cited by 2,529
Introduction to matrix computations
Stewart, G. W. (1973) · International Linear Collider · Cited by 2,381
Numerical methods for solving linear least squares problems
Golub, G. (1965) · Numerische Mathematik · doi:10.1007/bf01436075 · Cited by 849
Methods for modifying matrix factorizations
Gill, P. E., Golub, G. H., Murray, W., & Saunders, M. A. (1974) · Mathematics of Computation · doi:10.1090/s0025-5718-1974-0343558-6 · Cited by 590
Rank revealing QR factorizations
Chan, T. F. (1987) · Linear Algebra and its Applications · doi:10.1016/0024-3795(87)90103-0 · Cited by 521
Linear least squares solutions by householder transformations
Businger, P., & Golub, G. H. (1965) · Numerische Mathematik · doi:10.1007/bf01436084 · Cited by 508
An updating algorithm for subspace tracking
Stewart, G. W. (1992) · IEEE Transactions on Signal Processing · doi:10.1109/78.139256 · Cited by 326
Kahan, W. (1966) · Canadian Mathematical Bulletin · doi:10.4153/cmb-1966-083-2 · Cited by 198
Rank degeneracy and least squares problems
Golub, G. H., Klema, V. C., & Stewart, G. W. (1976) · Cited by 175
Some Applications of the Rank Revealing QR Factorization
Chan, T. F.-C., & Hansen, P. C. (1992) · SIAM Journal on Scientific and Statistical Computing · doi:10.1137/0913043 · Cited by 158
On Rank-Revealing Factorisations
Chandrasekaran, S., & Ipsen, I. C. F. (1994) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/s0895479891223781 · Cited by 155
Rank-revealing 𝑄𝑅 factorizations and the singular value decomposition
Hong, Y., & Pan, C.-T. (1992) · Mathematics of Computation · doi:10.1090/s0025-5718-1992-1106970-4 · Cited by 146
An improved algorithm for the computation of Kronecker's canonical form of a singular pencil
Beelen, T., & Dooren, P. M. V. (1988) · Linear Algebra and its Applications · doi:10.1016/0024-3795(88)90003-1 · Cited by 145
Rank and null space calculations using matrix decomposition without column interchanges
Foster, L. V. (1986) · Linear Algebra and its Applications · doi:10.1016/0024-3795(86)90115-1 · Cited by 130
Bischof, C. H., & Shroff, G. M. (1992) · IEEE Transactions on Signal Processing · doi:10.1109/78.157185 · Cited by 100
Chan, T. F.-C., & Hansen, P. C. (1990) · SIAM Journal on Scientific and Statistical Computing · doi:10.1137/0911029 · Cited by 96
On the existence and computation of 𝐿𝑈-factorizations with small pivots
Chan, T. F.-C. (1984) · Mathematics of Computation · doi:10.1090/s0025-5718-1984-0736451-4 · Cited by 59
Stewart, G. W. (1984) · SIAM Journal on Scientific and Statistical Computing · doi:10.1137/0905030 · Cited by 56
Structure-Preserving and Rank-Revealing QR-Factorizations
Bischof, C. H., & Hansen, P. C. (1991) · SIAM Journal on Scientific and Statistical Computing · doi:10.1137/0912073 · Cited by 47
AB-Algorithm and its modifications for the spectral problems of linear pencils of matrices
Kublanovskaya, V. N. (1984) · Numerische Mathematik · doi:10.1007/bf01390177 · Cited by 43
Analysis of a QR Algorithm for Computing Singular Values
Chandrasekaran, S., & Ipsen, I. C. F. (1995) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/s0895479892236532 · Cited by 33
A block algorithm for computing rank-revealing QR factorizations
Bischof, C. H., & Hansen, P. C. (1992) · Numerical Algorithms · doi:10.1007/bf02139475 · Cited by 17
Cited by
Halko, N., Martinsson, P. G., & Tropp, J. A. (2011) · SIAM Review · doi:10.1137/090771806 · Cited by 4,002
Fast Direct Methods for Gaussian Processes
Ambikasaran, S., Foreman-Mackey, D., Greengard, L., Hogg, D. W., & O'Neil, M. (2016) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2015.2448083 · Cited by 669
Randomized algorithms for the low-rank approximation of matrices
Liberty, E., Woolfe, F., Martinsson, P.-G., Rokhlin, V., & Tygert, M. (2007) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0709640104 · Cited by 559
Coifman, R. R., & Maggioni, M. (2006) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2006.04.004 · Cited by 491
Relative-Error $CUR$ Matrix Decompositions
Drineas, P., Mahoney, M. W., & Muthukrishnan, S. (2008) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/07070471x · Cited by 461
Metadata
- Authors
- Gu, M., & Eisenstat, S. C.
- Venue
- SIAM Journal on Scientific Computing
- Published
- 1996-07
- Volume
- 17
- Issue
- 4
- Pages
- 848-869
- ISSN
- 1064-8275 (ISSN-L)
- 1095-7197
- OpenAlex
- W2119233169
- Cited by
- 677
- References
- 24
- FWCI
- 4.12
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.