第 113 题：OPQ的正交优化，旋转矩阵对向量分布的适配？
题目
OPQ的正交优化，旋转矩阵对向量分布的适配？
完整讲解
一、PQ 的假设与各向异性问题
PQ 假设各子空间独立且每段内向量分布适合 k-means。若原始向量各维度强相关或方差分布不均（各向异性），直接按坐标分段会导致：某些段方差极大、量化误差大；段间仍有依赖，独立 k-means 不是最优。OPQ（Optimized Product Quantization） 通过正交旋转 $\boldsymbol{R}^\top \boldsymbol{x}$（$\boldsymbol{R}$ 正交矩阵）将向量变换到更「均衡」的空间，再做 PQ，使各段方差更接近、相关性减弱。
二、正交优化与目标
目标：在给定 PQ 段划分下，最小化重构误差（或量化误差）。设旋转 $\boldsymbol{R}$、码本 ${\mathcal{C}_j}$，优化
\(\min_{\boldsymbol{R}, \{\mathcal{C}_j\}} \sum_i \left\| \boldsymbol{R}^\top \boldsymbol{x}_i - \hat{\boldsymbol{x}}_i \right\|^2,\)
其中 $\hat{\boldsymbol{x}}_i$ 为 $\boldsymbol{R}^\top \boldsymbol{x}_i$ 经 PQ 量化后的重构。正交约束 $\boldsymbol{R}^\top \boldsymbol{R} = \boldsymbol{I}$ 保证旋转不改变范数、保持距离关系，且可逆、无尺度膨胀。
三、旋转矩阵对向量分布的适配
- 效果：好的 $\boldsymbol{R}$ 使旋转后各段方差更均衡（各向同性），每段 k-means 的量化误差更均匀；同时可减弱段间相关，使「分段独立」假设更成立。
- 求解：常用交替优化——固定 $\boldsymbol{R}$ 更新码本（k-means）；固定码本更新 $\boldsymbol{R}$（闭式解或梯度，保持正交用 Procrustes 或 Cayley 参数化）。多次迭代至收敛。
- 初始化：$\boldsymbol{R}$ 可取单位阵（即先做一次 PQ 再优化）；或用 PCA 旋转（主成分对齐坐标轴），再微调。
四、工程要点
- OPQ 比 PQ 多一步旋转与旋转矩阵存储（$d \times d$）；训练与编码时多一次 $\boldsymbol{R}^\top \boldsymbol{x}$，查询时对 query 同样旋转后再查表，精度通常明显优于裸 PQ。
- 与 IVF 结合时：先 OPQ 量化，再在 IVF 粗筛后的桶内做 PQ 距离精排。
面试要点
- 能说明 PQ 各向异性问题及 OPQ 用正交旋转 $\boldsymbol{R}^\top \boldsymbol{x}$ 再做 PQ 的思路。
- 能写出最小化重构误差、正交约束 $\boldsymbol{R}^\top \boldsymbol{R}=\boldsymbol{I}$，以及交替优化码本与 $\boldsymbol{R}$。
- 能说清旋转使各段方差均衡、减弱相关，以及 OPQ 相对 PQ 的精度与开销。
记忆要点
- OPQ：正交旋转 $\boldsymbol{R}^\top \boldsymbol{x}$ 后再 PQ，缓解各向异性、均衡各段方差。
- 目标：最小化旋转后向量的 PQ 重构误差；$\boldsymbol{R}$ 正交保持范数、可逆。
- 交替优化 $\boldsymbol{R}$ 与码本；初始化可用单位阵或 PCA；精度优于 PQ、多存 $d\times d$ 与一次旋转。