Nyström method for symmetric indefinite matrices

Abstract

The Nyström method approximates $A\approx A(:,I)A(I,I{)}^{†}A(:,I{)}^{\top }=CA(I,I{)}^{†}{C}^{\top }$, where $C:=A(:,I)\in {\mathbb{R}}^{n\times r}$ is a column subset matrix of $A$. When applied to symmetric but indefinite matrices, the Nyström method can fail because the core matrix $A(I,I)$ may severely underestimate the eigenvalues of $A$ and may become (nearly) singular. We address this issue by developing and analyzing an algorithm that carefully chooses $\hat{M}\in {\mathbb{R}}^{r\times r}$ in place of $A(I,I{)}^{†}$ by solving the two-sided sketched least-squares problem ${\min }_M\Vert X(A-CM{C}^{\top })X^{\top }{\Vert }_F$, where $X\in {\mathbb{R}}^{t\times n}$ is a random sketch matrix. We study in detail the cases where $X$ is a Gaussian or a leverage score sampling (LSS) matrix, and show that with oversampling $t>r$ the residual $\Vert A-C\hat{M}{C}^{\top }{\Vert }_{\ast }$ is comparable to ${\min }_M\Vert A-CM{C}^{\top }{\Vert }_{\ast }$. For the Gaussian sketch, we require $t=\mathcal{O}(r)$ samples; for LSS, we show that $t=\mathcal{O}(r\log r)$ samples suffice for the theoretical guarantee, with the LSS approach carrying the advantage that once a set of $t$ row indices is identified, the approximation requires only $t^2$ matrix-entry evaluations to find $\hat{M}$, given $C$. We illustrate our results with synthetic examples and applications to kernel methods.

16 pages, 4 figures