Exact and stable recovery of rotations for robust synchronization

Lanhui Wang, Amit Singer

Research output: Contribution to journalArticle

68 Scopus citations

Abstract

The synchronization problem over the special orthogonal group SO(d) consists of estimating a set of unknown rotations R1, R2,... , Rn from noisy measurements of a subset of their pairwise ratios Ri1Rj. The problem has found applications in computer vision, computer graphics and sensor network localization, among others. Its least squares solution can be approximated by either spectral relaxation or semidefinite programming followed by a rounding procedure, analogous to the approximation algorithms of Max-Cut. The contribution of this paper is three-fold: first, we introduce a robust penalty function involving the sum of unsquared deviations and derive a relaxation that leads to a convex optimization problem; secondly, we apply the alternating direction method to minimize the penalty function. Finally, under a specific model of the measurement noise and for both complete and random measurement graphs, we prove that the rotations are exactly and stably recovered, exhibiting a phase transition behavior in terms of the proportion of noisy measurements. Numerical simulations confirm the phase transition behavior for our method as well as its improved accuracy compared with existing methods.

Original languageEnglish (US)
Pages (from-to)145-193
Number of pages49
JournalInformation and Inference
Volume2
Issue number2
DOIs
StatePublished - Jan 1 2013

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics
  • Analysis
  • Applied Mathematics
  • Statistics and Probability
  • Numerical Analysis

Keywords

  • Alternating direction method
  • Least unsquared deviation
  • Semidefinite relaxation
  • Synchronization of rotations

Fingerprint Dive into the research topics of 'Exact and stable recovery of rotations for robust synchronization'. Together they form a unique fingerprint.

  • Cite this