On Rank-Revealing Factorisations

The problem of finding a rank-revealing QR (RRQR) factorisation of a matrix A consists of permuting the columns of A such that the resulting QR factorisation contains an upper triangular matrix whose linearly dependent columns are separated from the linearly independent ones. In this paper a systematic treatment of algorithms for determining RRQR factorisations is presented.

In particular, the authors start by presenting precise mathematical formulations for the problem of determining a RRQR factorisation, all of them optimisation problems. Then a hierarchy of “greedy” algorithms is derived to solve these optimisation problems, and it is shown that the existing RRQR algorithms correspond to particular greedy algorithms in this hierarchy. Matrices on which the greedy algorithms, and therefore the existing RRQR algorithms, can fail arbitrarily badly are presented.

Finally, motivated by an insight from the behaviour of the greedy algorithms, the authors present “hybrid” algorithms that solve the optimisation problems almost exactly (up to a factor proportional to the size of the matrix). Applying the hybrid algorithms as a follow-up to the conventional greedy algorithms may prove to be useful in practice.

(2020) New Numerical Algorithm for Deflation of Infinite and Zero Eigenvalues and Full Solution of Quadratic Eigenvalue Problems. ACM Transactions on Mathematical Software 46:4, 1-32. Crossref

(2020) A subset selection based approach to structural reducibility of complex networks. Physica A: Statistical Mechanics and its Applications 540, 123214. Crossref

2020. Dynamic Mode Decomposition—A Numerical Linear Algebra Perspective. The Koopman Operator in Systems and Control, 161-194. Crossref

2020. CUR LRA at Sublinear Cost Based on Volume Maximization. Mathematical Aspects of Computer and Information Sciences, 105-121. Crossref

Maolin Che, Yimin Wei, and Hong Yan. (2020) The Computation of Low Multilinear Rank Approximations of Tensors via Power Scheme and Random Projection. SIAM Journal on Matrix Analysis and Applications 41:2, 605-636. Abstract | PDF (684 KB) 

2020. GCA- $$\mathcal {H}^2$$ Matrix Compression for Electrostatic Simulations. Scientific Computing in Electrical Engineering, 211-223. Crossref

Alice Cortinovis and Daniel Kressner. (2020) Low-Rank Approximation in the Frobenius Norm by Column and Row Subset Selection. SIAM Journal on Matrix Analysis and Applications 41:4, 1651-1673. Abstract | PDF (786 KB) 

(2019) Reduction of multivariate mixtures and its applications. Journal of Computational Physics 383, 94-124. Crossref

(2019) Simple, direct and efficient multi-way spectral clustering. Information and Inference: A Journal of the IMA 8:1, 181-203. Crossref

(2019) SVD update methods for large matrices and applications. Linear Algebra and its Applications 561, 41-62. Crossref

2019. Quadrature Strategies for Constructing Polynomial Approximations. Uncertainty Modeling for Engineering Applications, 1-25. Crossref

(2018) A Note on QR-Based Model Reduction: Algorithm, Software, and Gravitational Wave Applications. Computing in Science & Engineering 20:4, 10-25. Crossref

(2018) Time and space efficient generators for quasiseparable matrices. Journal of Symbolic Computation 85, 224-246. Crossref

Laura Grigori, Sebastien Cayrols, and James W. Demmel. (2018) Low Rank Approximation of a Sparse Matrix Based on LU Factorization with Column and Row Tournament Pivoting. SIAM Journal on Scientific Computing 40:2, C181-C209. Abstract | PDF (701 KB) 

Zlatko Drmač and Arvind Krishna Saibaba. (2018) The Discrete Empirical Interpolation Method: Canonical Structure and Formulation in Weighted Inner Product Spaces. SIAM Journal on Matrix Analysis and Applications 39:3, 1152-1180. Abstract | PDF (766 KB) 

