Tightness of the maximum likelihood semidefinite relaxation for angular synchronization

DOI10.1007/s10107-016-1059-6zbMath1365.90188arXiv1411.3272OpenAlexW2161367205MaRDI QIDQ526833

Afonso S. Bandeira, Amit Singer, Nicolas Boumal

Publication date: 15 May 2017

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

maximum likelihood estimationsemidefinite programmingangular synchronizationtightness of convex relaxation

Mathematics Subject Classification ID

Point estimation (62F10) Semidefinite programming (90C22) Nonconvex programming, global optimization (90C26)

Related Items

Mathematical foundations of machine learning. Abstracts from the workshop held March 21--27, 2021 (hybrid meeting), Iterative algorithm for discrete structure recovery, An extension of the angular synchronization problem to the heterogeneous setting, Positive Semi-definite Embedding for Dimensionality Reduction and Out-of-Sample Extensions, Near-optimal performance bounds for orthogonal and permutation group synchronization via spectral methods, Universal inference, Improved Performance Guarantees for Orthogonal Group Synchronization via Generalized Power Method, On recovery guarantees for angular synchronization, Optimal rates of estimation for multi-reference alignment, On connections between amplitude flow and error reduction for phase retrieval and ptychography, Solving orthogonal group synchronization via convex and low-rank optimization: tightness and landscape analysis, Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs, Eigen Selection in Spectral Clustering: A Theory-Guided Practice, Revisiting Spectral Bundle Methods: Primal-Dual (Sub)linear Convergence Rates, A unified approach to synchronization problems over subgroups of the orthogonal group, Unnamed Item, A note on probably certifiably correct algorithms, Entrywise eigenvector analysis of random matrices with low expected rank, Hermitian completely positive matrices, New semidefinite relaxations for a class of complex quadratic programming problems, The noise-sensitivity phase transition in spectral group synchronization over compact groups, Phase transitions in semidefinite relaxations, Near-optimal bounds for generalized orthogonal Procrustes problem via generalized power method, Power spectrum unbiasing for dilation-invariant multi-reference alignment, A graphic structure based branch-and-bound algorithm for complex quadratic optimization and applications to magnitude least-square problem, On the Estimation Performance and Convergence Rate of the Generalized Power Method for Phase Synchronization, Tightness of a New and Enhanced Semidefinite Relaxation for MIMO Detection, Near-Optimal Bounds for Phase Synchronization, Lasserre Hierarchy for Large Scale Polynomial Optimization in Real and Complex Variables, Fundamental limits of symmetric low-rank matrix estimation, Unnamed Item, Random Laplacian matrices and convex relaxations, Argument division based branch-and-bound algorithm for unit-modulus constrained complex quadratic programming, Penalized semidefinite programming for quadratically-constrained quadratic optimization, Optimality and sub-optimality of PCA. I: Spiked random matrix models, On the Landscape of Synchronization Networks: A Perspective from Nonconvex Optimization, Nonconvex Phase Synchronization, On the geometric analysis of a quartic-quadratic optimization problem under a spherical constraint, Robust group synchronization via cycle-edge message passing, Orthogonal Trace-Sum Maximization: Tightness of the Semidefinite Relaxation and Guarantee of Locally Optimal Solutions

Uses Software

• PhaseLift

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Latent variable graphical model selection via convex optimization
• Sharp nonasymptotic bounds on the norm of random matrices with independent entries
• Approximating the little Grothendieck problem over the orthogonal and unitary groups
• Rotation averaging
• Guaranteed clustering and biclustering via semidefinite programming
• Stable optimizationless recovery from phaseless linear measurements
• Disentangling orthogonal matrices
• A class of semidefinite programs with rank-one solutions
• Spectral distributions of adjacency and Laplacian matrices of random graphs
• Angular synchronization by eigenvectors and semidefinite programming
• Rank-reducibility of a symmetric matrix and sampling theory of minimum trace factor analysis
• On approximating complex quadratic optimization problems via semidefinite programming relaxations
• Problems of distance geometry and convex properties of quadratic maps
• Complementarity and nondegeneracy in semidefinite programming
• Random Laplacian matrices and convex relaxations
• Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
• The convex geometry of linear inverse problems
• Exact matrix completion via convex optimization
• On the Rank of Extreme Matrices in Semidefinite Programs and the Multiplicity of Optimal Eigenvalues
• PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex Programming
• Phase Retrieval with Polarization
• Exact Recovery in the Stochastic Block Model
• Multireference alignment using semidefinite programming
• The Design of Approximation Algorithms
• Three-Dimensional Structure Determination from Common Lines in Cryo-EM by Eigenvectors and Semidefinite Programming
• Low-Rank Optimization on the Cone of Positive Semidefinite Matrices
• Grothendieck inequalities for semidefinite programs with rank constraint
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Just relax: convex programming methods for identifying sparse signals in noise
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Semidefinite Programming
• Exact and stable recovery of rotations for robust synchronization
• Cramer-Rao bounds for synchronization of rotations
• Phase retrieval from power spectra of masked signals
• Living on the edge: phase transitions in convex programs with random data
• Exactness of Semidefinite Relaxations for Nonlinear Optimization Problems with Underlying Graph Structure
• Grothendieck’s Theorem, past and present
• A Cheeger Inequality for the Graph Connection Laplacian
• Complex Quadratic Optimization and Semidefinite Programming
• Stable signal recovery from incomplete and inaccurate measurements
• Compressed sensing