Randomized biorthogonalization through a two-sided Gram-Schmidt process

2025/09/04 by Grigori, Laura, Piccinini, Lorenzo, Simunec, Igor · 1 citation
#65F25 (Primary) 65F15 (Secondary) #FOS: Mathematics #Numerical Analysis (math.NA)

paper · doi:10.48550/arxiv.2509.04386

Abstract

We propose and analyze a randomized two-sided Gram-Schmidt process for the biorthogonalization of two given matrices X, Y ∈ℝ^{n× m}. The algorithm aims to find two matrices Q, P ∈ℝ^{n× m} such that \rm range(X) = \rm range(Q), \rm range(Y) = \rm range(P) and (ΩQ)^T ΩP = I, where Ω∈ℝ^{s × n} is a sketching matrix satisfying an oblivious subspace ε-embedding property; in other words, the biorthogonality condition on the columns of Q and P is replaced by an equivalent condition on their sketches. This randomized approach is computationally less expensive than the classical two-sided Gram-Schmidt process, has better numerical stability, and the condition number of the computed bases Q, P is often smaller than in the deterministic case. Several different implementations of the randomized algorithm are analyzed and compared numerically. The randomized two-sided Gram-Schmidt process is applied to the nonsymmetric Lancozs algorithm for the approximation of eigenvalues and both left and right eigenvectors.

Citations

• Randomized Krylov-Schur eigensolver with deflation
• Randomized strong rank-revealing QR for column subset selection and low-rank matrix approximation
• Estimation of spectral gaps for sparse symmetric matrices
• Randomized Implicitly Restarted Arnoldi method for the non-symmetric eigenvalue problem
• Randomized Householder QR
• Sketched and truncated polynomial Krylov methods: Evaluation of matrix functions
• Using Mixed Precision in Low-Synchronization Reorthogonalized Block Classical Gram-Schmidt
• Randomized sketching for Krylov approximations of large-scale matrix functions
• Randomized Gram-Schmidt process with application to GMRES
• Randomized Numerical Linear Algebra: Foundations & Algorithms
• Streaming Low-Rank Matrix Approximation with an Application to\n Scientific Simulation
• Low-distortion Subspace Embeddings in Input-sparsity Time and Applications to Robust Linear Regression

Cited by

• Randomized orthogonalization and Krylov subspace methods: principles and algorithms

Related

• Randomized Gram-Schmidt process with application to GMRES
• Reorthogonalized Block Classical Gram--Schmidt
• Fast & Accurate Randomized Algorithms for Linear Systems and Eigenvalue Problems
• Randomized Approximation of the Gram Matrix: Exact Computation and Probabilistic Bounds
• Randomized orthogonalization and Krylov subspace methods: principles and algorithms