Fast approximations to discrete optimal quantization (Q1117894)

An O(N log K) and an \(O(N+K \log (N/K))\) algorithm are proposed to approximate the optimal K-level quantizer for a discrete density of N points. The low time complexities are achieved by approximating an optimal K-level quantizer by K-1 optimal bilevel quantizers recursively. For well-behaved discrete densities, the algorithms perform satisfactorily in terms of optimality.