Linde–Buzo–Gray algorithm

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:
  • Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1109/TCOM.1980.1094577, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1109/TCOM.1980.1094577 instead.

External links

• http://www.data-compression.com/vq.html#lbg