Paperlane

no. 6 · Monday 2 November 2026

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

Hongjin Wu

math.OC · 17 pp

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 $\mathbb{R}$ 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.

comments
17 pages
fields
Optimization and Control
pdf ↗ page arXiv:2610.40872 ↗