Abstract:
We consider the $K$-clustering problem with the $\ell_2^2$ distortion measure, also known as the problem of optimal fixed-rate vector quantizer design. We provide a deterministic approximation algorithm which works for all dimensions $d$ and which, given a data set of size $n$, computes in time ${\rm poly}(K)(d/\ep)^{O(d)} n \log \log n +(d/\ep)^{O(Kd)}$ a solution of distortion at most $1+\ep$ times optimal. The key tool is construction of a new kind of representation called a "data net". A variety of applications of this object are discussed.