Optimality of empirical measures as quantizers
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918113740587008 |
|---|---|
| author | Boedihardjo, March T. |
| author_facet | Boedihardjo, March T. |
| contents | A common way to discretize a probability measure is to use an empirical measure as a discrete approximation. But how far from being optimal is this approximation in the p-Wasserstein distance? In this paper, we study this question in two contexts: (1) optimality among all uniform quantizers and (2) optimality among all (non-uniform) quantizers. In the first context, for p=1, we provide a complete answer to this question up to a polylog(n) factor. From the probabilistic point of view, this resolves, up to a polylog(n) factor, the problem of characterizing the expected 1-Wasserstein distance between a probability measure and its empirical measure in terms of non-random quantities. We also obtain some partial results for p>1 in the first context and for p>=1 in the second context. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_02615 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Optimality of empirical measures as quantizers Boedihardjo, March T. Probability A common way to discretize a probability measure is to use an empirical measure as a discrete approximation. But how far from being optimal is this approximation in the p-Wasserstein distance? In this paper, we study this question in two contexts: (1) optimality among all uniform quantizers and (2) optimality among all (non-uniform) quantizers. In the first context, for p=1, we provide a complete answer to this question up to a polylog(n) factor. From the probabilistic point of view, this resolves, up to a polylog(n) factor, the problem of characterizing the expected 1-Wasserstein distance between a probability measure and its empirical measure in terms of non-random quantities. We also obtain some partial results for p>1 in the first context and for p>=1 in the second context. |
| title | Optimality of empirical measures as quantizers |
| topic | Probability |
| url | https://arxiv.org/abs/2508.02615 |