Linde–Buzo–Gray algorithm

<h2 id="description">Description</h2>
The Linde–Buzo–Gray algorithm may be implemented as follows:

algorithm linde-buzo-gray is
 input: set of training vectors training, codebook to improve old-codebook
 output: codebook that is twice the size and better or as good as old-codebook
 
 new-codebook ← {}
 
 for each old-codevector in old-codebook do
 insert old-codevector into new-codebook
 insert old-codevector + 𝜖 into new-codebook where 𝜖 is a small vector
 
 return lloyd(new-codebook, training)

algorithm lloyd is
 input: codebook to improve, set of training vectors training
 output: improved codebook
 
 do
 previous-codebook ← codebook
 
 clusters ← divide training into |codebook| clusters, where each cluster contains all vectors in training who are best represented by the corresponding vector in codebook
 
 for each cluster cluster in clusters do
 the corresponding code vector in codebook ← the centroid of all training vectors in cluster
 
 while difference in error representing training between codebook and previous-codebook > 𝜖
 
 return codebook

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Linde, Y.; Buzo, A.; Gray, R. (1980). "An Algorithm for Vector Quantizer Design". IEEE Transactions on Communications. 28 (1): 84–95. doi:10.1109/TCOM.1980.1094577. ISSN 0090-6778. S2CID 18530691. Retrieved 2023-12-28. <a href="https://ieeexplore.ieee.org/document/1094577" target="_blank">https://ieeexplore.ieee.org/document/1094577</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Gray, R.; Gersho, A. (1992). Vector Quantization and Signal Compression (1 ed.). Springer. doi:10.1007/978-1-4615-3626-0. ISBN 978-1-4613-6612-6. <a href="978-1-4613-6612-6" target="_blank">978-1-4613-6612-6</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
</ol>

Linde–Buzo–Gray algorithm open-in-new

Linde–Buzo–Gray algorithm