Finite-budget Nyström kernel ridge fit with residual status

All matrix-vector operations below use exact real arithmetic. The inputs are a finite real symmetric matrix $K\in {\mathbb{R}}^{n\times n}$ with $n\ge 1$ and $x^{T}Kx\ge 0$ for every $x\in {\mathbb{R}}^n$, a vector $y\in {\mathbb{R}}^n$, a scalar $\tau >0$, a finite sketch $S\in {\mathbb{R}}^{n\times s}$ with $s\ge 0$, a residual tolerance $\eta \ge 0$, and a finite nonnegative integer iteration budget $T$. Write $I_n$ for the identity matrix and $\parallel x{\parallel }_2=({\sum }_i{x}_i^2{)}^{1\mathrm{/}2}$ for the Euclidean norm. The Moore–Penrose inverse $M^{†}$ is the unique matrix satisfying $M{M}^{†}M=M$, $M^{†}M{M}^{†}=M^{†}$, $(M{M}^{†}{)}^T=M{M}^{†}$, and $(M^{†}M{)}^T=M^{†}M$.

1. Form the Nyström matrix $\tilde{K}=KS(S^{T}KS{)}^{†}{S}^{T}K$. The formula is defined even when $S^{T}KS$ is singular or $s=0$.

2. Set $B=\tilde{K}+\tau I_n$. Initialize $b_0=0$, ${\tilde{r}}_0=y-B{b}_0=y$, and $p_0={\tilde{r}}_0$.

3. For $j=0,1,\dots ,T$, recompute the actual residuals ${\tilde{r}}_j=y-B{b}_j$ and $r_j=y-(K+\tau I_n)b_j$. If both norms are at most $\eta$, return status certified, coefficient vector $b_j$, fitted vector $\tilde{K}{b}_j$, and both residuals. If ${\tilde{r}}_j=0$ but $\parallel r_j{\parallel }_2>\eta$, return status uncertified with the same outputs. If $j=T$ and neither return condition holds, return status budget-exhausted with the same outputs.

4. Otherwise compute $q_j=B{p}_j$. If $p_j^T{q}_j=0$, return status uncertified with the current outputs. If $p_j^T{q}_j>0$, set ${\alpha }_j=({\tilde{r}}_j^T{\tilde{r}}_j)\mathrm{/}(p_j^T{q}_j)$, $b_{j+1}=b_j+{\alpha }_j{p}_j$, and ${\tilde{r}}_{j+1}={\tilde{r}}_j-{\alpha }_j{q}_j$. If ${\tilde{r}}_{j+1}=0$, recompute $r_{j+1}$ and return certified when $\parallel r_{j+1}{\parallel }_2\le \eta$, and otherwise return uncertified, together with the resulting outputs. If ${\tilde{r}}_{j+1}\mathrm{\ne }0$, set ${\beta }_j=({\tilde{r}}_{j+1}^T{\tilde{r}}_{j+1})\mathrm{/}({\tilde{r}}_j^T{\tilde{r}}_j)$ and $p_{j+1}={\tilde{r}}_{j+1}+{\beta }_j{p}_j$, then continue at the next iteration.

The output always includes the actual residuals for both the Nyström system and the original system. certified asserts that both residuals meet the requested tolerance; uncertified and budget-exhausted make no solve-accuracy claim. In particular, exhausting the budget does not certify a solve. If $K$ is a Gram matrix and $\tau =n\lambda$, the original-system residual is the one used in the residual prediction certificate.

The positive-semidefinite Nyström approximation: For a PSD matrix $K$, the Nyström matrix is $KS(S^{T}KS{)}^{†}{S}^{T}K$.

Nyström is positive semidefinite, dominated by A, and exact when it captures the range: Every such Nyström matrix is positive semidefinite and is bounded above by $K$.

Inverse norm bound for a regularized Gram matrix: Adding $\tau I$ with $\tau >0$ makes the Nyström system positive definite.

The four equations stated above define a Moore–Penrose inverse.

Every finite real matrix has a unique Moore–Penrose inverse, including singular and zero-sized matrices.

The original-system residual bounds coefficient and training fitted-vector errors.