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)

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

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)

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.

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

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)

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

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)