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$?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.