# Nystrom approximation with inexact/stochastic kernel evaluation

Suppose we have several data points $$x_1,\ldots,x_m\in\mathbb R^n$$ as well as a positive definite kernel $$K(x,y):\mathbb R^n\times\mathbb R^n\to\mathbb R$$ that can be written in the form $$K(x,y)=\mathbb E_{\theta\sim P(\theta)}[\phi_\theta(x)\cdot\phi_\theta(y)].$$ That is, we think of $$\phi_\theta:\mathbb R^n\to\mathbb R^p$$ as a function that lifts points into a feature space (similarly to any kernel) but we average over many $$\phi$$'s parameterized by $$\theta$$. Random Fourier features and several kernels can be written this way.

I can approximate a given entry $$K_{ij}:=K(x_i,x_j)$$ of my kernel matrix by taking a sample mean with $$Q$$ points: $$K_{ij}\approx\frac{1}{Q}\sum_{q=1}^Q \phi_{\theta_q}(x_i)\cdot\phi_{\theta_q}(x_j),$$ where $$\theta_1,\ldots,\theta_q\sim P(\theta)$$.

Suppose I compute $$R$$ rows of $$K\in\mathbb R^{m\times m}$$ using the expectation above; I can draw a different set of $$\theta$$'s for each $$(i,j)$$ pair. Then, I fill in the remaining $$m-R$$ rows using the Nystrom approximation, or some regularized variant. The error in my approximated $$K_{ij}$$ matrix comes from two sources: Evaluating $$K(\cdot,\cdot)$$ using a sampling approach, and filling in missing rows using a low-rank assumption.

Is there a way to understand the trade-off between $$Q$$ and $$R$$ here? That is, to improve the quality of my approximation of the full kernel matrix, should I increase the number of samples $$Q$$ or the number of rows $$R$$?