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
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
A Randomized Algorithm for Principal Component Analysis
Rokhlin, V., Szlam, A., & Tygert, M. (2010) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/080736417 · Cited by 422
Randomized Algorithms for Matrices and Data
MAHONEY, M. (2012) · Chapman & Hall/CRC Data Mining and Knowledge Discovery Series · doi:10.1201/b11822-37 · Cited by 409
See all by looking at a few: Sparse modeling for finding representative objects
Elhamifar, E., Sapiro, G., & Vidal, R. (2012) · 2012 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2012.6247852 · Cited by 394
Structured Pruning for Deep Convolutional Neural Networks: A Survey
He, Y., & Xiao, L. (2024) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2023.3334614 · Cited by 363
A randomized algorithm for the decomposition of matrices
Martinsson, P.-G., Rokhlin, V., & Tygert, M. (2011) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2010.02.003 · Cited by 352
On the Compression of Low Rank Matrices
Cheng, H., Gimbutas, Z., Martinsson, P. G., & Rokhlin, V. (2005) · SIAM Journal on Scientific Computing · doi:10.1137/030602678 · Cited by 301
Randomized numerical linear algebra: Foundations and algorithms
Martinsson, P.-G., & Tropp, J. A. (2020) · Acta Numerica · doi:10.1017/s0962492920000021 · Cited by 300
An improved approximation algorithm for the column subset selection problem
Boutsidis, C., Mahoney, M. W., & Petros Drineas, B. (2009) · doi:10.5555/1496770.1496875 · Cited by 286
A fast randomized algorithm for the approximation of matrices
Woolfe, F., Liberty, E., Rokhlin, V., & Tygert, M. (2008) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2007.12.002 · Cited by 280
A Randomized Algorithm for the Approximation of Matrices
Martinsson, P.-G., Rockhlin, V., & Tygert, M. (2006) · doi:10.21236/ada458932 · Cited by 268
Sparse Polynomial Chaos Expansions: Literature Survey and Benchmark
Lüthen, N., Marelli, S., & Sudret, B. (2021) · SIAM/ASA Journal on Uncertainty Quantification · doi:10.1137/20m1315774 · Cited by 256
Subset Selection Algorithms: Randomized vs. Deterministic
Broadbent, M., Brown, M., & Penner, K. (2010) · SIAM Undergraduate Research Online · doi:10.1137/09s010435 · Cited by 32
Constrained instruments and their application to Mendelian randomization with pleiotropy
Jiang, L., Oualkacha, K., Didelez, V., Ciampi, A., Rosa‐Neto, P., Benedet, A. L., Mathotaarachchi, S., Richards, J. B., Greenwood, C. M. T., & Initiative, A. F. T. A. D. N. (2019) · Genetic Epidemiology · doi:10.1002/gepi.22184 · Cited by 23
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.