Local Geometry Determines Global Landscape in Low-Rank Factorization for Synchronization.
Saved in:
| Title: | Local Geometry Determines Global Landscape in Low-Rank Factorization for Synchronization. |
|---|---|
| Authors: | Ling, Shuyang1 (AUTHOR) sl3635@nyu.edu |
| Source: | Foundations of Computational Mathematics. Jun2026, Vol. 26 Issue 3, p1553-1585. 33p. |
| Subjects: | Laplacian matrices, Semidefinite programming, Matrix decomposition |
| Abstract: | The orthogonal group synchronization problem, which focuses on recovering orthogonal group elements from their corrupted pairwise measurements, encompasses examples such as high-dimensional Kuramoto model on general signed networks, Z 2 -synchronization, community detection under stochastic block models, and orthogonal Procrustes problem. The semidefinite relaxation (SDR) has proven its power in solving this problem; however, its expensive computational costs impede its widespread practical applications. We consider the Burer–Monteiro factorization approach to the orthogonal group synchronization, an effective and scalable low-rank factorization to solve large scale SDPs. Despite the significant empirical successes of this factorization approach, it is still a challenging task to understand when the nonconvex optimization landscape is benign, i.e., the optimization landscape possesses only one local minimizer, which is also global. In this work, we demonstrate that if the rank of the factorization exceeds twice the condition number of the "Laplacian" (certificate matrix) at the global minimizer, the optimization landscape is absent of spurious local minima. Our main theorem is purely algebraic and versatile, and it seamlessly applies to all the aforementioned examples: the nonconvex landscape remains benign under almost identical condition that enables the success of the SDR. Additionally, we illustrate that the Burer–Monteiro factorization is robust to "monotone adversaries", mirroring the resilience of the SDR. In other words, introducing "favorable" adversaries into the data will not result in the emergence of new spurious local minimizers. [ABSTRACT FROM AUTHOR] |
| Copyright of Foundations of Computational Mathematics is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
|
Full text is not displayed to guests.
Login for full access.
|
|
| Abstract: | The orthogonal group synchronization problem, which focuses on recovering orthogonal group elements from their corrupted pairwise measurements, encompasses examples such as high-dimensional Kuramoto model on general signed networks, Z 2 -synchronization, community detection under stochastic block models, and orthogonal Procrustes problem. The semidefinite relaxation (SDR) has proven its power in solving this problem; however, its expensive computational costs impede its widespread practical applications. We consider the Burer–Monteiro factorization approach to the orthogonal group synchronization, an effective and scalable low-rank factorization to solve large scale SDPs. Despite the significant empirical successes of this factorization approach, it is still a challenging task to understand when the nonconvex optimization landscape is benign, i.e., the optimization landscape possesses only one local minimizer, which is also global. In this work, we demonstrate that if the rank of the factorization exceeds twice the condition number of the "Laplacian" (certificate matrix) at the global minimizer, the optimization landscape is absent of spurious local minima. Our main theorem is purely algebraic and versatile, and it seamlessly applies to all the aforementioned examples: the nonconvex landscape remains benign under almost identical condition that enables the success of the SDR. Additionally, we illustrate that the Burer–Monteiro factorization is robust to "monotone adversaries", mirroring the resilience of the SDR. In other words, introducing "favorable" adversaries into the data will not result in the emergence of new spurious local minimizers. [ABSTRACT FROM AUTHOR] |
|---|---|
| ISSN: | 16153375 |
| DOI: | 10.1007/s10208-025-09707-9 |
