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-citationOrthogonal Procrustes Rotation for Two or More Matrices
Ten Berge, J. M. F. (1977) · Psychometrika · doi:10.1007/bf02294053 · Cited by 320
Robust Rotation and Translation Estimation in Multiview Reconstruction
Martinec, D., & Pajdla, T. (2007) · 2007 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2007.383115 · Cited by 319
Consensus Optimization on Manifolds
Sarlette, A., & Sepulchre, R. (2009) · SIAM Journal on Control and Optimization · doi:10.1137/060673400 · Cited by 270
Vector diffusion maps and the connection Laplacian
Singer, A., & Wu, H. ‐. (2012) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.21395 · Cited by 251
Self-citationHow to generate random matrices from the classical compact groups
Mezzadri, F. (2007) · Cited by 198
L1 rotation averaging using the Weiszfeld algorithm
Hartley, R., Aftab, K., & Trumpf, J. (2011) · CVPR 2011 · doi:10.1109/cvpr.2011.5995745 · Cited by 179
Singer, A., & Shkolnisky, Y. (2011) · SIAM Journal on Imaging Sciences · doi:10.1137/090767777 · Cited by 178
Self-citationGlobal Motion Estimation from Point Matches
Arie-Nachimson, M., Kovalsky, S. Z., Kemelmacher-Shlizerman, I., Singer, A., & Basri, R. (2012) · 2012 Second International Conference on 3D Imaging, Modeling, Processing, Visualization & Transmission · doi:10.1109/3dimpvt.2012.46 · Cited by 170
Self-citationA Cheeger Inequality for the Graph Connection Laplacian
Bandeira, A. S., Singer, A., & Spielman, D. A. (2013) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/120875338 · Cited by 158
Self-citationOn the concentration of eigenvalues of random symmetric matrices
Alon, N., Krivelevich, M., & Vu, V. H. (2002) · Israel Journal of Mathematics · doi:10.1007/bf02785860 · Cited by 133
On Approximating Complex Quadratic Optimization Problems via Semidefinite Programming Relaxations
So, A. M., Zhang, J., & Ye, Y. (2005) · Lecture notes in computer science · doi:10.1007/11496915_10 · Cited by 111
Sensor network localization by eigenvector synchronization over the euclidean group
Cucuringu, M., Lipman, Y., & Singer, A. (2012) · ACM Transactions on Sensor Networks · doi:10.1145/2240092.2240093 · Cited by 110
Self-citationA Novel M-Estimator for Robust PCAPreprint
Zhang, T., & Lerman, G. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1112.4863 · Cited by 110
Distributed image-based 3-D localization of camera sensor networks
Tron, R., & Vidal, R. (2009) · Proceedings of the 48h IEEE Conference on Decision and Control (CDC) held jointly with 2009 28th Chinese Control Conference · doi:10.1109/cdc.2009.5400405 · Cited by 102
Viewing Direction Estimation in Cryo-EM Using Synchronization
Shkolnisky, Y., & Singer, A. (2012) · SIAM Journal on Imaging Sciences · doi:10.1137/120863642 · Cited by 96
Self-citationCramer-Rao bounds for synchronization of rotations
Boumal, N., Singer, A., Absil, P. A., & Blondel, V. D. (2014) · Information and Inference · doi:10.1093/imaiai/iat006 · Cited by 89
Self-citationEigenvector synchronization, graph rigidity and the molecule problem
Cucuringu, M., Singer, A., & Cowburn, D. (2012) · Information and Inference A Journal of the IMA · doi:10.1093/imaiai/ias002 · Cited by 85
Self-citationSums of random symmetric matrices and quadratic optimization under orthogonality constraints
Nemirovski, A. S. (2006) · Mathematical Programming · doi:10.1007/s10107-006-0033-0 · Cited by 74
Moment inequalities for sums of random matrices and their applications in optimization
So, A. M. (2009) · Mathematical Programming · doi:10.1007/s10107-009-0330-5 · Cited by 72
Eigenvector synchronization, graph rigidity and the molecule problem
Cucuringu, M., Singer, A., & Cowburn, D. (2012) · Cited by 71
Self-citationViewing Angle Classification of Cryo-Electron Microscopy Images Using Eigenvectors
Singer, A., Zhao, Z., Shkolnisky, Y., & Hadani, R. (2011) · SIAM Journal on Imaging Sciences · doi:10.1137/090778390 · Cited by 69
Self-citationMax cut and the smallest eigenvalue
Trevisan, L. (2009) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1536414.1536452 · Cited by 58
On orthogonal linear ?1 approximation
Sp�th, H., & Watson, G. A. (1987) · Numerische Mathematik · doi:10.1007/bf01400354 · Cited by 47
Convex Recovery From Interferometric Measurements
Demanet, L., & Jugnon, V. (2017) · IEEE Transactions on Computational Imaging · doi:10.1109/tci.2017.2688923 · Cited by 43
Least orthogonal absolute deviations
Nyquist, H. (1988) · Computational Statistics & Data Analysis · doi:10.1016/0167-9473(88)90076-x · Cited by 40
Efficient rounding for the noncommutative grothendieck inequality
Naor, A., Regev, O., & Vidick, T. (2013) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2488608.2488618 · Cited by 38
Robust Computation of Linear Models, or How to Find a Needle in a Haystack
Lerman, G., McCoy, M. B., Tropp, J. A., & Zhang, T. (2012) · Defense Technical Information Center (DTIC) · doi:10.21236/ada563093 · Cited by 35
Angular embedding: From jarring intensity differences to perceived luminance
Yu, S. X. (2009) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2009.5206673 · Cited by 32
Wide-Sense Estimation on the Special Orthogonal Group
Chiuso, A., Picci, G., & Soatto, S. (2008) · Communications in Information and Systems · doi:10.4310/cis.2008.v8.n3.a1 · Cited by 25
Estimation and Registration on GraphsPreprint
Howard, S. D., Cochran, D., Moran, B., & Cohen, F. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1010.2983 · Cited by 15
A Matrix Equation for Resolvents of Random Matrices with Independent Blocks
Girko, V. L. (1996) · Theory of Probability and Its Applications · doi:10.1137/1140073 · Cited by 7
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
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.