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!



Rates of convergence for empirical quantization error
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](http://perso-math.univ-mlv.fr/users/kloeckner.benoit/papiers/DiscreteApproximation.pdf).


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$.


