On Recovery Guarantees for Angular Synchronization

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 prob...

Full description

Saved in:
Bibliographic Details
Published in:The Journal of fourier analysis and applications 2021-04, Vol.27 (2), Article 31
Main Authors: Filbir, Frank, Krahmer, Felix, Melnyk, Oleh
Format: Article
Language:English
Subjects:
Abstract Harmonic Analysis
Approximations and Expansions
Eigenvectors
Fourier Analysis
Graphs
Harmonic Analysis on Combinatorial Graphs
Mathematical Methods in Physics
Mathematics
Mathematics and Statistics
Optimization
Partial Differential Equations
Recovery
Signal,Image and Speech Processing
Synchronism
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1069-5869
1531-5851
DOI:10.1007/s00041-021-09834-1