四元数方法处理带野值Wahba问题：首个多项式时间最优解

本文主要探讨了基于四元数的带野值(Wahba)问题的证明最优解，针对大量存在离群值的情况。Wahba问题在计算机视觉、机器人学以及航空航天等领域有着广泛应用，如姿态估计、同步匹配等。原始问题的目标是找到最佳旋转矩阵R，使得一组向量能够与另一组向量对齐，即使在有噪声和异常值的情况下。 作者首先指出传统的最小二乘方法在处理离群值时效果不佳，因为它们对异常观测值的误差贡献过大。为了解决这个问题，他们提出了一个新颖的方法——QUASAR（QuAternion-based Semi-definite Alignment Robustness，基于四元数的半定关系鲁棒对准），该方法利用了四元数表示旋转并将其转化为二次约束二次规划（QCQP）形式。通过使用截断最小二乘（TLS）成本函数，QUASAR能够赋予正常观测值较大的权重，从而对离群值具有较好的鲁棒性。 QUASAR算法的核心在于其设计了一个凸半定规划（SDP）松弛，尽管原始优化问题高度非凸，但这种方法允许在全局范围内寻找更优解。相比于传统的RANSAC（随机采样一致性）和局部优化技术，QUASAR能够在95%的对应值是异常值的情况下仍能提供可证最优解，即SDP松弛结果是精确的。实验证明，QUASAR在理论和实际数据集上表现出色，尤其是在处理含有大量离群值的复杂场景中。 总结来说，本文的主要贡献包括： 1. 提出了一种新的方法，即QUASAR，解决了带野值的Wahba问题，通过四元数和二次规划理论提供了更为稳健的全局优化策略。 2. 证明了在存在大量离群值的情况下，QUASAR能够找到可证最优解，这在传统方法中是难以实现的。 3. 通过实验证明，QUASAR在处理噪声和异常值时，比现有的局部优化、全局离群值去除和分支定界方法更有效。 这是一项具有重要实用价值的研究，对于提高基于旋转搜索问题的鲁棒性和准确性具有重要意义。