COMPETITIVE LEARNING AND SOFT COMPETITION FOR VECTOR QUANTIZER DESIGN

Vector quantizer (VQ) design is a multidimensional optimization problem in which a distortion function is minimized. The most widely used technique for designing vector quantizers is the generalized Lloyd algorithm (GLA), an iterative descent algorithm which monotonically decreases the distortion function towards a local minimum. One major drawback of the GLA, and of any descent minimization technique, is the "greedy" nature of the search, generally resulting in a nonglobal local optimum. A promising alternative to the GLA is the Kohonen learning algorithm (KLA), originally proposed for unsupervised training of neural networks. The KLA is an "on-line" algorithm where the codebook is designed while training data is arriving, and the reduction of the distortion function is not necessarily monotonic. In this paper we provide a convergence analysis for the KLA with respect to VQ optimality criteria and introduce a stochastic relaxation technique which produces the global minimum but is computationally expensive. By incorporating the principles of the stochastic approach into the KLA, a new deterministic VQ design algorithm, called the soft competition scheme (SCS), is introduced. Experimental results are presented where the SCS consistently provided better codebooks than the GLA, even when the same computation time was used for both algorithms. The SCS may therefore prove to be a valuable alternative to the GLA for VQ design.