Exact and stable recovery of rotations for robust synchronization
Open accessThe DOI matches its Crossref record; 41 of the 41 references it cites were found in a registry or an index.
Abstract
The synchronization problem over the special orthogonal group SO(d) consists of estimating a set of unknown rotations from noisy measurements of a subset of their pairwise ratios . 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.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Citations
Cites
Anderson, E., Bai, Z., Bischof, C., Blackford, L. S., Demmel, J., Dongarra, J., Du Croz, J., Greenbaum, A., Hammarling, S., McKenney, A., et al. (1999) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9780898719604 · Cited by 4,435
Efficient variants of the ICP algorithm
Rusinkiewicz, S., & Levoy, M. (2002) · Proceedings Third International Conference on 3-D Digital Imaging and Modeling · doi:10.1109/im.2001.924423 · Cited by 3,945
Semidefinite Relaxation of Quadratic Optimization Problems
Luo, Z.-Q., Ma, W.-K., So, A., Ye, Y., & Zhang, S. (2010) · IEEE Signal Processing Magazine · doi:10.1109/msp.2010.936019 · Cited by 3,715
Goemans, M. X., & Williamson, D. P. (1995) · Journal of the ACM · doi:10.1145/227683.227684 · Cited by 3,587
On the $O(1/n)$ Convergence Rate of the Douglas–Rachford Alternating Direction Method
He, B., & Yuan, X. (2012) · SIAM Journal on Numerical Analysis · doi:10.1137/110836936 · Cited by 881
A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
Burer, S., & Monteiro, R. D. C. (2003) · Mathematical Programming · doi:10.1007/s10107-002-0352-8 · Cited by 770
Computing the Polar Decomposition—with Applications
Higham, N. J. (1986) · SIAM Journal on Scientific and Statistical Computing · doi:10.1137/0907079 · Cited by 427
Means and Averaging in the Group of Rotations
Moakher, M. (2002) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/s0895479801383877 · Cited by 423
Alternating direction augmented Lagrangian methods for semidefinite programming
Wen, Z., Goldfarb, D., & Yin, W. (2010) · Mathematical Programming Computation · doi:10.1007/s12532-010-0017-1 · Cited by 359
Angular synchronization by eigenvectors and semidefinite programming
Singer, A. (2011) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2010.02.001 · Cited by 329
Self-citation
Cited by
Past, Present, and Future of Simultaneous Localization and Mapping: Toward the Robust-Perception Age
Cadena, C., Carlone, L., Carrillo, H., Latif, Y., Scaramuzza, D., Neira, J., Reid, I., & Leonard, J. J. (2016) · IEEE Transactions on Robotics · doi:10.1109/tro.2016.2624754 · Cited by 3,596
Past, present, and future of simultaneous localization and mapping: Toward the robust-perception age
Cadena, C., Carlone, L., Carrillo, H., Latif, Y., Scaramuzza, D., Neira, J., Reid, I. D., & Leonard, J. J. (2016) · Zurich Open Repository and Archive (University of Zurich) · doi:10.5167/uzh-138892 · Cited by 3,048
A survey of structure from motion.
Özyeşil, O., Voroninski, V., Basri, R., & Singer, A. (2017) · Acta Numerica · doi:10.1017/s096249291700006x · Cited by 489
Self-citationThe non-convex Burer-Monteiro approach works on smooth semidefinite programsPreprint
Boumal, N., Voroninski, V., & Bandeira, A. S. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1606.04970 · Cited by 288
SE-Sync: A certifiably correct algorithm for synchronization over the special Euclidean group
Rosen, D. M., Carlone, L., Bandeira, A. S., & Leonard, J. J. (2019) · The International Journal of Robotics Research · doi:10.1177/0278364918784361 · Cited by 282
Metadata
- Authors
- Wang, L., & Singer, A.
- Affiliations
- Princeton University (US)
- Corresponding author
- Wang, L.
- ORCID
- Singer, A.
- Venue
- Information and Inference
- Publisher
- Oxford University Press (OUP)
- Published
- 2013-09-27
- Volume
- 2
- Issue
- 2
- Pages
- 145-193
- ISSN
- 2049-8764 (ISSN-L)
- 2049-8772
- OpenAlex
- W2963537367
- Cited by
- 178
- References
- 40
- Citations by year
- 2026: 5 · 2025: 8 · 2024: 7 · 2023: 7 · 2022: 12 · 2021: 23 · 2020: 15 · 2019: 22 · 2018: 9 · 2017: 8 · 2016: 25 · 2015: 13 · 2014: 14 · 2013: 7
- FWCI
- 19.50
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- Information and Inference A Journal of the IMA (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- National Science Foundation (0914892)
- Alfred P. Sloan Foundation
- National Institute of General Medical Sciences (LTR DTD 06-05-2012, R01GM090200)
- Topics
- Physical Sciences › Computer Science › Signal Processing › Sparse and Compressive Sensing Techniques
- Physical Sciences › Mathematics › Numerical Analysis › Advanced Optimization Algorithms Research
- Physical Sciences › Engineering › Control and Systems Engineering › Distributed Control Multi-Agent Systems
- Keywords
- convex relaxation, alternating direction method, phase transitions, noisy measurements, node localization, spectral relaxation, semidefinite programming
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Exact and stable recovery of rotations for robust synchronization. https://app.cochat.ai/papers/10.1093/imaiai/iat005
- The paper
- Wang, L., & Singer, A. (2013). Exact and stable recovery of rotations for robust synchronization. Information and Inference. https://doi.org/10.1093/imaiai/iat005
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.