[IEEE Trans. on Signal Processing, February 1992, pp. 294-309]
Competitive Learning and Soft Competition
for Vector Quantizer Design
Eyal Yair, Kenneth Zeger, and Allen Gersho
Abstract
Vector quantizer (VQ) design is a multi-dimensional 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.