Suppose the standard normal X (in R^d) is quantized by some f : R^d -> [K], and mu_k is the conditional mean of X given f(X) = k. Then on average, the squared length of mu_{f(X)} is at most log(K). The same is true for any subgaussian X.
@djhsu f must assign contiguous intervals of X to {1,...,K}? Suppose d=1 and we assign X < 10^6 to k=1, X in (k-1)e6 to ke6 to k for k=2,...,10 and X>1e7 to k=11. Then mu0 is approx 0 (though slightly less), all other mu_k should be > (k-1)e6, so the average squared mu_k would be 25e12 which is > log 11. Does that check out? What am I missing. Must be something obvious.
@djhsu oh is the average weighted by interval probability?
@kristinmbranson Yes, the average is weighted by Pr(f(X)=k) rather than 1/K for all k.
@kristinmbranson Also "log" uses some mysterious base that I haven't revealed (but it's some absolute constant > 1, I swear!)
@djhsu OK post-shower Kristin buys this, and thinks it would be nice if the log base is e :). What are the implications of this? When should I be arbitrarily quantizing my data? This should hold for any function f: X^d - > [K], correct?
@kristinmbranson I agree, but I forgot the constant :-) Yes, it puts a limit on how well you can quantize "unstructured" data, with any f: not much better than the trivial quantizer (mu=0). Can contrast this to what happens with structured data (e.g., mixture of K Gaussians).
@djhsu I see, so quantizing my Gaussian data, or more generally further quantizing beyond my GMM modes, won't give me much representational power. Interesting! Thanks for sharing!! 
(Sorry, just found the custom emojis...)
