Product quantization (PQ) coupled with a space rotation, is widely used in
modern approximate nearest neighbor (ANN) search systems to significantly
compress the disk storage for embeddings and speed up the inner product
computation. Existing rotation learning methods, however, minimize quantization
distortion for fixed embeddings, which are not applicable to an end-to-end
training scenario where embeddings are updated constantly. In this paper, based
on geometric intuitions from Lie group theory, in particular the special
orthogonal group $SO(n)$, we propose a family of block Givens coordinate
descent algorithms to learn rotation matrix that are provably convergent on any
convex objectives. Compared to the state-of-the-art SVD method, the Givens
algorithms are much more parallelizable, reducing runtime by orders of
magnitude on modern GPUs, and converge more stably according to experimental
studies. They further improve upon vanilla product quantization significantly
in an end-to-end training scenario.

本文提出了一种基于几何直觉的块 Givens 坐标下降算法，用于学习旋转矩阵，具有可证明的收敛性和更高的并行性，可显著优化最近邻搜索中的产品量化方法，在端到端训练方案中取得了更好的性能。