Near-optimal bounds for phase synchronization

DOI10.1137/17M1122025zbMATH Open1396.90068arXiv1703.06605OpenAlexW2598300585WikidataQ130044978 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}^{*}+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

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

Cited In (40)

• Mathematical foundations of machine learning. Abstracts from the workshop held March 21--27, 2021 (hybrid meeting)
• Improved Performance Guarantees for Orthogonal Group Synchronization via Generalized Power Method
• Title not available (Why is that?)
• 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
• 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
• 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
• An extension of the angular synchronization problem to the heterogeneous setting
• Robust high-dimensional factor models with applications to statistical machine learning
• The lower bound of the network connectivity guaranteeing in-phase synchronization
• On the Landscape of Synchronization Networks: A Perspective from Nonconvex Optimization
• 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
• On the Estimation Performance and Convergence Rate of the Generalized Power Method for Phase Synchronization
• 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
• Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via 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

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)