mlsanityData to 7 Oct 2026

On the low-rank approach for semidefinite programs arising in synchronization and community detection

arXiv 1602.04426 ↗First posted 14 Feb 2016math.OCcited by 17

Not on the map. Why?

Abstract (arXiv)

To address difficult optimization problems, convex relaxations based on semidefinite programming are now common place in many fields. Although solvable in polynomial time, large semidefinite programs tend to be computationally challenging. Over a decade ago, exploiting the fact that in many applications of interest the desired solutions are low rank, Burer and Monteiro proposed a heuristic to solve such semidefinite programs by restricting the search space to low-rank matrices. The accompanying theory does not explain the extent of the empirical success. We focus on Synchronization and Community Detection problems and provide theoretical guarantees shedding light on the remarkable efficiency of this heuristic.

Key facts. Cited by 17 papers in the map (data through 7 Oct 2026). First posted on arXiv 14 Feb 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2019: 1; 2020: 0; 2021: 6; 2022: 4; 2023: 0; 2024: 1; 2025: 3; 2026: 2.

17 papers.

Sort:

By area:

  1. 2022Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimizationcited by 40
  2. 2019On the Global Convergence of Imitation Learning: A Case for Linear Quadratic Regulatorcited by 20
  3. 2021Why Do Local Methods Solve Nonconvex Problems?cited by 8
  4. 2026A solvable high-dimensional model where nonlinear autoencoders learn structure invisible to PCA while test loss misaligns with generalizationcited by 7
  5. 2021Rank-one matrix estimation: analytic time evolution of gradient descent dynamicscited by 5
  6. 2021Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal Algorithmscited by 4
  7. 2021Sharp Global Guarantees for Nonconvex Low-rank Recovery in the Noisy Overparameterized Regimecited by 3
  8. 2021Non-Convex Joint Community Detection and Group Synchronization via Generalized Power Methodcited by 2
  9. 2022Learning with latent group sparsity via heat flow dynamics on networkscited by 2
  10. 2024Robust Second-Order Nonconvex Optimization and Its Application to Low Rank Matrix Sensingcited by 2
  11. 2025Scalable Second-order Riemannian Optimization for K-means Clusteringcited by 2
  12. 2021On Stochastic Variance Reduced Gradient Method for Semidefinite Optimizationcited by 1
5 more
  1. 2025Nonnegative Low-rank Matrix Recovery Can Have Spurious Local Minimacited by 1
  2. 2022A conditional gradient homotopy method with applications to Semidefinite Programmingcited by 0
  3. 2022Exact Recovery of Community Detection in dependent Gaussian Mixture Modelscited by 0
  4. 2025Learning under Latent Group Sparsity via Diffusion on Networkscited by 0
  5. 2026SATORIS-N: Spectral Analysis based Traffic Observation Recovery via Informed Subspaces and Nuclear-norm minimizationcited by 0