Given two matrices X, Y of dimension n times m, with m < n and full rank, the Two-Sided Gram-Schmidt process aims to find two bases Q, P of the same dimension such that range(X) = range(Q), range(Y) = range(P) and Q^T P = D, with D diagonal, i.e. Q and P are biorthogonal. It is widely known that this algorithm frequently suffers from numerical instability, and the bases Q and P are often ill-conditioned.

In this talk, we present a randomized version of the algorithm, which computes two matrices Q and P that satisfy the sketched biorthognality condition (SQ)^T SP = D, where S is a sketching matrix of dimension s times n satisfying an oblivious eps-embedding property, such as a subsampled randomized Hadamard transform or a sparse sign matrix. We show how this approach can improve the stability of the algorithm and the condition number of the computed bases Q and P.

As an application, we consider the computation of approximate eigenvalues and both right and left eigenvectors, where our randomized two-sided Gram-Schmidt orthogonalization process can be implemented within the non-symmetric Lanczos algorithm.