Linde-Buzo-Gray algorithm

The Linde-Buzo-Gray algorithm is an iterative vector quantization method named after its creators Yoseph Linde, Andres Buzo and Robert M. Gray, who designed it in 1980. Its purpose is to improve a small set of vectors, called a codebook, so that it represents a much larger training set of vectors and is locally optimal. It combines Lloyd's algorithm with a splitting step: each code vector in the current codebook is split into two by adding a small perturbation, which doubles the codebook size, and Lloyd's iteration then assigns training vectors to their nearest code vector and moves each code vector to the centroid of its cluster until the representation error stops improving. Because every old code vector is kept in the new codebook, the enlarged codebook must be at least as good as the one before it. The article presents the procedure as short pseudocode.