VQ

Vector quantization (VQ) is a quantization technique used in digital signal processing and data compression. It encodes a large set of input vectors by mapping each to a single representative vector from a finite codebook. The codebook contains codewords that stand for typical data patterns, and the encoding process replaces each input vector with the index of its closest codeword.

A codebook is typically learned from a dataset of training vectors. The most common method is the Linde-Buzo-Gray (LBG) algorithm, which is closely related to k-means clustering. Encoding involves finding the nearest codeword to each input vector, usually using Euclidean distance, and decoding reconstructs the data by replacing indices with their corresponding codewords. The codebook size controls the rate: larger codebooks yield higher fidelity but require more bits per vector.

VQ has been used in image and video compression, speech and audio coding, and certain pattern-recognition tasks. Variants and enhancements include multistage vector quantization (MSVQ) to reduce search complexity, product quantization (PQ) to handle high-dimensional vectors, and residual or hierarchical VQ to improve quality.

Advantages of VQ include good exploitation of correlations within blocks of data and relatively simple decoders. Limitations involve the computational burden of designing an optimal codebook, the expense of searching large codebooks for each vector, and sensitivity to training data. High-dimensional data suffer from the curse of dimensionality, demanding large memory for codebooks. While influential in early coding systems, modern standards often favor transform-based techniques, with VQ remaining of historical and specialized use.