Anil Damle and Lin Lin. (2018) Disentanglement via Entanglement: A Unified Method for Wannier Localization. Multiscale Modeling & Simulation 16:3, 1392-1410. Abstract | PDF (1922 KB) 

(2018) Methods for solving underdetermined systems. Numerical Linear Algebra with Applications 25:1, e2127. Crossref

(2017) Literature survey on low rank approximation of matrices. Linear and Multilinear Algebra 65:11, 2212-2244. Crossref

(2017) SCDM-k: Localized orbitals for solids via selected columns of the density matrix. Journal of Computational Physics 334, 1-15. Crossref

(2017) A QR decomposition approach to factor modelling. Signal Processing 132, 19-28. Crossref

Pranay Seshadri, Akil Narayan, and Sankaran Mahadevan. (2017) Effectively Subsampled Quadratures for Least Squares Polynomial Approximations. SIAM/ASA Journal on Uncertainty Quantification 5:1, 1003-1023. Abstract | PDF (1282 KB) 

2017. Fast Multipole Method as a Matrix-Free Hierarchical Low-Rank Approximation. Eigenvalue Problems: Algorithms, Software and Applications in Petascale Computing, 267-286. Crossref

(2017) New studies of randomized augmentation and additive preprocessing. Linear Algebra and its Applications 512, 256-305. Crossref

(2016) A Nonlinear QR Algorithm for Banded Nonlinear Eigenvalue Problems. ACM Transactions on Mathematical Software 43:1, 1-19. Crossref

Zlatko Drmač and Serkan Gugercin. (2016) A New Selection Operator for the Discrete Empirical Interpolation Method---Improved A Priori Error Bound and Extensions. SIAM Journal on Scientific Computing 38:2, A631-A648. Abstract | PDF (964 KB) 

K. Lessel, M. Hartman, and S. Chandrasekaran. (2016) A Fast Memory Efficient Construction Algorithm for Hierarchically Semi-Separable Representations. SIAM Journal on Matrix Analysis and Applications 37:1, 338-353. Abstract | PDF (820 KB) 

(2016) An algebraic multifrontal preconditioner that exploits the low-rank property. Numerical Linear Algebra with Applications 23:1, 61-82. Crossref

(2016) Computing with Quasiseparable Matrices. Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation - ISSAC '16, 389-396. Crossref

(2016) On the solution of large-scale algebraic Riccati equations by using low-dimensional invariant subspaces. Linear Algebra and its Applications 488, 430-459. Crossref

(2015) Estimation of atmospheric PSF parameters for hyperspectral imaging. Numerical Linear Algebra with Applications 22:5, 795-813. Crossref

(2015) Convergence to diagonal form of block Jacobi-type methods. Numerische Mathematik 129:3, 449-481. Crossref

James W. Demmel, Laura Grigori, Ming Gu, and Hua Xiang. (2015) Communication Avoiding Rank Revealing QR Factorization with Column Pivoting. SIAM Journal on Matrix Analysis and Applications 36:1, 55-89. Abstract | PDF (1109 KB) | Supplementary Materials 

M. Gu. (2015) Subspace Iteration Randomization and Singular Value Problems. SIAM Journal on Scientific Computing 37:3, A1139-A1173. Abstract | PDF (573 KB) | Supplementary Materials 

John T. Holodnak and Ilse C. F. Ipsen. (2015) Randomized Approximation of the Gram Matrix: Exact Computation and Probabilistic Bounds. SIAM Journal on Matrix Analysis and Applications 36:1, 110-137. Abstract | PDF (959 KB) 

(2015) Computing Low-Rank Approximation of a Dense Matrix on Multicore CPUs with a GPU and Its Application to Solving a Hierarchically Semiseparable Linear System of Equations. Scientific Programming 2015, 1-17. Crossref

(2014) Column Subset Selection Problem is UG-hard. Journal of Computer and System Sciences 80:4, 849-859. Crossref

