Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Rank-one updates and other potential performance gains for CUR #216

Open
agoscinski opened this issue Aug 24, 2023 · 1 comment
Open

Rank-one updates and other potential performance gains for CUR #216

agoscinski opened this issue Aug 24, 2023 · 1 comment
Labels
enhancement New feature or request low-priority Something is not so important

Comments

@agoscinski
Copy link
Collaborator

This is a revive of the draft PR #86 (please look into it for further information) because I think it is worth to look into this more given that CUR outperforms FPS by far in regression quality and is often not used because it is so expensive to compute.

The core idea is to update the eigenvectors after a selection instead of recomputing them by an eigendecomposition. @ceriottm mentioned in a discussion that it was mathematically unstable for eigenvectors corresponding to degenerated eigenvalues. So this deserves some dedicated time look into this in detail.

Links:

@agoscinski agoscinski added enhancement New feature or request low-priority Something is not so important labels Aug 24, 2023
@ceriottm
Copy link
Collaborator

Ok I thought a bit more and I think I recall better what the issue was.

  1. these are some algorithms for rank-1 updates http://doi.org/10.1137/S089547989223924X and http://doi.org/10.1007/BF01396012 - you can see it's kind of a pain to get the eigenvectors
  2. the issue here is that for a big matrix we don't want to compute ALL eigenvectors, but only the top ones. this can be done efficiently, but the problem is then how to do a rank-one update of only some of the eigenvectors. this is the only article I had found for this, but couldn't find an implementation https://epubs.siam.org/doi/epdf/10.1137/18M1172120

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request low-priority Something is not so important
Projects
None yet
Development

No branches or pull requests

2 participants