Skip to content

Distribution: Approximate Volume sampling #152

@nathanielpritchard

Description

@nathanielpritchard

Please describe your motivation for this feature request
The sampling compressor needs new distributions. One important distribution is the approximate volume distribution of Deshpande and Vempala. It works by computing the squared norms of each row (column), sampling from those probability weights then updating the distribution by subtracting the span of all previously selected indices from A and recomputing the row (column) weights.

Image

Describe the solution you'd like
I would like for a new distribution type implemented that utilizes the Approximate Volume Distribution. This distribution will need to be computed at every iteration. This implementation should include a:

  1. complete_distribution function which forms the recipe and computes the distribution.
  2. update_distribution! function which updates the distribution to correspond with a new matrix.
  3. sample_distribution! function which samples from the distribution.

Describe alternatives you've considered
N/A

Additional context
See uniform.jl for an example of a distribution. See this paper for a definition of the distribution.

Metadata

Metadata

Assignees

Labels

enhancementNew feature or request

Type

No type

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions