guilgautier / guilgautier/DPPy

Address numerical stability in exact sampling of k DPPs for large matrices

Open
#80 1 comment 0 reactions 0 assignees View on GitHub
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.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.