7
$\begingroup$

Given a probability measures $\mu$ on $\mathbb R^d$ with finite first movement, i.e.

$$\int_{\mathbb R^d}|x|\mu(dx)~~<~~+\infty.$$

My concern is to approximate $\mu$ some $\mu_n$ that is countably or finitely supported. Of course, a generic way is to take such a $\mu_n$ concentrated on the grid $\{\vec{k}/n\}_{\vec{k}\in \mathbb Z^d}$. I wonder whether there exists more literature dealing with this issue, especially from the viewpoint of implementation. Many thanks for answers and comments.

PS: Thanks for the reply. To summarise, I'm interested in the $\mu_n$ such that:

(1) the computation of $\mu_n[\{\vec{k}/n\}]$ is tractable;

(2) the Wasserstein distance $W_1(\mu,\mu_n)$ is easy to estimate.

Of course, the quantisation approach provides a good upper bound for $W_1(\mu,\mu_n)$, but the computation of $\mu_n[\{\vec{k}/n\}]$ is not obvious. So my question is whether there exists some explicit "discretisation" of $\mu$ such that the "discretised weights" are easy to obtain?

Improve this question
$\endgroup$
6
  • $\begingroup$ See zbmath.org/?q=an:0981.31002 to this end. $\endgroup$
    – user64494
    Commented May 27, 2018 at 19:25
  • 2
    $\begingroup$ Another approach would be to approximate the probability measure by sample distributions, see here. $\endgroup$
    – Michael Greinecker
    Commented May 27, 2018 at 22:17
  • $\begingroup$ Cluster analysis is concerned with taking a probability measure of the form $n^{-1} \sum_{i=1}^n \delta_{x_i}$ by another one of the same form, but with much smaller $n$. Perhaps you can look into cluster analysis and check whether any of its algorithms generalize to the case where the original measure is some general (f.f.m.) probability measure $\mu$? $\endgroup$
    – Tobias Fritz
    Commented Jun 27, 2018 at 12:12
  • $\begingroup$ Generally, the answer may also depend on the form in which $\mu$ is given to you. Is it given in terms of its moments? Or can we assume that $\mu$ can be computed e.g. on polyhedra? Or on other kinds of sets? $\endgroup$
    – Tobias Fritz
    Commented Jun 27, 2018 at 12:14
  • $\begingroup$ You cannot talk about "tractable computation" of $\mu_n$ without first saying something about how $\mu$ is represented. Does it belong to some parametric family? Is it implicitly defined via some process? The computational answer will very much depend on that. The same applies to estimating the Wasserstein distance. $\endgroup$
    – Aryeh Kontorovich
    Commented Jul 27, 2018 at 14:15

1 Answer 1

Reset to default
0
$\begingroup$

The keyword to look for might be "quantization", see e.g. G. Pagès' review :

https://doi.org/10.1051/proc/201448002

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Thank you very much for the literature. But what I'm interested in is slightly different from the quantization. Indeed, I'd like to find $\mu_n$ s.t. the computation of $\mu_n[\{\vec{k}/n\}]$ is tractable and the Wasserstein distance $W_1(\mu,\mu_n)$ is easy to estimate. Of course, the quantisation approach provides a good upper bound for $W_1(\mu,\mu_n)$, but the computation of $\mu_n[\{\vec{k}/n\}]$ is not obvious. $\endgroup$
    – user111097
    Commented May 28, 2018 at 7:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .