Алгоритм Линде – Дайвера – Грея

Алгоритм Линде-Бузо-Грея (назван в честь его создателей Йозефа Линде, Андреса Бузо и Роберта М. Грея , которые разработали его в 1980 году) ^{[ 1 ]} — это итеративный алгоритм векторного квантования, предназначенный для улучшения небольшого набора векторов (кодовой книги) для представления большего набора векторов (обучающего набора), так что он будет локально оптимальным . Он сочетает в себе алгоритм Ллойда с методом разделения, при котором более крупные кодовые книги создаются из меньших кодовых книг путем разделения каждого кодового вектора на две части. Основная идея алгоритма заключается в том, что при разделении кодовой книги таким образом, чтобы присутствовали все кодовые векторы из предыдущей кодовой книги, новая кодовая книга должна быть такой же хорошей, как предыдущая, или лучше. ^{[ 2 ]}^{: 361–362}

Описание

Алгоритм Линде – Бьюзо – Грея можно реализовать следующим образом:

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

Ссылки

^ Линде, Ю.; Бузо, А.; Грей, Р. (1980). «Алгоритм проектирования векторного квантователя» . Транзакции IEEE в области коммуникаций . 28 (1): 84–95. дои : 10.1109/TCOM.1980.1094577 . ISSN 0090-6778 . S2CID 18530691 . Проверено 28 декабря 2023 г.
^ Грей, Р.; Гершо, А. (1992). Векторное квантование и сжатие сигналов (1-е изд.). Спрингер. дои : 10.1007/978-1-4615-3626-0 . ISBN 978-1-4613-6612-6 .

[1] Линде, Ю.; Бузо, А.; Грей, Р. (1980). «Алгоритм проектирования векторного квантователя» . Транзакции IEEE в области коммуникаций . 28 (1): 84–95. дои : 10.1109/TCOM.1980.1094577 . ISSN 0090-6778 . S2CID 18530691 . Проверено 28 декабря 2023 г.

[gray1992-2] Грей, Р.; Гершо, А. (1992). Векторное квантование и сжатие сигналов (1-е изд.). Спрингер. дои : 10.1007/978-1-4615-3626-0 . ISBN 978-1-4613-6612-6 .

[ 1 ]

[ 2 ]