Nonconvex Phase Synchronization

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.

• Publication year

  2016

• Venue

  SIAM Journal on Optimization

• Publication date

  2016-01-22

• Fields of study

  Mathematics, Physics, Computer Science, Engineering

• Identifiers
  DOI 10.1137/16M105808XarXiv 1601.06114
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The non-convex Burer-Monteiro approach works on smooth semidefinite programs

  2016cited by this paper
• Non-Convex Phase Retrieval From STFT Measurements

  2016cited by this paper
• A Geometric Analysis of Phase Retrieval

  2016cited by this paper
• On the low-rank approach for semidefinite programs arising in synchronization and community detection

  2016cited by this paper
• On the Statistical Performance and Convergence Rate of the Generalized Power Method for Angular Synchronization

  2016cited by this paper
• On the Statistical Performance of the Generalized Power Method for Angular Synchronization

  2016influential reference
• Escaping From Saddle Points - Online Stochastic Gradient for Tensor Decomposition

  2015cited by this paper
• Sync-Rank: Robust Ranking, Constrained Ranking and Rank Aggregation via Eigenvector and Semidefinite Programming Synchronization

  2015cited by this paper
• Complete dictionary recovery over the sphere

  2015cited by this paper
• A Nonconvex Optimization Framework for Low Rank Matrix Estimation

  2015cited by this paper
• A Riemannian low-rank method for optimization over semidefinite matrices with block-diagonal constraints

  2015cited by this paper
• Phase transitions in semidefinite relaxations

  2015cited by this paper
• Renegar's Condition Number and Compressed Sensing Performance

  2015cited by this paper
• When Are Nonconvex Problems Not Scary?

  2015cited by this paper
• Sync-Rank: Robust Ranking, Constrained Ranking and Rank Aggregation via Eigenvector and SDP Synchronization

  2015cited by this paper
• Cone-Constrained Principal Component Analysis

  2014cited by this paper
• Tightness of the maximum likelihood semidefinite relaxation for angular synchronization

  2014influential reference
• Non-Negative Principal Component Analysis: Message Passing Algorithms and Sharp Asymptotics

  2014cited by this paper
• Designing Unimodular Codes Via Quadratic Optimization

  2013cited by this paper
• Rotation Averaging

  2013cited by this paper
• Phase retrieval from power spectra of masked signals

  2013cited by this paper
• Phase Retrieval Using Alternating Minimization

  2013cited by this paper
• Approximating the little Grothendieck problem over the orthogonal and unitary groups

  2013cited by this paper
• An analytical solution for the complete sensor network attitude estimation problem

  2013cited by this paper
• Manopt, a matlab toolbox for optimization on manifolds

  2013cited by this paper
• Cramér-Rao bounds for synchronization of rotations

  2012cited by this paper
• Complexity bounds for second-order optimality in unconstrained optimization

  2012cited by this paper
• Phase Retrieval with Polarization

  2012cited by this paper
• A Cheeger Inequality for the Graph Connection Laplacian

  2012cited by this paper
• Phase recovery, MaxCut and complex semidefinite programming

  2012cited by this paper
• Exact and Stable Recovery of Rotations for Robust Synchronization

  2012influential reference
• L1 rotation averaging using the Weiszfeld algorithm

  2011cited by this paper
• Three-Dimensional Structure Determination from Common Lines in Cryo-EM by Eigenvectors and Semidefinite Programming

  2011cited by this paper
• Conditional Gradient Algorithmsfor Rank-One Matrix Approximations with a Sparsity Constraint

  2011cited by this paper
• Probabilistic analysis of the semidefinite relaxation detector in digital communications

  2010cited by this paper
• Estimation and Registration on Graphs

  2010cited by this paper
• Optimization algorithms on matrix manifolds

  2009cited by this paper
• Angular Synchronization by Eigenvectors and Semidefinite Programming.

  2009cited by this paper
• Generalized Power Method for Sparse Principal Component Analysis

  2008influential reference
• Robust Rotation and Translation Estimation in Multiview Reconstruction

  2007cited by this paper
• Trust-Region Methods on Riemannian Manifolds

  2007influential reference
• Complex Quadratic Optimization and Semidefinite Programming

  2006cited by this paper
• Distributed Clock Synchronization over Wireless Networks: Algorithms and Analysis

  2006cited by this paper
• What Is the Range of Surface Reconstructions from a Gradient Field?

  2006cited by this paper
• Rank-Two Relaxation Heuristics for MAX-CUT and Other Binary Quadratic Programs

  2002cited by this paper
• Reconstruction of Optical Surfaces from Ray Data

  2001cited by this paper
• Nonlinear optimization: complexity issues

  1991influential reference

• Dual Quaternion SE(3) Synchronization with Recovery Guarantees

  2026cites this paper
• Phase Synchronization Error Calibration in Focused Energy Delivery for Precision Electronic Warfare

  2025influential citation
• Quality Coefficients for Interferometric Phase Linking

  2025cites this paper
