Sampling lattice points in a polytope: a Bayesian biased algorithm with random updates
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929430913351680 |
|---|---|
| author | Bakenhus, Miles Petrović, Sonja |
| author_facet | Bakenhus, Miles Petrović, Sonja |
| contents | The set of nonnegative integer lattice points in a polytope, also known as the fiber of a linear map, makes an appearance in several applications including optimization and statistics. We address the problem of sampling from this set using three ingredients: an easy-to-compute lattice basis of the constraint matrix, a biased sampling algorithm with a Bayesian framework, and a step-wise selection method. The bias embedded in our algorithm updates sampler parameters to improve fiber discovery rate at each step chosen from previously discovered elements. We showcase the performance of the algorithm on several examples, including fibers that are out of reach for the state-of-the-art Markov bases samplers. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_02428 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Sampling lattice points in a polytope: a Bayesian biased algorithm with random updates Bakenhus, Miles Petrović, Sonja Computation Commutative Algebra Statistics Theory 62R01 (Primary) 62-08, 52B20 (Secondary) The set of nonnegative integer lattice points in a polytope, also known as the fiber of a linear map, makes an appearance in several applications including optimization and statistics. We address the problem of sampling from this set using three ingredients: an easy-to-compute lattice basis of the constraint matrix, a biased sampling algorithm with a Bayesian framework, and a step-wise selection method. The bias embedded in our algorithm updates sampler parameters to improve fiber discovery rate at each step chosen from previously discovered elements. We showcase the performance of the algorithm on several examples, including fibers that are out of reach for the state-of-the-art Markov bases samplers. |
| title | Sampling lattice points in a polytope: a Bayesian biased algorithm with random updates |
| topic | Computation Commutative Algebra Statistics Theory 62R01 (Primary) 62-08, 52B20 (Secondary) |
| url | https://arxiv.org/abs/2307.02428 |