Skip to content
DraconiticResearch
Search Sources API
182,549 studies31 sourcesUpdated 27 min ago
PreprintCC BY 4.0arXiv

Simple Cuts, Simple Landscape: Dimension-Free Rank Bounds for Burer-Monteiro Factorizations via Rank-Width

  • Hongjin Wu
Open at sourcePDFDOICite

Abstract

In this work, we study Burer-Monteiro factorizations of semidefinite programs with unit diagonal constraints. For a real symmetric cost matrix whose rank-width over ℝ is at most k, we prove that every non-flat second-order stationary point of the factorized problem is globally optimal whenever the factorization rank is at least 2k, independently of the matrix size.

Related

  1. Robust dimension-free estimation of simple random tensors: optimal guarantees under heavy tails and adversarial contamination
    Roberto I. Oliveira, Zoraida F. Rico, Philip Thompson
    arXivPreprintCC BY 4.0Full textStatisticsarXiv
  2. The Dimension Landscape of Bivariate C2 Splines
    Xinyu Wu, Jiansong Deng
    arXivPreprintarXiv licenceFull textNumerical analysis & scientific computingarXiv
  3. PDE-Based Bounds on Optimal Exponents in Active Simple Hypothesis Testing
    Sushant Vijayan, Himadri Mandal
    arXivPreprintCC BY-NC-SA 4.0Full textStatisticsarXiv
  4. Quantum expanders and dimension-free commutator bounds
    Tuan Tran
    arXivPreprintarXiv licenceFull textAnalysis & PDEsarXiv
  5. Sharp dimension bounds for right-angled hyperbolic polytopes
    Alexander Kolpakov
    arXivPreprintarXiv licenceFull textGeometry & topologyarXiv

Cite

BibTeXRIS
BibTeX
@misc{wu2026simple,
  title = {{Simple Cuts, Simple Landscape: Dimension-Free Rank Bounds for Burer-Monteiro Factorizations via Rank-Width}},
  author = {Hongjin Wu},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.40872},
  eprint = {2610.40872},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.40872},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Simple Cuts, Simple Landscape: Dimension-Free Rank Bounds for Burer-Monteiro Factorizations via Rank-Width
AU  - Hongjin Wu
PY  - 2026
DA  - 2026/10/29
PB  - arXiv
DO  - 10.48550/arxiv.2610.40872
UR  - https://arxiv.org/abs/2610.40872
AB  - In this work, we study Burer-Monteiro factorizations of semidefinite programs with unit diagonal constraints. For a real symmetric cost matrix whose rank-width over ℝ is at most k, we prove that every non-flat second-order stationary point of the factorized problem is globally optimal whenever the factorization rank is at least 2k, independently of the matrix size.
ER  -