Computing Strong Rank-Revealing Factorizations for Matrices with Orthonormal Rows
Provides a faster method for strong rank-revealing factorizations, benefiting numerical linear algebra and data analysis applications.
The paper shows that Stewart's pivoting strategy computes a strong rank-revealing factorization for matrices with orthonormal rows, achieving rank-k approximation accuracy and basis conditioning comparable to direct strong rank-revealing factorizations. A randomized variant returns the desired subset up to two orders of magnitude faster.
We show that a pivoting strategy due to Stewart (based on work by Bischof) computes a strong rank-revealing factorization when applied to a matrix with orthonormal rows. When paired with the classical column selection algorithm of Golub, Klema, and Stewart (GKS) it helps achieve rank-$k$ approximation accuracy bounds and basis conditioning as good as those from applying a strong rank-revealing factorization directly to A. We then extend this framework in two directions: (1) providing analysis of GKS when only approximations of right singular vectors are available and (2) providing a randomized variant of the pivoting strategy for matrices with orthonormal rows that achieves the same theoretical guarantees but can return the desired subset two orders of magnitude faster than the deterministic variant.