Near-Optimal Bounds for Phase Synchronization

DOI10.1137/17M1122025zbMath1396.90068arXiv1703.06605OpenAlexW2598300585MaRDI QIDQ4637501

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

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

Related Items

On the tightness of semidefinite relaxations for rotation estimation, Mathematical foundations of machine learning. Abstracts from the workshop held March 21--27, 2021 (hybrid meeting), Iterative algorithm for discrete structure recovery, Iterative Collaborative Filtering for Sparse Matrix Estimation, An extension of the angular synchronization problem to the heterogeneous setting, Near-optimal performance bounds for orthogonal and permutation group synchronization via spectral methods, Singular vector and singular subspace distribution for the matrix denoising model, Nonconvex Low-Rank Tensor Completion from Noisy Data, Improved Performance Guarantees for Orthogonal Group Synchronization via Generalized Power Method, On recovery guarantees for angular synchronization, Solving orthogonal group synchronization via convex and low-rank optimization: tightness and landscape analysis, Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution, 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, Unnamed Item, Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval, Entrywise eigenvector analysis of random matrices with low expected rank, A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization, The noise-sensitivity phase transition in spectral group synchronization over compact groups, 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, On the Estimation Performance and Convergence Rate of the Generalized Power Method for Phase Synchronization, Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization, Singular vector distribution of sample covariance matrices, Robust high-dimensional factor models with applications to statistical machine learning, Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees, Spectral method and regularized MLE are both optimal for top-\(K\) ranking, On the Landscape of Synchronization Networks: A Perspective from Nonconvex Optimization, Quadratic optimization with orthogonality constraint: explicit Łojasiewicz exponent and linear convergence of retraction-based line-search and stochastic variance-reduced gradient methods, Non-convex exact community recovery in stochastic block model, An \({\ell_p}\) theory of PCA and spectral clustering, Orthogonal Trace-Sum Maximization: Tightness of the Semidefinite Relaxation and Guarantee of Locally Optimal Solutions

Cites Work

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