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.
|
|
| FullText | Links: – Type: pdflink Text: Availability: 1 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 194201084 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Local Geometry Determines Global Landscape in Low-Rank Factorization for Synchronization. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Ling%2C+Shuyang%22">Ling, Shuyang</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> sl3635@nyu.edu</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Foundations+of+Computational+Mathematics%22">Foundations of Computational Mathematics</searchLink>. Jun2026, Vol. 26 Issue 3, p1553-1585. 33p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Laplacian+matrices%22">Laplacian matrices</searchLink><br /><searchLink fieldCode="DE" term="%22Semidefinite+programming%22">Semidefinite programming</searchLink><br /><searchLink fieldCode="DE" term="%22Matrix+decomposition%22">Matrix decomposition</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: 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] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>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.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=194201084 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1007/s10208-025-09707-9 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 33 StartPage: 1553 Subjects: – SubjectFull: Laplacian matrices Type: general – SubjectFull: Semidefinite programming Type: general – SubjectFull: Matrix decomposition Type: general Titles: – TitleFull: Local Geometry Determines Global Landscape in Low-Rank Factorization for Synchronization. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Ling, Shuyang IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 06 Text: Jun2026 Type: published Y: 2026 Identifiers: – Type: issn-print Value: 16153375 Numbering: – Type: volume Value: 26 – Type: issue Value: 3 Titles: – TitleFull: Foundations of Computational Mathematics Type: main |
| ResultId | 1 |
