# Rates of convergence for empirical quantization error

I'm looking for error rates of convergence for approximating a probability measure $P$ by a discrete probability with at most $k$ supporting points.

The setup I'm looking at is the following. Let $X$ be an $\mathbb{R}^d$-valued random variable with distribution $P$. Fix $k\in\mathbb{N}$ and let $\mathcal{F}_k$ be the set of all Borel measurable maps $f:\mathbb{R}^d\to\mathbb{R}^d$ that take at most $k$ values. Furthermore, let $fP$ be the pushforward, or image measure of $P$ under the mapping $f\in\mathcal{F}_k$, i.e., $fP(A):=P\left(f^{-1}(A)\right)$ for all Borel measurable sets $A$.

The quantization error I'm currently looking at is with respect to the total variation (TV) distance between measures: Let $(X,\mathcal{F})$ be a measurable space and $\mu,\nu$ be two measures of $\mathcal{F}$. The TV distance between $\mu$ and $\nu$ is:

$\delta_{\mathsf{TV}}(\mu,\nu)=\sup_{A\in\mathcal{F}}|\mu(A)-\nu(A)|$.

With respect to the above, the quantization error of $P$ quantized by $f\in\mathcal{F}_k$ is set as

$e_f^{(k)}(P):=\delta_\mathsf{TV}(P,fP)$.

A couple of remarks:

1) If there are no good results for the TV distance I'm OK with switching to another proximity metric such as the Wasserstein distance, etc.

2) I'm not looking for the best quantizer that achieves the convergence rates I'll be asking about in a moment. Instead, knowing that such a quantizer (complicated as it may be) exists and to know the exact convergence rates as a function of $P$, $k$ and $d$ is sufficient for my needs (an abstract proof of existence).

So bottom line, letting $f\in\mathcal{F}_k$ be the best quantization function, what known bounds are there on the quantization error $e_f^{(k)}(P)$ in terms of $P$, $k$ and $d$ (for the TV distance based definition or any of it's alternatives)? I'm looking for a simple bound, but an explicit one (i.e., not one that involves vague constants on which all that is stated is that they depend on some parameter but not on others).

An additional question I'd like to ask concerns the special case where the dimension $d=1$ but instead of $P$, we look at the product measure $P^n$ and the quantized product measure $(fP)^n$ (i.e., we quantize $P$ to $fP$, where $f:\mathbb{R}\to\mathbb{R}$ takes at most $k$ values, and look at the $n$-fold product measure of $fP$. Namely, the quantization is preformed element-wise and we take the product of the quantized measures). What bounds on the quantization error $\delta_\mathsf{TV}\big(P^n,(fP)^n\big)$ are out there in terms of $P$, $k$ and $n$. Do the bounds simplify for this i.i.d. scenario?

I'm rather new to the study of distribution quantization and would also appreciate good (but preferably concise, not entire books :) reading material.

Thanks a lot!

• I guess your maps $f$ take value in $\mathbb{R}^d$, not $\mathbb{R}$. – Benoît Kloeckner Oct 31 '16 at 11:38
• For the original problem formulation, you are right - $f$ take values in $\mathbb{R}^d$. I've written $f:\mathbb{R}\to\mathbb{R}$ only when considering the i.i.d. scenario where $d=1$. Am I missing your point or should I further clarify that in my question? – AD1984 Oct 31 '16 at 12:16
• I was referring to a probable mistake in the second paragraph, which I edited given your answer to my comment. – Benoît Kloeckner Oct 31 '16 at 15:41

There is a large literature on this topic. A quite extensive reference is Graf and H. Luschgy, Foundations of quantization for probability distributions, Lecture Notes in Mathematics 1730. Other references are available in this paper of mine.

A first remark is that unless $P$ is atomic (in which case the problem is less interesting), using total variation distance is hopeless. For example if $P$ has no atom at all (e.g. is absolutely continuous), then $\delta_{TV}(P,fP)=1$ for all $f$ with finitely many values (take the set of values of $f$ as $A$).

Since you prefer explicitness to optimality, here is one easy result using Wasserstein distance: if $P$ is supported on the unit cube of $\mathbb{R}^d$, endowed with the $\ell_\infty$ metric for simplicity, then for all $n$ there is an $f$ taking $k=n^d$ values such that $$W_1(P,fP)\le \frac{1}{2n} =\frac{1}{2k^{1/d}}.$$ To prove this, simply cut your cube into $n^d$ smaller cubes of size $1/n$, and take $f$ that maps each point to the center of its small cube (make arbitrary measurable choices at the boundaries).

Other integers $k$ (not $d$-powers) can be handled by monotony, you still get an explicit bound $O(k^{-1/d})$ which is optimal (idem with other norms, since they are equivalent).

If $P$ is supported on a larger cube then up to a dilation the same kind of result will hold, but if $P$ is not compactly supported then you will need a moment condition for the distance to be finite for any $f$. Then a trucation argument will give you reasonable estimates.

An interesting point is that if $\mathbb{R}^d$ is endowed with the Euclidean metric, then determining the optimal constant in the $O(k^{-1/d})$ is open even for $P$ uniform over the unit cube for all dimensions $d$ except $d=1$, $d=2$ and possibly $d=3$ (I don't remember). For most Wasserstein distances $W_p$, I am pretty sure the answer is unknown in dimension $d=3$.

• Thanks for your answer. I would like the $P$ measure to also (but not only) account for the Gaussian measure so the case where it is not compactly supported is of interest to me. What moment conditions would one have to impose to get the reasonable estimates you've mentioned? Could you write out the expression of those estimates or refer me to a text when I can find them? – AD1984 Oct 31 '16 at 12:29
• @ZivGoldfeld: you just have to take a large cube, and project everything outside it to any point inside or to the outmost values of $f$. With a Gaussian measure, whose tail is light, if the cube is large the cost will be small. I won't write it for you as I don't have much time, and it is a good exercise -- you should do it. More generally, the bare minimum moment condition would be for $\int d(x_0,x) dP(x)$ to be finite, but to obtain explicit estimates it might be useful to bound the integral of any larger power of the distance to a basepoint. – Benoît Kloeckner Oct 31 '16 at 15:45
• Thanks a lot for your answers, they are extremely helpful. I'll do the exercise. I have one last question, if you don't mind: What if $P$ is actually a product measure, i.e., $P=Q^n$, where $Q$ is a measure on $\mathcal{B}(\mathbb{R})$ and the quantization functions in $\mathcal{F}_k$ are $f:\mathbb{R}\to\mathbb{R}$ (rather than $\mathbb{R}^d$-valued function). Applying $f\in\mathcal{F}_k$ on $Q$ and taking the product to gives $(fQ)^n$. What bounds are there on the Wasserstein distance $W_p(Q^n,(fQ)^n)$ (or for $p=1$ in particular)? – AD1984 Oct 31 '16 at 20:56
• @ZivGoldfeld: there is not more to hope here, as the uniform case is a product and the order of magnitude of the bound I gave is tight in this case. Of course, given your notation you replace $n$ by $k$, i.e. the bound is in $1/k$, but that is only an artifact of the notation. The important point is that you don't loose either, even while you restrict the quantization function quite a bit by asking them to be product. The reason for this is that the quantization I proposed is already a product. – Benoît Kloeckner Oct 31 '16 at 21:19
• Perfect. Thanks a lot again! The $n$ was a typo, it should have been $k$ all the way. Where can I read proofs of these results? Would the references you mentioned contain them? – AD1984 Oct 31 '16 at 21:35