SKIP with fast Toeplitz multiplication and no Lanczos?

[roger-]

I have a purely theoretical question: can I exploit fast FFT based Toeplitz kernels with product kernels, kernel interpolation and MVM, without a Lanczos decomposition?

Looking at (10) and lemma 3.1 in the SKIP paper (and imagining K=W Kuu W' instead of K=Q T Q') it's not clear how to formulate it as a two matrix vector products (for two kernel matrices) where I could exploit the Toeplitz FFT methods.

I guess I'm basically asking if there's an answer to this special case of the question in section 7.

[gpleiss]

can I exploit fast FFT based Toeplitz kernels with product kernels, kernel interpolation and MVM, without a Lanczos decomposition

This is not possible, because the element wise (Hadamard) product does not distribute over matrix vector multiplication. This in fact was the motivation behind the SKIP paper: coming up with an algorithm that translates fast MVMs for 2 kernel matrices into a fast MVM for their element wise product.