Incremental kernel PCA and the Nyström method
This work addresses memory and time efficiency issues for researchers and practitioners using kernel methods in data streaming scenarios, though it is incremental in nature.
The paper tackles the problem of efficiently updating kernel PCA and the Nyström approximation in streaming or memory-constrained settings, resulting in a novel incremental algorithm that is more computationally efficient than existing methods and enables memory savings and empirical subset evaluation.
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öm approximation to the kernel matrix, the first such algorithm proposed. Incremental calculation of the Nyström approximation leads to further gains in memory efficiency, and allows for empirical evaluation of when a subset of sufficient size has been obtained.