Title: Memory-efficient Kernel PCA via Partial Matrix Sampling and Nonconvex Optimization: a Model-free Analysis of Local Minima,
Abstract: Kernel PCA is a widely used nonlinear dimension reduction technique in
machine learning, but storing the kernel matrix is notoriously challenging when
the sample size is large. Inspired by Yi et al. [2016], where the idea of
partial matrix sampling followed by nonconvex optimization is proposed for
matrix completion and robust PCA, we apply a similar approach to
memory-efficient Kernel PCA. In theory, with no assumptions on the kernel
matrix in terms of eigenvalues or eigenvectors, we established a model-free
theory for the low-rank approximation based on any local minimum of the
proposed objective function. As interesting byproducts, when the underlying
positive semidefinite matrix is assumed to be low-rank and highly structured,
corollaries of our main theorem improve the state-of-the-art results of Ge et
al. [2016, 2017] for nonconvex matrix completion with no spurious local minima.
Numerical experiments also show that our approach is competitive in terms of
approximation accuracy compared to the well-known Nyström algorithm for
Kernel PCA.