Abstract
Product quantization (PQ) (and its variants) has been effectively used to encode high-dimensional data into compact
codes for many problems in vision. In principle, PQ decomposes the given data into a number of lower-dimensional
subspaces where the quantization proceeds independently
for each subspace. While the original PQ approach does
not explicitly optimize for these subspaces, later proposals
have argued that the performance tends to benefit significantly if such subspaces are chosen in an optimal manner. Despite such consensus, existing approaches in the
literature diverge in terms of which specific properties of
these subspaces are desirable and how one should proceed
to solve/optimize them. Nonetheless, despite the empirical
support, there is less clarity regarding the theoretical properties that underlie these experimental benefits for quantization problems in general. In this paper, we study the quantization problem in the setting where subspaces are orthogonal and show that this problem is intricately related to a
specific type of spectral decomposition of the data. This insight not only opens the door to a rich body of work in spectral analysis, but also leads to distinct computational benefits. Our resultant biresolution spectral formulation captures both the subspace projection error as well as the quantization error within the same framework. After a reformulation, the core steps of our algorithm involve a simple
eigen decomposition step, which can be solved efficiently.
We show that our method performs very favorably against
a number of state of the art methods on standard data sets