Nonconvex landscapes for Z₂ synchronization and graph clustering are benign near exact recovery thresholds

DOI10.1093/IMAIAI/IAAF012MaRDI QIDQ6909016zbMATH OpenFDO

Authors Andrew D. McRae, Pedro Abdalla, Afonso S. Bandeira, Nicolas Boumal

Publication date 30 October 2025

Published in Information and Inference (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1093/IMAIAI/IAAF012

zbMATH Keywords

graph clusteringlow-dimensional relaxationnonconvex landscapessynchronization

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Nonconvex programming, global optimization (90C26) Programming involving graphs or networks (90C35)

Cites work

• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions
• Almost global consensus on the n-sphere
• Angular synchronization by eigenvectors and semidefinite programming
• Benign landscapes of low-dimensional relaxations for orthogonal synchronization on general graphs
• Community detection and stochastic block models: recent developments
• Consistency thresholds for the planted bisection model
• Correlation clustering
• Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs
• Eigenvector synchronization, graph rigidity and the molecule problem
• Exact Recovery in the Stochastic Block Model
• Heuristics for semirandom graph problems
• How robust are reconstruction thresholds for community detection?
• scientific article; zbMATH DE number 194139 (Why is no real title available?)
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• On the landscape of synchronization networks: a perspective from nonconvex optimization
• Phase retrieval from local measurements: improved robustness via eigenvector-based angular synchronization
• Phase transitions in semidefinite relaxations
• Random Laplacian matrices and convex relaxations
• Rotation averaging
• SDP Achieves Exact Minimax Optimality in Phase Synchronization
• Solving orthogonal group synchronization via convex and low-rank optimization: tightness and landscape analysis
• The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
• Tightness of the maximum likelihood semidefinite relaxation for angular synchronization

Cited in

(2)

• Expander graphs are globally synchronizing
• Tightness of SDP and Burer-Monteiro factorization for phase synchronization in a high-noise regime

This page was built for publication: Nonconvex landscapes for \(\mathbf{Z}_2\) synchronization and graph clustering are benign near exact recovery thresholds

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