Under mild conditions on the noise level of the measurements, rotation averaging satisfies strong duality, which enables global solutions to be obtained via semidefinite programming (SDP) relaxation. However, generic solvers for SDP are rather slow in practice, even on rotation averaging instances of moderate size, thus developing specialised algorithms is vital. In this paper, we present a fast algorithm that achieves global optimality called rotation coordinate descent (RCD). Unlike block coordinate descent (BCD) which solves SDP by updating the semidefinite matrix in a row-by-row fashion, RCD directly maintains and updates all valid rotations throughout the iterations. This obviates the need to store a large dense semidefinite matrix. We mathematically prove the convergence of our algorithm and empirically show its superior efficiency over state-of-the-art global methods on a variety of problem configurations. Maintaining valid rotations also facilitates incorporating local optimisation routines for further speed-ups. Moreover, our algorithm is simple to implement; see supplementary material for a demonstration program.


翻译:在测量的噪音水平的温和条件下,平均轮换平均满足强烈的双重性,通过半限定程序(SDP)的放松可以获得全球解决方案。然而,SDP的通用解决方案在实践中相当缓慢,即使是中等规模的旋转平均情况也是如此,因此开发专业化的算法至关重要。在本文中,我们提出了一个快速算法,实现全球最佳的轮换协调下降(RCD),而区块协调下降(BCD)则通过逐行更新半限定矩阵解决SDP,刚果民盟直接维持并更新整个迭代的所有有效轮换。这避免了储存一个大密度的半限定矩阵的需要。我们从数学上证明我们算法的趋同和实验性地表明,它比各种问题配置的最新全球方法更具有优越的效率。保持有效的轮换还有助于将地方优化常规纳入进一步加速。此外,我们的算法简单易执行;见示范方案的补充材料。

0
下载
关闭预览

相关内容

坐标下降法(coordinate descent)是一种非梯度优化算法。算法在每次迭代中,在当前点处沿一个坐标方向进行一维搜索以求得一个函数的局部极小值。在整个过程中循环使用不同的坐标方向。对于不可拆分的函数而言,算法可能无法在较小的迭代步数中求得最优解。为了加速收敛,可以采用一个适当的坐标系,例如通过主成分分析获得一个坐标间尽可能不相互关联的新坐标系.
专知会员服务
50+阅读 · 2020年12月14日
专知会员服务
52+阅读 · 2020年9月7日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
【泡泡汇总】CVPR2019 SLAM Paperlist
泡泡机器人SLAM
14+阅读 · 2019年6月12日
Hierarchically Structured Meta-learning
CreateAMind
25+阅读 · 2019年5月22日
19篇ICML2019论文摘录选读!
专知
28+阅读 · 2019年4月28日
TCN v2 + 3Dconv 运动信息
CreateAMind
4+阅读 · 2019年1月8日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
23+阅读 · 2021年3月4日
Bridging Knowledge Graphs to Generate Scene Graphs
Arxiv
5+阅读 · 2020年1月7日
DPOD: Dense 6D Pose Object Detector in RGB images
Arxiv
5+阅读 · 2019年2月28日
Arxiv
7+阅读 · 2018年12月5日
VIP会员
相关VIP内容
专知会员服务
50+阅读 · 2020年12月14日
专知会员服务
52+阅读 · 2020年9月7日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
相关资讯
【泡泡汇总】CVPR2019 SLAM Paperlist
泡泡机器人SLAM
14+阅读 · 2019年6月12日
Hierarchically Structured Meta-learning
CreateAMind
25+阅读 · 2019年5月22日
19篇ICML2019论文摘录选读!
专知
28+阅读 · 2019年4月28日
TCN v2 + 3Dconv 运动信息
CreateAMind
4+阅读 · 2019年1月8日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员