Additive Quantization for Extreme Vector Compression

We introduce a new compression scheme for high-dimensional vectors that approximates the vectors using sums of M codewords coming from M different codebooks. We show that the proposed scheme permits efficient distance and scalar product computations between compressed and uncompressed vectors. We fu...

Full description

Saved in:
Bibliographic Details
Main Authors: Babenko, Artem, Lempitsky, Victor
Format: Conference Proceeding
Language:English
Subjects:
Additives
Approximation
Approximation error
Coding
Compressed
Compressing
Encoding
Errors
Mathematical analysis
Optimization
Pattern recognition
Quantization
Quantization (signal)
Vectors
Vectors (mathematics)
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We introduce a new compression scheme for high-dimensional vectors that approximates the vectors using sums of M codewords coming from M different codebooks. We show that the proposed scheme permits efficient distance and scalar product computations between compressed and uncompressed vectors. We further suggest vector encoding and codebook learning algorithms that can minimize the coding error within the proposed scheme. In the experiments, we demonstrate that the proposed compression can be used instead of or together with product quantization. Compared to product quantization and its optimized versions, the proposed compression approach leads to lower coding approximation errors, higher accuracy of approximate nearest neighbor search in the datasets of visual descriptors, and lower image classification error, whenever the classifiers are learned on or applied to compressed vectors.
ISSN:1063-6919
1063-6919
DOI:10.1109/CVPR.2014.124