Efficient kernel-PCA by Nyström sampling

Abstract: In this talk, we discuss and study a Nyström based approach to efficient large scale kernel principal component analysis (PCA). The latter is a natural nonlinear extension of classical PCA based on considering a nonlinear feature map or the corresponding kernel. Like other kernel approaches, kernel PCA enjoys good mathematical and statistical properties but, numerically, it scales poorly with the sample size. Our analysis shows that Nyström sampling greatly improves computational efficiency without incurring any loss of statistical accuracy. While similar effects have been observed in supervised learning, this is the first such result for PCA. Our theoretical findings, which are also illustrated by numerical results, are based on a combination of analytic and concentration of measure techniques. Our study is more broadly motivated by the question of understanding the interplay between statistical and computational requirements for learning.

analysis of PDEsfunctional analysisgeneral mathematicsnumerical analysisoptimization and controlprobabilitystatistics theory

Audience: researchers in the topic

One World seminar: Mathematical Methods for Arbitrary Data Sources (MADS)

Series comments: Description: Research seminar on mathematics for data

The lecture series will collect talks on mathematical disciplines related to all kind of data, ranging from statistics and machine learning to model-based approaches and inverse problems. Each pair of talks will address a specific direction, e.g., a NoMADS session related to nonlocal approaches or a DeepMADS session related to deep learning.

Approximately 15 minutes prior to the beginning of the lecture, a zoom link will be provided on the official website and via mailing list. For further details please visit our webpage.