Jack Poulson, Laurent Demanet, Nicholas Maxwell, and Lexing Ying. (2014) A Parallel Butterfly Algorithm. SIAM Journal on Scientific Computing 36:1, C49-C65. Abstract | PDF (263 KB) 

(2013) Gram-Schmidt orthogonalization: 100 years and more. Numerical Linear Algebra with Applications 20:3, 492-532. Crossref

(2013) An algorithm for the complete solution of quadratic eigenvalue problems. ACM Transactions on Mathematical Software 39:3, 1-19. Crossref

Artem Napov. (2013) Conditioning Analysis of Incomplete Cholesky Factorizations with Orthogonal Dropping. SIAM Journal on Matrix Analysis and Applications 34:3, 1148-1173. Abstract | PDF (759 KB) 

2013. Parallelization of the QR Decomposition with Column Pivoting Using Column Cyclic Distribution on Multicore and GPU Processors. High Performance Computing for Computational Science - VECPAR 2012, 50-58. Crossref

(2013) Exponential Inapproximability of Selecting a Maximum Volume Sub-matrix. Algorithmica 65:1, 159-176. Crossref

(2012) Column subset selection via sparse approximation of SVD. Theoretical Computer Science 421, 1-14. Crossref

2012. Algorithmic and Statistical Perspectives on Large-Scale Data Analysis. Combinatorial Scientific Computing, 427-469. Crossref

Jianlin Xia and Ming Gu. (2010) Robust Approximate Cholesky Factorization of Rank-Structured Symmetric Positive Definite Matrices. SIAM Journal on Matrix Analysis and Applications 31:5, 2899-2920. Abstract | PDF (446 KB) 

(2009) On selecting a maximum volume sub-matrix of a matrix and related problems. Theoretical Computer Science 410:47-49, 4801-4811. Crossref

Haim Avron, Esmond Ng, and Sivan Toledo. (2009) Using Perturbed $QR$ Factorizations to Solve Linear Least-Squares Problems. SIAM Journal on Matrix Analysis and Applications 31:2, 674-693. Abstract | PDF (260 KB) 

(2008) On the Failure of Rank-Revealing QR Factorization Software -- A Case Study. ACM Transactions on Mathematical Software 35:2, 1-28. Crossref

(2008) Accurate and efficient expression evaluation and linear algebra. Acta Numerica 17, 87-145. Crossref

Zlatko Drmač and Krešimir Veselić. (2008) New Fast and Accurate Jacobi SVD Algorithm. I. SIAM Journal on Matrix Analysis and Applications 29:4, 1322-1342. Abstract | PDF (285 KB) 

2008. Deterministic Sparse Column Based Matrix Reconstruction via Greedy Approximation of SVD. Algorithms and Computation, 414-423. Crossref

(2007) Fast linear algebra is stable. Numerische Mathematik 108:1, 59-91. Crossref

(2007) Propagator Method and Triangular Factorization for Source Bearing Estimation of Coherent sources. MILCOM 2007 - IEEE Military Communications Conference, 1-6. Crossref

S. Chandrasekaran, M. Gu, and T. Pals. (2006) A Fast $ULV$ Decomposition Solver for Hierarchically Semiseparable Representations. SIAM Journal on Matrix Analysis and Applications 28:3, 603-622. Abstract | PDF (211 KB) 

(2005) Stewart's pivoted QLP decomposition for low-rank matrices. Numerical Linear Algebra with Applications 12:2-3, 153-159. Crossref

S. Chandrasekaran, P. Dewilde, M. Gu, T. Pals, X. Sun, A. J. van der Veen, and D. White. (2005) Some Fast Algorithms for Sequentially Semiseparable Representations. SIAM Journal on Matrix Analysis and Applications 27:2, 341-364. Abstract | PDF (233 KB) 

(2004) A QR?method for computing the singular values via semiseparable matrices. Numerische Mathematik 99:1, 163-195. Crossref

