Kolmogorov complexity of spherical vector quantizers

Abstract

In this paper, we investigate memory complexity of spherical vector quantizer from Kolmogorov's perspective. The method for expressing the quantizer as binary string is proposed and minimal description length of the string is considered as Kolmogorov complexity of the quantizer. The Kolmogorov complexity is compared to memory requirements of two main algorithms for spherical vector quantizer design: uniform spherical quantizer and generalized Lloyd-Max's algorithm. It is proven that first of them has the minimal memory requirements needed for spherical quantizer realization, while the other upper bounds the theoretical minimal description length of the quantizer.