Computing Strong Rank-Revealing Factorizations for Matrices with Orthonormal Rows

DOI10.48550/arXiv.2607.13532MaRDI QIDQ7284055arXivFDO

Authors Anil Damle

Publication date 15 July 2026

Published in arXiv

Tldr We show a pivoting method computes strong rank-revealing factorizations on matrices with orthonormal rows and use it to improve the accuracy of approximations via Golub, Klema, and Stewart’s algorithm. We also extend this framework to provide analysis for approximated right singular vectors and a randomized version of the pivoting strategy that is significantly faster.

Full work available at URL https://doi.org/10.48550/arXiv.2607.13532

Mathematics Subject Classification ID

Numerical methods for low-rank matrix approximation; matrix compression (65F55)

arXiv classification

math.NA

Cites work

• A DEIM induced CUR factorization
• A new selection operator for the discrete empirical interpolation method -- improved a priori error bound and extensions
• A sublinear-time randomized algorithm for column and row subset selection based on strong rank-revealing QR factorizations
• A theory of pseudoskeleton approximations
• Adaptive randomized pivoting for column subset selection, DEIM, and low-rank approximation
• Adaptive Sampling and Fast Low-Rank Matrix Approximation
• Bayesian D-optimal experimental designs via column subset selection
• Close to optimal column approximation using a single SVD
• Collect, Commit, Expand: Efficient CPQR-Based Column Selection for Extremely Wide Matrices
• CUR matrix decompositions for improved data analysis
• Disentanglement via Entanglement: A Unified Method for Wannier Localization
• Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
• Efficient QR-based Column Subset Selection through Randomized Sparse Embeddings
• Efficient volume sampling for row/column subset selection
• Embrace rejection: Kernel matrix approximation by accelerated randomly pivoted Cholesky
• Estimating a matrix's singular values with interpolative decompositions
• Faster subset selection for matrices and applications
• Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
• Handbook series linear algebra. Linear least squares solutions by Householder transformations
• Incremental Condition Estimation
• Julia: a fresh approach to numerical computing
• Linear Systems and Eigenvalue Problems: Open Questions from a Simons Workshop
• Low-Rank Matrix Approximations Do Not Need a Singular Value Gap
• Matrix approximation and projective clustering via volume sampling
• Near-optimal column-based matrix reconstruction
• Numerical Linear Algebra
• Numerical methods for solving linear least squares problems
• On Rank-Revealing Factorisations
• Optimal column-based low-rank matrix reconstruction
• Randomized algorithms for the low-rank approximation of matrices
• Randomized strong rank-revealing QR for column subset selection and low-rank matrix approximation
• Randomly pivoted Cholesky: practical approximation of a kernel matrix with few entry evaluations
• Rank-Revealing QR Factorizations and the Singular Value Decomposition
• Robust Blockwise Random Pivoting: Fast and Accurate Adaptive Interpolative Decomposition
• Simpler is better: A comparative study of randomized algorithms for computing the CUR decomposition
• Structure-aware analyses and algorithms for interpolative decompositions
• Subset selection for matrices in spectral norm

Cited in

(1)

• Incremental Column Subset Selection via Conditional Determinantal Point Processes

This page was built for publication: Computing Strong Rank-Revealing Factorizations for Matrices with Orthonormal Rows

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7284055)