Near-optimal bounds for phase synchronization

Abstract

The problem of phase synchronization is to estimate the phases (angles) of a complex unit-modulus vector $z$ from their noisy pairwise relative measurements $C=z{z}^{\ast }+\sigma W$, where $W$ is a complex-valued Gaussian random matrix. The maximum likelihood estimator (MLE) is a solution to a unit-modulus constrained quadratic programming problem, which is nonconvex. Existing works have proposed polynomial-time algorithms such as a semidefinite relaxation (SDP) approach or the generalized power method (GPM) to solve it. Numerical experiments suggest both of these methods succeed with high probability for $\sigma$ up to $\tilde{\mathcal{O}}(n^{1/2})$, yet, existing analyses only confirm this observation for $\sigma$ up to $\mathcal{O}(n^{1/4})$. In this paper, we bridge the gap, by proving SDP is tight for $\sigma =\mathcal{O}(\sqrt{n/\log n})$, and GPM converges to the global optimum under the same regime. Moreover, we establish a linear convergence rate for GPM, and derive a tighter ${\ell }_{\infty }$ bound for the MLE. A novel technique we develop in this paper is to track (theoretically) $n$ closely related sequences of iterates, in addition to the sequence of iterates GPM actually produces. As a by-product, we obtain an ${\ell }_{\infty }$ perturbation bound for leading eigenvectors. Our result also confirms intuitions that use techniques from statistical mechanics.

34 pages, 1 figure

References in corpus (2)

• Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization
• A Certifiably Correct Algorithm for Synchronization over the Special Euclidean Group

Cited by in corpus (39)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• Bispectrum Inversion with Application to Multireference Alignment
• Spectral Method and Regularized MLE Are Both Optimal for Top-$K$ Ranking
• Entrywise Eigenvector Analysis of Random Matrices with Low Expected Rank
• From Symmetry to Geometry: Tractable Nonconvex Problems
• McTorch, a manifold optimization library for deep learning
• Entrywise Estimation of Singular Vectors of Low-Rank Matrices with Heteroskedasticity and Dependence
• On recovery guarantees for angular synchronization
• Singular vector and singular subspace distribution for the matrix denoising model
• Unified ${\ell }_{2\to \infty }$ Eigenspace Perturbation Theory for Symmetric Random Matrices
• Iterative Collaborative Filtering for Sparse Matrix Estimation
• Robust high dimensional factor models with applications to statistical machine learning
• Leave-one-out Approach for Matrix Completion: Primal and Dual Analysis
• Optimal Subspace Estimation Using Overidentifying Vectors via Generalized Method of Moments
• The Noise-Sensitivity Phase Transition in Spectral Group Synchronization Over Compact Groups
• Exact Minimax Estimation for Phase Synchronization
• Detecting Latent Communities in Network Formation Models
• Subspace Estimation from Unbalanced and Incomplete Data Matrices: ${\ell }_{2,\infty }$ Statistical Guarantees
• Optimal tuning-free convex relaxation for noisy matrix completion
• Minimax Estimation of Linear Functions of Eigenvectors in the Face of Small Eigen-Gaps
• Strong Consistency, Graph Laplacians, and the Stochastic Block Model
• The nonsmooth landscape of blind deconvolution
• On the Landscape of Synchronization Networks: A Perspective from Nonconvex Optimization
• Optimal Non-Convex Exact Recovery in Stochastic Block Model via Projected Power Method
• Tightness of the semidefinite relaxation for orthogonal trace-sum maximization
• Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution under Random Designs
• Multi-Frequency Joint Community Detection and Phase Synchronization
• An ${\ell }_p$ theory of PCA and spectral clustering
• Tightness and Equivalence of Semidefinite Relaxations for MIMO Detection
• Asymptotic mutual information in quadratic estimation problems over compact groups
• Implicit Regularization and Entrywise Convergence of Riemannian Optimization for Low Tucker-Rank Tensor Completion
• Generalized Orthogonal Procrustes Problem under Arbitrary Adversaries
• Non-Convex Exact Community Recovery in Stochastic Block Model
• Lecture notes on non-convex algorithms for low-rank matrix recovery
• Robust Max Entrywise Error Bounds for Tensor Estimation from Sparse Observations via Similarity Based Collaborative Filtering
• Momentum-inspired Low-Rank Coordinate Descent for Diagonally Constrained SDPs
• Unbiasing Procedures for Scale-invariant Multi-reference Alignment
• Multi-Frequency Phase Synchronization