guilgautier / guilgautier/DPPy
Address numerical stability in exact sampling of k DPPs for large matrices
- Dominant language
- Python
- Stars
- 240
- Forks
- 56
- PR merge metrics
- No merged PRs in 30d
Description
# Problem
The current k-DPP sampling algorithm using GS is not numerically stable and frequently runs into division warnings when dealing with large matrices (~10kx10k) with large condition numbers (~10^6) and low stable rank (~10).
## Solution
I believe this can be traced to the computation of the [elementary symmetric polynomials](https://github.com/guilgautier/DPPy/blob/0d34dd67deedfed1d66f555636067f8fb2b0aab7/dppy/exact_sampling.py#L1306) and [this check](https://github.com/guilgautier/DPPy/blob/0d34dd67deedfed1d66f555636067f8fb2b0aab7/dppy/exact_sampling.py#L1296)
I have implemented a numerically stable recursion by working in the log space of the elementary symmetric polynomials and changing the check mentioned above. This can also be moved to GPUs using torch instead of numpy
**Would be happy to contribute to this project.**
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.