Incremental kernel PCA and the Nyström method
Incremental versions of batch algorithms are often desired, for increased time efficiency in the streaming data setting, or increased memory efficiency in general. In this paper we present a novel algorithm for incremental kernel PCA, based on rank one updates to the eigendecomposition of the kernel matrix, which is more computationally efficient than comparable existing algorithms. We extend our algorithm to incremental calculation of the Nystr\"om approximation to the kernel matrix, the first such algorithm proposed. Incremental calculation of the Nystr\"om approximation leads to further gains in memory efficiency, and allows for empirical evaluation of when a subset of sufficient size has been obtained.
Code (1)
Similar Papers 제목 키워드 기반
Less is More: Nyström Computational Regularization
We study Nystr\"om type subsampling approaches to large scale kernel methods, and prove learning bounds in the statistical learning setting, where random sampling and high probability estimates are considered. In particu…
Efficient Kernel UCB for Contextual Bandits
In this paper, we tackle the computational efficiency of kernelized UCB algorithms in contextual bandits. While standard methods require a O(CT^3) complexity where T is the horizon and the constant C is related to optimi…
Computational EfficiencyMulti-Armed BanditsPack only the essentials: Adaptive dictionary learning for kernel ridge regression
One of the major limits of kernel ridge regression (KRR) is that storing and manipulating the kernel matrix K_n for n samples requires O(n^2) space, which rapidly becomes unfeasible for large n. Nystrom approximations re…
Kernel PCA with the Nyström method
The Nystr\"om method is one of the most popular techniques for improving the scalability of kernel methods. However, it has not yet been derived for kernel PCA in line with classical PCA. In this paper we derive kernel P…
regressionScalable Kernel K-Means Clustering with Nystrom Approximation: Relative-Error Bounds
Kernel $k$-means clustering can correctly identify and extract a far more varied collection of cluster structures than the linear $k$-means clustering algorithm. However, kernel $k$-means clustering is computationally ex…
Clustering