• Tightness of SDP and Burer–Monteiro Factorization for Phase Synchronization in a High-Noise Regime

  2025cites this paper
• Functional Multi-Reference Alignment via Deconvolution

  2025cites this paper
• On a spherically lifted spin model at finite temperature

  2025cites this paper
• Bispectrum Unbiasing for Dilation-Invariant Multi-Reference Alignment

  2024cites this paper
• Absence of spurious solutions far from ground truth: A low-rank analysis with high-order losses

  2024cites this paper
• Rotation Averaging: A Primal-Dual Method and Closed-Forms in Cycle Graphs

  2024influential citation
• Dynamic angular synchronization under smoothness constraints

  2024influential citation
• VICAN: Very Efficient Calibration Algorithm for Large Camera Networks

  2024cites this paper
• Well-conditioned Primal-Dual Interior-point Method for Accurate Low-rank Semidefinite Programming

  2024cites this paper
• Asymptotic mutual information in quadratic estimation problems over compact groups

  2024cites this paper
• Random Multi-Type Spanning Forests for Synchronization on Sparse Graphs

  2024influential citation
• Ellipsoidal embeddings of graphs

  2024influential citation
• Cardinality-Constrained Binary Quadratic Optimization via Extreme Point Pursuit, with Application to the Densest K-Subgraph Problem

  2024cites this paper
• Power System State Estimation by Phase Synchronization and Eigenvectors

  2024influential citation
• Orientation estimation of cryo-EM images using projected gradient descent method

  2023cites this paper
• Local Geometry Determines Global Landscape in Low-rank Factorization for Synchronization

  2023influential citation
• Robust Angular Synchronization via Directed Graph Neural Networks

  2023influential citation
• Hybrid TH precoding with subarray connection for multi‐user mmWave MIMO systems

  2023cites this paper
• Adaptive Trust-Region Method on Riemannian Manifold

  2023cites this paper
• Geometric Analysis of Noisy Low-Rank Matrix Recovery in the Exact Parametrized and the Overparametrized Regimes

  2023cites this paper
• SE(3) Synchronization by eigenvectors of dual quaternion matrices

  2023cites this paper
• A graphic structure based branch-and-bound algorithm for complex quadratic optimization and applications to magnitude least-square problem

  2023cites this paper
• Algorithmic Regularization in Tensor Optimization: Towards a Lifted Approach in Matrix Sensing

  2023cites this paper
• Power Spectrum Unbiasing for Dilation-Invariant Multi-reference Alignment

  2023cites this paper
• Projected Tensor Power Method for Hypergraph Community Recovery

  2023influential citation
• Riemannian Trust Region Methods for SC1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\hbox {SC}^1$$\end{document} Mi

  2023cites this paper
• Rotation Group Synchronization via Quotient Manifold

  2023cites this paper
• ReSync: Riemannian Subgradient-based Robust Rotation Synchronization

  2023cites this paper
• Over-parametrization via Lifting for Low-rank Matrix Sensing: Conversion of Spurious Solutions to Strict Saddle Points

  2023cites this paper
• Generative Principal Component Analysis

  2022cites this paper
• Seeded graph matching for the correlated Wigner model via the projected power method

  2022influential citation
• Synthetic Principal Component Design: Fast Covariate Balancing with Synthetic Controls

  2022influential citation
• The sample complexity of sparse multi-reference alignment and single-particle cryo-electron microscopy

  2022cites this paper
• On connections between Amplitude Flow and Error Reduction for phase retrieval and ptychography

  2022cites this paper
• Exact Minimax Optimality of Spectral Methods in Phase Synchronization and Orthogonal Group Synchronization

  2022cites this paper
• Guarantees for Spontaneous Synchronization on Random Geometric Graphs

  2022cites this paper
• Semidefinite Programming versus Burer-Monteiro Factorization for Matrix Sensing

  2022cites this paper
• A Newton-MR algorithm with complexity guarantees for nonconvex smooth unconstrained optimization

  2022cites this paper
• Unrolled Algorithms for Group Synchronization

  2022cites this paper
• Multi-Frequency Joint Community Detection and Phase Synchronization

  2022cites this paper
• Convergence and Recovery Guarantees of the K-Subspaces Method for Subspace Clustering

  2022cites this paper
• Minimax optimal clustering of bipartite graphs with a generalized power method

  2022influential citation
• Rates of estimation for high-dimensional multi-reference alignment

  2022cites this paper
• Seeded Graph Matching for the Correlated Gaussian Wigner Model via the Projected Power Method

  2022cites this paper
• Noisy Low-rank Matrix Optimization: Geometry of Local Minima and Convergence Rate

  2022influential citation
• A Riemannian approach to low-rank tensor learning

  2022cites this paper
• Performance Guarantees for Spectral Initialization in Rotation Averaging and Pose-Graph SLAM

  2022cites this paper
• Adaptive Hybrid Precoding With High Energy Efficiency for Millimeter Wave Communication Systems

  2022influential citation
• General Low-rank Matrix Optimization: Geometric Analysis and Sharper Bounds

  2021influential citation
