Nonconvex phase synchronization

Abstract

We estimate $n$ phases (angles) from noisy pairwise relative phase measurements. The task is modeled as a nonconvex least-squares optimization problem. It was recently shown that this problem can be solved in polynomial time via convex relaxation, under some conditions on the noise. In this paper, under similar but more restrictive conditions, we show that a modified version of the power method converges to the global optimum. This is simpler and (empirically) faster than convex approaches. Empirically, they both succeed in the same regime. Further analysis shows that, in the same noise regime as previously studied, second-order necessary optimality conditions for this quadratically constrained quadratic program are also sufficient, despite nonconvexity.

29 pages, 7 figures, to appear in SIAM Journal of Optimization (2016)

References in corpus (11)

• Generalized power method for sparse principal component analysis
• Global rates of convergence for nonconvex optimization on manifolds
• Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition
• Phase Transitions in Semidefinite Relaxations
• When Are Nonconvex Problems Not Scary?
• On the low-rank approach for semidefinite programs arising in synchronization and community detection
• The non-convex Burer-Monteiro approach works on smooth semidefinite programs
• Estimation and Registration on Graphs
• Sync-Rank: Robust Ranking, Constrained Ranking and Rank Aggregation via Eigenvector and Semidefinite Programming Synchronization
• Non-negative Principal Component Analysis: Message Passing Algorithms and Sharp Asymptotics
• On the Estimation Performance and Convergence Rate of the Generalized Power Method for Phase Synchronization

Cited by in corpus (58)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Global rates of convergence for nonconvex optimization on manifolds
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• A Geometric Analysis of Phase Retrieval
• Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
• 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
• Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization
• A Well-Tempered Landscape for Non-convex Robust Subspace Recovery
• Functional Control of Oscillator Networks
• Reshaped Wirtinger Flow and Incremental Algorithm for Solving Quadratic System of Equations
• From Symmetry to Geometry: Tractable Nonconvex Problems
• Symbol-Level Precoding Through the Lens of Zero Forcing and Vector Perturbation
• McTorch, a manifold optimization library for deep learning
• Robust PCA by Manifold Optimization
• Multi-reference alignment in high dimensions: sample complexity and phase transition
• On recovery guarantees for angular synchronization
• Convergence to Second-Order Stationarity for Constrained Non-Convex Optimization
• The generalized method of moments for multi-reference alignment
• Convolutional Phase Retrieval via Gradient Descent
• The condition number of Riemannian approximation problems
• An accelerated expectation-maximization algorithm for multi-reference alignment
• Solving Complex Quadratic Systems with Full-Rank Random Matrices
• Finding the Sparsest Vectors in a Subspace: Theory, Algorithms, and Applications
• The Noise-Sensitivity Phase Transition in Spectral Group Synchronization Over Compact Groups
• An Alternating Manifold Proximal Gradient Method for Sparse PCA and Sparse CCA
• Exact Minimax Estimation for Phase Synchronization
• Optimal Structured Principal Subspace Estimation: Metric Entropy and Minimax Rates
• Proximal Gradient Method for Nonsmooth Optimization over the Stiefel Manifold
• Robust Multi-object Matching via Iterative Reweighting of the Graph Connection Laplacian
• General Low-rank Matrix Optimization: Geometric Analysis and Sharper Bounds
• Towards the optimal construction of a loss function without spurious local minima for solving quadratic equations
• On the Landscape of Synchronization Networks: A Perspective from Nonconvex Optimization
• A Manifold Proximal Linear Method for Sparse Spectral Clustering with Application to Single-Cell RNA Sequencing Data Analysis
• The Landscape of Matrix Factorization Revisited
• Multi-Frequency Joint Community Detection and Phase Synchronization
• Optimal Non-Convex Exact Recovery in Stochastic Block Model via Projected Power Method
• Tightness of the semidefinite relaxation for orthogonal trace-sum maximization
• On the Estimation Performance and Convergence Rate of the Generalized Power Method for Phase Synchronization
• On The Geometric Analysis of A Quartic-quadratic Optimization Problem under A Spherical Constraint
• Asymptotic mutual information in quadratic estimation problems over compact groups
• VICAN: Very Efficient Calibration Algorithm for Large Camera Networks
• Lecture notes on non-convex algorithms for low-rank matrix recovery
• Generalized Orthogonal Procrustes Problem under Arbitrary Adversaries
• Tightness of a new and enhanced semidefinite relaxation for MIMO detection
• Using Negative Curvature in Solving Nonlinear Programs
• Momentum-inspired Low-Rank Coordinate Descent for Diagonally Constrained SDPs
• Multi-Frequency Phase Synchronization
• Heuristic Quality Coefficients for Interferometric Phase Linking
• Seeded graph matching for the correlated Gaussian Wigner model via the projected power method
• Efficient ${\mathbb{Z}}_2$ synchronization on ${\mathbb{Z}}^d$ under symmetry-preserving side information
• Unbiasing Procedures for Scale-invariant Multi-reference Alignment
• Conditions for Exact Convex Relaxation and No Spurious Local Optima
• Depth Descent Synchronization in $\mathrm{SO}(D)$
• CPL-SLAM: Efficient and Certifiably Correct Planar Graph-Based SLAM Using the Complex Number Representation