(2003) Strong rank revealing LU factorizations. Linear Algebra and its Applications 367, 1-16. Crossref

(2001) A Newton method for rigid body frictional impact with multiple simultaneous impact points. Computer Methods in Applied Mechanics and Engineering 191:3-5, 239-254. Crossref

Per Christian Hansen and Plamen Y. Yalamov. (2001) Computing Symmetric Rank-Revealing Decompositions via Triangular Factorization. SIAM Journal on Matrix Analysis and Applications 23:2, 443-458. Abstract | PDF (197 KB) 

(2000) Symbiosis between linear algebra and optimization. Journal of Computational and Applied Mathematics 123:1-2, 447-465. Crossref

(2000) On the existence and computation of rank-revealing LU factorizations. Linear Algebra and its Applications 316:1-3, 199-222. Crossref

James Demmel. (2000) Accurate Singular Value Decompositions of Structured Matrices. SIAM Journal on Matrix Analysis and Applications 21:2, 562-580. Abstract | PDF (4563 KB) 

G. W. Stewart. (1999) The QLP Approximation to the Singular Value Decomposition. SIAM Journal on Scientific Computing 20:4, 1336-1348. Abstract | PDF (288 KB) 

(1998) Algebraic methods for deterministic blind beamforming. Proceedings of the IEEE 86:10, 1987-2008. Crossref

Gregorio Quintana-Ortí, Xiaobai Sun, and Christian H. Bischof. (1998) A BLAS-3 Version of the QR Factorization with Column Pivoting. SIAM Journal on Scientific Computing 19:5, 1486-1494. Abstract | PDF (217 KB) 

(1998) Computing rank-revealing QR factorizations of dense matrices. ACM Transactions on Mathematical Software 24:2, 226-253. Crossref

(1998) Algorithm 782. ACM Transactions on Mathematical Software 24:2, 254-257. Crossref

(1998) Parallel codes for computing the numerical rank. Linear Algebra and its Applications 275-276, 451-470. Crossref

(1998) Approximating minimum norm solutions of rank-deficient least squares problems. Numerical Linear Algebra with Applications 5:2, 79-99. Crossref

Gregorio Quintana-Ortí, Enrique S. Quintana-Ortí, and Antoine Petitet. (1998) Efficient Solution Of The Rank-Deficient Linear Least Squares Problem. SIAM Journal on Scientific Computing 20:3, 1155-1163. Abstract | PDF (261 KB) 

(1997) Improved bound for rank revealing LU factorizations. Linear Algebra and its Applications 261:1-3, 173-186. Crossref

1997. Parallel Algorithms for Computing Rank-Revealing QR Factorizations. Workshop on High Performance Computing and Gigabit Local Area Networks, 122-137. Crossref

Ming Gu and Stanley C. Eisenstat. (1996) Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization. SIAM Journal on Scientific Computing 17:4, 848-869. Abstract | PDF (1929 KB) 

Alle-Jan van der Veen. (1996) A Schur Method for Low-Rank Matrix Approximation. SIAM Journal on Matrix Analysis and Applications 17:1, 139-160. Abstract | PDF (2512 KB) 

S. Chandrasekaran and I. C. F. Ipsen. (1995) Analysis of a QR Algorithm for Computing Singular Values. SIAM Journal on Matrix Analysis and Applications 16:2, 520-535. Abstract | PDF (1743 KB) 

S. Chandrasekaran and I. C. F. Ipsen. (1995) On the Sensitivity of Solution Components in Linear Systems of Equations. SIAM Journal on Matrix Analysis and Applications 16:1, 93-112. Abstract | PDF (2011 KB) 

Fast Selection of Linear Features in Image Data. 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) - Workshops, 49-49. Crossref

Subspace tracking using a constrained hyperbolic URV decomposition. Proceedings of the 1998 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP '98 (Cat. No.98CH36181), 1953-1956. Crossref