Random Projection Trees for Vector Quantization
A simple and computationally efficient scheme for tree-structured vector quantization is presented. Unlike previous methods, its quantization error depends only on the intrinsic dimension of the data distribution, rather than the apparent dimension of the space in which the data happen to lie. In this paper, the authors are interested in techniques that automatically adapt to intrinsic low dimensional structure without having to explicitly learn this structure. They describe an algorithm for designing a tree-structured vector quantizer whose quantization error is k−1/O(d) (Times the quantization error induced by a single codeword); that is to say, its error rate depends only on the low intrinsic dimension rather than the high apparent dimension.