TY - JOUR
T1 - Exact and stable recovery of rotations for robust synchronization
AU - Wang, Lanhui
AU - Singer, Amit
N1 - Funding Information:
This work was supported by the National Science Foundation (DMS-0914892); the Air Force Office of Scientific Research (FA9550-12-1-0317); the National Institute of General Medical Sciences (R01GM090200); the Simons Foundation (LTR DTD 06-05-2012); and the Alfred P. Sloan Foundation.
Publisher Copyright:
© The authors 2013. Published by Oxford University Press on behalf of the Institute of Mathematics and its Applications. All rights reserved.
PY - 2013/12/1
Y1 - 2013/12/1
N2 - 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 R−i1Rj. 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.
AB - 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 R−i1Rj. 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.
KW - Alternating direction method
KW - Least unsquared deviation
KW - Semidefinite relaxation
KW - Synchronization of rotations
UR - http://www.scopus.com/inward/record.url?scp=85071591797&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85071591797&partnerID=8YFLogxK
U2 - 10.1093/imaiai/iat005
DO - 10.1093/imaiai/iat005
M3 - Article
AN - SCOPUS:85071591797
VL - 2
SP - 145
EP - 193
JO - Information and Inference
JF - Information and Inference
SN - 2049-8772
IS - 2
ER -