• Non-Convex Joint Community Detection and Group Synchronization via Generalized Power Method

  2021cites this paper
• Near-Optimal Bounds for Generalized Orthogonal Procrustes Problem via Generalized Power Method

  2021influential citation
• An iterative clustering algorithm for the Contextual Stochastic Block Model with optimality guarantees

  2021cites this paper
• Orthogonal Group Synchronization with Incomplete Measurements: Error Bounds and Linear Convergence of the Generalized Power Method

  2021influential citation
• Symbol-Level Precoding Through the Lens of Zero Forcing and Vector Perturbation

  2021cites this paper
• Orthogonal Trace-Sum Maximization: Tightness of the Semidefinite Relaxation and Guarantee of Locally Optimal Solutions

  2021influential citation
• Optimal orthogonal group synchronization and rotation group synchronization

  2021cites this paper
• Dihedral Multi-Reference Alignment

  2021cites this paper
• Unbiasing Procedures for Scale-invariant Multi-reference Alignment

  2021cites this paper
• SISAL Revisited

  2021cites this paper
• Generalized Orthogonal Procrustes Problem under Arbitrary Adversaries

  2021cites this paper
• Momentum-inspired Low-Rank Coordinate Descent for Diagonally Constrained SDPs

  2021cites this paper
• Optimal Non-Convex Exact Recovery in Stochastic Block Model via Projected Power Method

  2021cites this paper
• Efficient $\mathbb{Z}_2$ synchronization on $\mathbb{Z}^d$ under symmetry-preserving side information

  2021cites this paper
• Lecture notes on non-convex algorithms for low-rank matrix recovery

  2021cites this paper
• Sharp Restricted Isometry Property Bounds for Low-rank Matrix Recovery Problems with Corrupted Measurements

  2021cites this paper
• An accelerated expectation-maximization for multi-reference alignment

  2021cites this paper
• Joint Community Detection and Rotational Synchronization via Semidefinite Programming

  2021cites this paper
• The Generalized Method of Moments for Multi-Reference Alignment

  2021cites this paper
• A joint optimization algorithm for focused energy delivery in precision electronic warfare

  2021cites this paper
• Conditions for Exact Convex Relaxation and No Spurious Local Optima

  2021cites this paper
• An Accelerated Expectation-Maximization Algorithm for Multi-Reference Alignment

  2021cites this paper
• Functional control of oscillator networks

  2021cites this paper
• On the Local Linear Rate of Consensus on the Stiefel Manifold

  2021cites this paper
• SDP Achieves Exact Minimax Optimality in Phase Synchronization

  2021influential citation
• Phase-Only Robust Minimum Dispersion Beamforming

  2020cites this paper
• Finding the Sparsest Vectors in a Subspace: Theory, Algorithms, and Applications

  2020cites this paper
• A Provably Robust Multiple Rotation Averaging Scheme for SO(2)

  2020cites this paper
• Optimal Structured Principal Subspace Estimation: Metric Entropy and Minimax Rates

  2020cites this paper
• The Landscape of Matrix Factorization Revisited

  2020cites this paper
• On Recovery Guarantees for Angular Synchronization

  2020cites this paper
• Solving orthogonal group synchronization via convex and low-rank optimization: tightness and landscape analysis

  2020influential citation
• Robust Multi-object Matching via Iterative Reweighting of the Graph Connection Laplacian

  2020cites this paper
• Revisiting the Landscape of Matrix Factorization

  2020cites this paper
• CPL-SLAM: Efficient and Certifiably Correct Planar Graph-Based SLAM Using the Complex Number Representation

  2020cites this paper
• From Symmetry to Geometry: Tractable Nonconvex Problems

  2020cites this paper
• RIS-Assisted MISO Communication: Optimal Beamformers and Performance Analysis

  2020cites this paper
• A Manifold Proximal Linear Method for Sparse Spectral Clustering with Application to Single-Cell RNA Sequencing Data Analysis

  2020cites this paper
• Multi-reference alignment in high dimensions: sample complexity and phase transition

  2020cites this paper
• Near-Optimal Performance Bounds for Orthogonal and Permutation Group Synchronization via Spectral Methods

  2020cites this paper
• A Unified Approach to Synchronization Problems over Subgroups of the Orthogonal Group

  2020influential citation
• Exact Minimax Estimation for Phase Synchronization

  2020influential citation
• Hybrid Precoding with Adaptive Sub-connected Architecture for mmWave Massive MIMO Systems

  2020cites this paper
• An Alternating Manifold Proximal Gradient Method for Sparse Principal Component Analysis and Sparse Canonical Correlation Analysis

  2020cites this paper
• Improved Performance Guarantees for Orthogonal Group Synchronization via Generalized Power Method

  2020cites this paper
• On the Power of Louvain in the Stochastic Block Model

  2020cites this paper
• Nonconvex Robust Synchronization of Rotations

  2020cites this paper
• An extension of the angular synchronization problem to the heterogeneous setting

  2020cites this paper