Near-optimal bounds for phase synchronization

DOI10.1137/17M1122025zbMATH Open1396.90068OpenAlexW2598300585WikidataQ130044978 ScholiaQ130044978MaRDI QIDQ4637501FDOQ4637501

Authors: Yiqiao Zhong, Nicolas Boumal 

Publication date: 24 April 2018

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

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 }+sigmaW$, 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 $ildemathcalO(n^{1/2})$, yet, existing analyses only confirm this observation for $sigma$ up to $mathcalO(n^{1/4})$. In this paper, we bridge the gap, by proving SDP is tight for $sigma=mathcalO(sqrtn/logn)$, and GPM converges to the global optimum under the same regime. Moreover, we establish a linear convergence rate for GPM, and derive a tighter $el{l}_{i}nfty$ 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 $el{l}_{i}nfty$ perturbation bound for leading eigenvectors. Our result also confirms intuitions that use techniques from statistical mechanics.

Full work available at URL: https://arxiv.org/abs/1703.06605

Recommendations

• On the estimation performance and convergence rate of the generalized power method for phase synchronization
• Nonconvex phase synchronization
• Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
• Angular synchronization by eigenvectors and semidefinite programming
• Phase transitions in semidefinite relaxations

zbMATH Keywords

nonconvex optimizationmaximum likelihood estimatorquadratically constrained quadratic programsemidefinite programming relaxationangular synchronizationprojected power methodeigenvector perturbation bound

Mathematics Subject Classification ID

Optimality conditions and duality in mathematical programming (90C46) Nonconvex programming, global optimization (90C26) Nonlinear programming (90C30)

Cites Work

• A useful variant of the Davis-Kahan theorem for statisticians
• Angular synchronization by eigenvectors and semidefinite programming
• Asymptotics of sample eigenstructure for a large dimensional spiked covariance model
• Complex Quadratic Optimization and Semidefinite Programming
• Computational complexity versus statistical performance on sparse recovery problems
• Conditional gradient algorithms for rank-one matrix approximations with a sparsity constraint
• Eigenvector synchronization, graph rigidity and the molecule problem
• Exact and stable recovery of rotations for robust synchronization
• Fundamental limits of symmetric low-rank matrix estimation
• Generalized power method for sparse principal component analysis
• Non-asymptotic theory of random matrices: extreme singular values
• Nonconvex phase synchronization
• On Intrinsic Cramér-Rao Bounds for Riemannian Submanifolds and Quotient Manifolds
• On consistency and sparsity for principal components analysis in high dimensions
• Optimality and sub-optimality of PCA. I: Spiked random matrix models
• Phase transitions in semidefinite relaxations
• Random Laplacian matrices and convex relaxations
• Robust regression using iteratively reweighted least-squares
• Spectral clustering and the high-dimensional stochastic blockmodel
• Synchronization over Cartan motion groups via contraction
• The Rotation of Eigenvectors by a Perturbation. III
• The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices
• The largest eigenvalues of finite rank deformation of large Wigner matrices: Convergence and nonuniversality of the fluctuations
• The projected power method: an efficient algorithm for joint alignment from pairwise differences
• Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
• Viewing direction estimation in cryo-EM using synchronization

Cited In (42)

• Mathematical foundations of machine learning. Abstracts from the workshop held March 21--27, 2021 (hybrid meeting)
• Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval
• Quadratic optimization with orthogonality constraint: explicit Łojasiewicz exponent and linear convergence of retraction-based line-search and stochastic variance-reduced gradient methods
• On recovery guarantees for angular synchronization
• Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution
• Orthogonal Trace-Sum Maximization: Tightness of the Semidefinite Relaxation and Guarantee of Locally Optimal Solutions
• Noisy matrix completion: understanding statistical guarantees for convex relaxation via nonconvex optimization
• On the tightness of semidefinite relaxations for rotation estimation
• Entrywise eigenvector analysis of random matrices with low expected rank
• A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization
• Denoising modulo samples: \(k\)-NN regression and tightness of SDP relaxation
• Cramer-Rao bounds for synchronization of rotations
• Optimal Phase Response Functions for Fast Pulse-Coupled Synchronization in Wireless Sensor Networks
• Non-convex exact community recovery in stochastic block model
• Near-optimal bounds for generalized orthogonal Procrustes problem via generalized power method
• Power spectrum unbiasing for dilation-invariant multi-reference alignment
• Entrywise limit theorems for eigenvectors of signal-plus-noise matrix models with weak signals
• Improved performance guarantees for orthogonal group synchronization via generalized power method
• An extension of the angular synchronization problem to the heterogeneous setting
• Strong consistency, graph Laplacians, and the stochastic block model
• Robust high-dimensional factor models with applications to statistical machine learning
• The lower bound of the network connectivity guaranteeing in-phase synchronization
• Near-optimal performance bounds for orthogonal and permutation group synchronization via spectral methods
• The noise-sensitivity phase transition in spectral group synchronization over compact groups
• Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees
• Nonconvex phase synchronization
• Spectral method and regularized MLE are both optimal for top-\(K\) ranking
• Nonconvex Low-Rank Tensor Completion from Noisy Data
• Angular synchronization by eigenvectors and semidefinite programming
• Iterative Collaborative Filtering for Sparse Matrix Estimation
• Singular vector distribution of sample covariance matrices
• Exact minimax optimality of spectral methods in phase synchronization and orthogonal group synchronization
• Optimal orthogonal group synchronization and rotation group synchronization
• Solving orthogonal group synchronization via convex and low-rank optimization: tightness and landscape analysis
• Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution Under Random Designs
• A unified approach to synchronization problems over subgroups of the orthogonal group
• On the landscape of synchronization networks: a perspective from nonconvex optimization
• Singular vector and singular subspace distribution for the matrix denoising model
• An \({\ell_p}\) theory of PCA and spectral clustering
• Iterative algorithm for discrete structure recovery
• On the estimation performance and convergence rate of the generalized power method for phase synchronization
• Tightness of the maximum likelihood semidefinite relaxation for angular synchronization

This page was built for publication: Near-optimal bounds for phase synchronization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4637501)