A Generalized Randomized Rank-Revealing Factorization

2019/09/14 by Grey Ballard, James Demmel, Ballard, Grey +5 · 1 citation
Computer Science · Engineering · #15-04 #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Face and Expression Recognition #Numerical Analysis (math.NA) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1909.06524

openalex publication_date 2019/09/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We introduce a Generalized Randomized QR-decomposition that may be applied to arbitrary products of matrices and their inverses, without needing to explicitly compute the products or inverses. This factorization is a critical part of a communication-optimal spectral divide-and-conquer algorithm for the nonsymmetric eigenvalue problem. In this paper, we establish that this randomized QR-factorization satisfies the strong rank-revealing properties. We also formally prove its stability, making it suitable in applications. Finally, we present numerical experiments which demonstrate that our theoretical bounds capture the empirical behavior of the factorization.

Citations

• Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions
• Linear least squares solutions by householder transformations

Cited by

• Structured Divide-and-Conquer for the Definite Generalized Eigenvalue Problem

Related

• Randomized strong rank-revealing QR for column subset selection and low-rank matrix approximation
• Blocked rank-revealing QR factorizations: How randomized sampling can be used to avoid single-vector pivoting
• A randomized blocked algorithm for efficiently computing rank-revealing\n factorizations of matrices
• A Rank Revealing Factorization Using Arbitrary Norms
• Randomized Rank-Revealing QLP for Low-Rank Matrix Decomposition