Computing Strong Rank-Revealing Factorizations for Matrices with Orthonormal Rows

Abstract

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.

Disclosure

“Robert Web- ber, Ilse Ipsen, Mark Embree, Laura Grigori, Yuji Nakatsukasa, Mark Fornace, Alex Townsend, and Michael Lindsey sharpened our thinking of the relationship between mGKS and Osinsky’s results. Implementations were produced using Anthropic’s Claude Code [1]. As was code to run numerical experiments and generate plots. OpenAI Codex [4] was used for code review and early prototyping. Deterministic im- plementations were validated against a carefully audited oracle implementation (albei”

PDF page 21

Classification

Computational experiments or data processing

Multiplier

3

Verified

2026-08-23T18:55:40.474897Z

Structural counts