Dominant subspace and low-rank approximations from block Krylov subspaces without a prescribed gap

Abstract

We develop a novel convergence analysis of the classical deterministic block Krylov methods for the approximation of $h$-dimensional dominant subspaces and low-rank approximations of matrices $A\in {\mathbb{K}}^{m\times n}$ (where $\mathbb{K}=\mathbb{R}$ or $\mathbb{C})$ in the case that there is no singular gap at the index $h$ i.e., if $\ddot{I}{ƒ}_h=\ddot{I}{ƒ}_{h+1}$ (where $\ddot{I}{ƒ}_1\ge \dots \ge \ddot{I}{ƒ}_p\ge 0$ denote the singular values of $A$, and $p=\min \{m,n\}$). Indeed, starting with a (deterministic) matrix $X\in {\mathbb{K}}^{n\times r}$ with $r\ge h$ satisfying a compatibility assumption with some $h$-dimensional right dominant subspace of $A$, we show that block Krylov methods produce arbitrarily good approximations for both problems mentioned above. Our approach is based on recent work by Drineas, Ipsen, Kontopoulou and Magdon-Ismail on the approximation of structural left dominant subspaces. The main difference between our work and previous work on this topic is that instead of exploiting a singular gap at the prescribed index $h$ (which is zero in this case) we exploit the nearest existing singular gaps.