Speaker
Description
Given two matrices $X,Y\in\mathbb{R}^{n\times m}$ with $m<n$ and full rank, the Two-Sided Gram-Schmidt process aims to find two bases $Q,P\in\mathbb{R}^{n\times m}$ such that ${\rm range}(X)={\rm range}(Q)$, ${\rm range}(Y) = {\rm 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 $(\Omega Q)^T \Omega P = D$, where $\Omega \in\mathbb{R}^{s\times n}$ is a sketching matrix satisfying an oblivious $\varepsilon$-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.
