Sketched kernel learning and certified approximate solves — Examples

For $K=\mathrm{diag}(1,0)$, $K+\tau I_2=\mathrm{diag}(1+\tau ,\tau )$, whose inverse is $\mathrm{diag}((1+\tau {)}^{-1},{\tau }^{-1})$. Multiplication by $(p,q{)}^T$ gives the displayed coefficient vector, and multiplication by $K$ gives $u=((1+\tau {)}^{-1}p,0{)}^T$.

For $K=0$, $K+\tau I_n=\tau I_n$ has inverse ${\tau }^{-1}{I}_n$, so $a=y\mathrm{/}\tau$ and $u=Ka=0$ for every $n\ge 1$. Both matrices are positive semidefinite, and [F3] identifies their finite systems with the stated RKHS minimizers when the kernel hypotheses hold.

Since $S=I_2$, $KS=K$, hence $\mathrm{Ran}(KS)=\mathrm{Ran}(K)$. By [F2], the Nyström matrix equals $K$.

The shifted matrix is $K+\tau I_2=\mathrm{diag}(4+\tau ,1+\tau )$, so its inverse gives $a_K=((4+\tau {)}^{-1}p,(1+\tau {)}^{-1}q{)}^T$ and multiplication by $K$ gives the displayed fitted vector. Step 1.1 makes the same calculations apply to $\tilde{K}$, while [F4] with $\delta =0$ confirms both errors vanish.

Both $K$ and $\tilde{K}$ are positive semidefinite, and their spectral-norm difference is $d$. Their shifted systems are the positive scalars $\tau$ and $d+\tau$, so [F1] gives $a_K=1\mathrm{/}\tau$ and $a_{\tilde{K}}=1\mathrm{/}(d+\tau )$.

Subtraction gives $\mid a_K-a_{\tilde{K}}\mid =\mid \frac{1}{\tau }-\frac{1}{d+\tau }\mid =\frac{d}{\tau (d+\tau )}$. For $0<\tau \le d$, this is at least $1\mathrm{/}(2\tau )$, so it diverges as $\tau \downarrow 0$. The general upper bound in [F2] is $d\mathrm{/}{\tau }^2$; it remains a valid scale-sensitive certificate and gives no uniform coefficient bound as $\tau$ approaches zero.

For each $j$, the feature vectors ${\varphi }_j(x),{\varphi }_j(z)$ are linearly independent. Hence $v\mapsto f_v$ is injective, the stated inner product makes ${\mathcal{H}}_j$ a complete two-dimensional real inner-product space, and $k_j(\cdot ,s)=f_{{\varphi }_j(s)}$ satisfies $⟨f_v,k_j(\cdot ,s){⟩}_{{\mathcal{H}}_j}=v^T{\varphi }_j(s)=f_v(s)$. For any finite list $(t_i)$ in $\{x,z\}$ and real coefficients $(c_i)$, ${\sum }_{i,j}{c}_i{c}_j{k}_j(t_i,t_j)=\parallel {\sum }_i{c}_i{\varphi }_j(t_i){\parallel }_2^2\ge 0$. Thus each $k_j$ is a positive-semidefinite kernel with the displayed Gram matrix and an explicitly specified real RKHS.

For the training list consisting of $x$, both training Gram matrices equal $[1]$. By [F2], both shifted systems give coefficient $1\mathrm{/}(1+\tau )$ and training fitted value $1\mathrm{/}(1+\tau )$. The list length is $n=1$, so setting $\lambda =\tau >0$ gives $\tau =n\lambda$; the actual RKHSs established in step 1.1 let [F4] identify these coefficients with the unique kernel-ridge minimizers. The exact test predictions are $k_0(z,x)\mathrm{/}(1+\tau )=0$ and $k_1(z,x)\mathrm{/}(1+\tau )=1\mathrm{/}(2(1+\tau ))$.

Since $G_{0}S=(1,1\mathrm{/}10{)}^T$ and $S^T{G}_{0}S=101\mathrm{/}100$, [F3] gives the displayed rank-one matrix $\tilde{K}$. Its training entry is $100\mathrm{/}101$, so [F2] gives $\tilde{a}=(100\mathrm{/}101+1{)}^{-1}=101\mathrm{/}201$ at $\tau =1$. The approximate test prediction is $(10\mathrm{/}101)(101\mathrm{/}201)=10\mathrm{/}201$; the exact prediction under $G_0$ is zero. The training fitted-value difference is $\mathrm{\mid }1\mathrm{/}2-(100\mathrm{/}101)(101\mathrm{/}201)\mathrm{\mid }=\mathrm{\mid }1\mathrm{/}2-100\mathrm{/}201\mathrm{\mid }=1\mathrm{/}402$, while the test-prediction difference is $10\mathrm{/}201$.