fredhallgren / inkpca

Incremental kernel PCA

Incremental kernel PCA

Incremental kernel PCA based on rank-one updates to the eigendecomposition of the kernel matrix, which takes into account the changing mean of the covariance matrix for additional data points.

This is the most efficient algorithm for incremental kernel PCA currently available. See our paper for further details, available at this link.

We also create the first incremental algorithm for the Nyström approximation to the kernel matrix.

The algorithm is located in the file incremental_kpca.py. The rank-one update algorithm we apply is located in eigen_update.py. Experiments on two datasets from the UCI Machine Learning repository are included.

Requirements

• Python 3.6

• Numpy

• Scipy

• nose (for tests)

Running

To run the experiments, do from this folder

cd inkpca
python experiments.py

Tested on Ubuntu 20.04

Citation

If you found this package useful then please consider citing the paper.

@article{hallgren2018incremental,
  title={Incremental kernel PCA and the Nyström method},
  author={Hallgren, Fredrik and Northrop, Paul},
  journal={arXiv preprint arXiv:1802.00043},
  year={2018}
}

inkpca's Issues

License

Thanks for your nice work!

Did you already make up your mind about which license is going to being applied for this?
Just curious if I'd be able to apply it for my own work.

Distributed version of algorithm

Hello. Thanks for your interesting algorithm and repository.

A nice advantage of many incremental methods is that they are also easily parallelized. Do you think your algorithm could be extended to a version that:

• Accepts a set of X files instead of a single file, where each file represents a subset of rows the original matrix
• Runs X processes, one on each file, with each process locally performing an incremental update for each row it reads
• After all of the files have been processed (or repeatedly after a given number of rows), combines the results of each process together

From a implementation perspective a package like Ray or Dask would probably be easy to use

From a theory perspective we only have to figure out how to combine the results of the separate processes, and how frequently, right? Or is it not that simple?

Incremental KPCA for Python 3.6

Hi, I am trying to use this in Python 3.6 but it is failing at places. Just wondering if you are planning to release a new version of incremental kpca which will for with Python 3.6 and above.

Extracting components

Where can I get some help on how to extract components? It would be very helpful if we have some small examples to describe all the methods.

Numerical instability when performing rank-one update

Hi,

Great work. Thanks for building this library. I am working on a life-long learning problem that tends to have a large number of data points, and thus a large kernel matrix.

It appears that your rank-one implementation is solving the omega equation in Golub's 1973 paper. I have noticed that for a ~large number of data points (roughly 500), the rank-one update of the eigenvalues fails due to no roots being found in the secular equation for very small eigenvalues (likely from numerical inaccuracies due to floating point).

Have you:

1. Experienced this problem? You should be able to reproduce the issue if you change m0 to 500.
2. Implemented any other rank-one update algorithms that provide better numerical stability?

Thanks.

How to build KPCA components and perform inverse transform?

Thank you for your wonderful work and algorithm! I found it really helpful.
Now I am trying to apply inkpca to a large image dataset. However, I found that in the 'experiments.py', there are no results for kpca final components and its inverse transformation results, which would really help my work.
Is there any possiblity that this algorithm can include calculating components and inverse transformation?