Poster
Normalized Spectral Map Synchronization
Yanyao Shen · Qixing Huang · Nati Srebro · Sujay Sanghavi

Mon Dec 5th 06:00 -- 09:30 PM @ Area 5+6+7+8 #117 #None
in Monday Posters »

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.

Keywords: Spectral Methods · (Application) Computer Vision

Author Information

Yanyao Shen (UT Austin)
Qixing Huang (Toyota Technological Institute at Chicago)
Nati Srebro (TTI-Chicago)
Sujay Sanghavi (UT-Austin)

More from the Same Authors