Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
arXiv:1411.3272 · doi:10.1007/s10107-016-1059-6
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 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.
arXiv comment2 figures
References in corpus (14)
- The Convex Geometry of Linear Inverse Problems
- Manopt, a Matlab toolbox for optimization on manifolds
- Latent variable graphical model selection via convex optimization
- Low-rank optimization for semidefinite convex problems
- Sharp nonasymptotic bounds on the norm of random matrices with independent entries
- Cramér-Rao bounds for synchronization of rotations
- Spectral distributions of adjacency and Laplacian matrices of random graphs
- Guaranteed clustering and biclustering via semidefinite programming
- A Riemannian low-rank method for optimization over semidefinite matrices with block-diagonal constraints
- Convex recovery from interferometric measurements
- Grothendieck inequalities for semidefinite programs with rank constraint
- Open problem: Tightness of maximum likelihood semidefinite relaxations
- Sync-Rank: Robust Ranking, Constrained Ranking and Rank Aggregation via Eigenvector and Semidefinite Programming Synchronization
- 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 -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 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 synchronization on 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