Kernel Approximation Over Algebraic Varieties

Low-rank approximation of the Gaussian kernel is a core component of many data-science algorithms. Often the approximation is desired over an algebraic variety (e.g., in problems involving sparse data or low-rank data). Can better approximations be obtained in this setting? In this talk, I’ll show that the answer is yes: The improvement is exponential and controlled by the variety’s Hilbert dimension. 

Joint work with Pablo Parrilo