Vector quantizer design by constrained global optimization

Central to vector quantization is the design of optimal code book. The construction of a globally optimal code book has been shown to be NP-complete. However, if the partition halfplanes are restricted to be orthogonal to the principal direction of the training vectors, then the globally optimal K-partition of a set of N D-dimensional data points can be computed in O((N+KM/sup 2/)D) time by dynamic programming, where M is the intensity …