Normalized Spectral Map Synchronization
Normalized Spectral Map Synchronization
复制标题
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Yanyao Shen;Qi-Xing Huang;N. Srebro;S. Sanghavi
中科院分区：
文献类型：
--
作者：
Yanyao Shen;Qi-Xing Huang;N. Srebro;S. Sanghavi
同步地图的算法进步对于解决可能的大规模数据集的广泛实践问题至关重要。在本文中，我们为地图同步问题的光谱技术提供了理论依据，即它将一组目标和对目标之间估计的噪声地图作为输入，并输出所有对目标之间的干净地图。我们展示了一种简单的归一化谱方法，该方法将数据矩阵的顶部特征向量块投影到映射空间，会产生令人惊讶的好结果。由于噪声被自然地建模为随机排列矩阵，该算法NormSpecSync导致与最先进的凸优化技术相竞争的理论保证，但它更有效。我们在几个应用中展示了我们的算法的实用性，在这些应用中，它在复杂性和准确性方面都是现有方法中最优的。
The algorithmic advancement of synchronizing maps is important in order to solve a wide range of practice problems with possible large-scale dataset. In this paper, we provide theoretical justifications for spectral techniques for the map synchronization problem, i.e., it takes as input a collection of objects and noisy maps estimated between pairs of objects, and outputs clean maps between all pairs of objects. We show that a simple normalized spectral method that projects the blocks of the top eigenvectors of a data matrix to the map space leads to surprisingly good results. As the noise is modelled naturally as random permutation matrix, this algorithm NormSpecSync leads to competing theoretical guarantees as state-of-the-art convex optimization techniques, yet it is much more efficient. We demonstrate the usefulness of our algorithm in a couple of applications, where it is optimal in both complexity and exactness among existing methods.