Linde–Buzo–Gray algorithm

This article relies too much on references to primary sources. Please improve this by adding secondary or tertiary sources. (June 2012) (Learn how and when to remove this template message)

The Linde–Buzo–Gray algorithm (introduced by Yoseph Linde, Andrés Buzo and Robert M. Gray in 1980) is a vector quantization algorithm to derive a good codebook.

It is similar to the k-means method in data clustering.

The algorithm[]

At each iteration, each vector is split into two new vectors.

• A initial state: centroid of the training sequence;
• B initial estimation #1: code book of size 2;
• C final estimation after LGA: Optimal code book with 2 vectors;
• D initial estimation #2: code book of size 4;
• E final estimation after LGA: Optimal code book with 4 vectors;

References[]

• The original paper describing the algorithm, as an extension to Lloyd's algorithm:
  • Linde, Y.; Buzo, A.; Gray, R. (1980). "An Algorithm for Vector Quantizer Design". IEEE Transactions on Communications. 28: 84–95. doi:10.1109/TCOM.1980.1094577.