Chamfer距离不再只算欧氏范数:斜投影嵌入把任意ℓp的近似压到近线性时间
核心概要
Chamfer距离衡量两个点集之间的不相似度,此前的高效近似算法主要针对欧氏范数,扩展到一般ℓp范数仍是未解问题。这项工作用弱保证的斜投影嵌入把ℓp下的Chamfer距离归约到低维ℓp实例,在高维情形借助快速矩阵乘法加速嵌入,得到近线性时间的近似算法;欧氏情形则用Toeplitz矩阵构造的快速Johnson-Lindenstrauss变换降维,运行时与已有最优结果持平。
深度剖析
一般ℓp范数下的Chamfer距离现在有了近线性时间的近似算法,不再局限于欧氏情形。 此前针对Chamfer距离的高效近似主要建立在欧氏范数上,把同样的效率推广到一般ℓp范数仍是公开问题。 算法把ℓp实例归约到低维ℓp实例,总运行时间随输入规模近线性增长,并给出近似比保证。
做法是先用一个弱保证的随机投影把点集压到低维,再在低维空间里跑已有的Chamfer求解器。 所用斜投影嵌入只保证不收缩和期望误差有界,并不像标准Johnson-Lindenstrauss变换那样双向集中。 Chamfer距离是最近邻距离之和,逐对距离的不收缩足以让嵌入后的距离保持住原距离,高维时嵌入矩阵用快速矩阵乘法施加。
欧氏情形改用Toeplitz矩阵构造的快速Johnson-Lindenstrauss变换降维,再在低维空间重新分析原有的四叉树估计框架。 此前的欧氏Chamfer算法在原始维度上运行,降维后四叉树估计的近似因子需要重新论证。 降维只需常数级失真,因为该变换只用于四叉树阶段,常数失真可被本就粗糙的近似因子吸收,最终运行时间与已有最优结果持平。
启示与展望
结论针对大小为n的点集在ℓp范数下的有向Chamfer距离,给出近似比与总运行时间的理论保证;实验在合成高维点集和300维GloVe词嵌入上完成,运行于单块NVIDIA T4 GPU。
一般ℓp情形下,上界与朴素下界之间仍留有因子差距,作者将其列为待解决的问题;实验评估限于合成数据加GloVe和单GPU设置,作者提出应在更大范围的点云与检索数据集上评估。
