Tightness of the maximum likelihood semidefinite relaxation for angular synchronization

Abstract

Maximum likelihood estimation problems are, in general, intractable optimization problems. As a result, it is common to approximate the maximum likelihood estimator (MLE) using convex relaxations. In some cases, the relaxation is tight: it recovers the true MLE. Most tightness proofs only apply to situations where the MLE exactly recovers a planted solution (known to the analyst). It is then sufficient to establish that the optimality conditions hold at the planted signal. In this paper, we study an estimation problem (angular synchronization) for which the MLE is not a simple function of the planted solution, yet for which the convex relaxation is tight. To establish tightness in this context, the proof is less direct because the point at which to verify optimality conditions is not known explicitly. Angular synchronization consists in estimating a collection of $n$ phases, given noisy measurements of the pairwise relative phases. The MLE for angular synchronization is the solution of a (hard) non-bipartite Grothendieck problem over the complex numbers. We consider a stochastic model for the data: a planted signal (that is, a ground truth set of phases) is corrupted with non-adversarial random noise. Even though the MLE does not coincide with the planted signal, we show that the classical semidefinite relaxation for it is tight, with high probability. This holds even for high levels of noise.

2 figures

References in corpus (6)

• Sharp nonasymptotic bounds on the norm of random matrices with independent entries
• Spectral distributions of adjacency and Laplacian matrices of random graphs
• A Riemannian low-rank method for optimization over semidefinite matrices with block-diagonal constraints
• Sync-Rank: Robust Ranking, Constrained Ranking and Rank Aggregation via Eigenvector and Semidefinite Programming Synchronization
• Open problem: Tightness of maximum likelihood semidefinite relaxations
• Disentangling Orthogonal Matrices

Cited by in corpus (49)

• Transmit MIMO Radar Beampattern Design Via Optimization on the Complex Circle Manifol
• Nonconvex phase synchronization
• Universal Inference
• Phase Transitions in Semidefinite Relaxations
• Near-optimal bounds for phase synchronization
• Bispectrum Inversion with Application to Multireference Alignment
• On the low-rank approach for semidefinite programs arising in synchronization and community detection
• Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models
• Message-passing algorithms for synchronization problems over compact groups
• Entrywise Eigenvector Analysis of Random Matrices with Low Expected Rank
• Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization
• A Riemannian low-rank method for optimization over semidefinite matrices with block-diagonal constraints
• Moment/Sum-of-Squares Hierarchy for Complex Polynomial Optimization
• The non-convex Burer-Monteiro approach works on smooth semidefinite programs
• Approximating the XY model on a random graph with a $q$-state clock model
• On recovery guarantees for angular synchronization
• Sync-Rank: Robust Ranking, Constrained Ranking and Rank Aggregation via Eigenvector and Semidefinite Programming Synchronization
• Message Passing Least Squares Framework and its Application to Rotation Synchronization
• On Semidefinite Relaxations for Matrix-Weighted State-Estimation Problems in Robotics
• Robust Group Synchronization via Cycle-Edge Message Passing
• The Noise-Sensitivity Phase Transition in Spectral Group Synchronization Over Compact Groups
• Optimal Structured Principal Subspace Estimation: Metric Entropy and Minimax Rates
• New semidefinite relaxations for a class of complex quadratic programming problems
• A Geometric View of SDP Exactness in QCQPs and its Applications
• Multi-Frequency Joint Community Detection and Phase Synchronization
• Critical properties of disordered XY model on sparse random graphs
• Tightness of the semidefinite relaxation for orthogonal trace-sum maximization
• On the Landscape of Synchronization Networks: A Perspective from Nonconvex Optimization
• Asymptotic mutual information in quadratic estimation problems over compact groups
• The planted XY model: thermodynamics and inference
• Denoising modulo samples: k-NN regression and tightness of SDP relaxation
• Eigen selection in spectral clustering: a theory guided practice
• On The Geometric Analysis of A Quartic-quadratic Optimization Problem under A Spherical Constraint
• Tightness and Equivalence of Semidefinite Relaxations for MIMO Detection
• Advances in Inference and Representation for Simultaneous Localization and Mapping
• On the Estimation Performance and Convergence Rate of the Generalized Power Method for Phase Synchronization
• Tightness of a new and enhanced semidefinite relaxation for MIMO detection
• Achieving the Bayes Error Rate in Synchronization and Block Models by SDP, Robustly
• Generalized Orthogonal Procrustes Problem under Arbitrary Adversaries
• Lecture notes on non-convex algorithms for low-rank matrix recovery
• Smoothed analysis of the low-rank approach for smooth semidefinite programs
• Nonconvex landscapes for ${\mathbf{Z}}_2$ synchronization and graph clustering are benign near exact recovery thresholds
• Multi-Frequency Phase Synchronization
• FAST-Sync: Fast Group Synchronization for any Matrix Lie Group
• CPL-SLAM: Efficient and Certifiably Correct Planar Graph-Based SLAM Using the Complex Number Representation
• Efficient ${\mathbb{Z}}_2$ synchronization on ${\mathbb{Z}}^d$ under symmetry-preserving side information
• Unbiasing Procedures for Scale-invariant Multi-reference Alignment
• Convergence Analysis of Nonconvex ADMM for Rigid Registration
• An Enhanced SDR based Global Algorithm for Nonconvex Complex Quadratic Programs with Signal Processing Applications