On Recovery Guarantees for Angular Synchronization
Open Access
- 5 April 2021
- journal article
- research article
- Published by Springer Nature in Journal of Fourier Analysis and Applications
- Vol. 27 (2) , 1-26
Abstract
The angular synchronization problem of estimating a set of unknown angles from their known noisy pairwise differences arises in various applications. It can be reformulated as an optimization problem on graphs involving the graph Laplacian matrix. We consider a general, weighted version of this problem, where the impact of the noise differs between different pairs of entries and some of the differences are erased completely; this version arises for example in ptychography. We study two common approaches for solving this problem, namely eigenvector relaxation and semidefinite convex relaxation. Although some recovery guarantees are available for both methods, their performance is either unsatisfying or restricted to the unweighted graphs. We close this gap, deriving recovery guarantees for the weighted problem that are completely analogous to the unweighted version.Keywords
All Related Versions
Funding Information
- Helmholtz Zentrum München - Deutsches Forschungszentrum für Gesundheit und Umwelt (GmbH)
This publication has 22 references indexed in Scilit:
- Alternating projection, ptychographic imaging and phase synchronizationApplied and Computational Harmonic Analysis, 2016
- Sync-Rank: Robust Ranking, Constrained Ranking and Rank Aggregation via Eigenvector and SDP SynchronizationIEEE Transactions on Network Science and Engineering, 2016
- Phase Retrieval with PolarizationSIAM Journal on Imaging Sciences, 2014
- A Cheeger Inequality for the Graph Connection LaplacianSIAM Journal on Matrix Analysis and Applications, 2013
- Angular synchronization by eigenvectors and semidefinite programmingApplied and Computational Harmonic Analysis, 2011
- Probabilistic Analysis of Semidefinite Relaxation for Binary Quadratic MinimizationSIAM Journal on Optimization, 2010
- On approximating complex quadratic optimization problems via semidefinite programming relaxationsMathematical Programming, 2006
- Distributed Clock Synchronization over Wireless Networks: Algorithms and Analysis2006
- Complex Quadratic Optimization and Semidefinite ProgrammingSIAM Journal on Optimization, 2006
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programmingJournal of the ACM, 1995