Collection Imaging and machine learning
Organizer(s)
Date(s)
03/05/2024
Rank optimality for the Burer-Monteiro factorization
In the last decades, semidefinite programs have emerged as a a powerful way to solve difficult combinatorial optimization problems in polynomial time. Unfortunately, they are difficult to numerically solve in high dimensions. This talk will discuss a classical heuristic used to speed up the solving, namely the Burer-Monteiro formulation. We will review the main correctness guarantees that have been established for this heuristic, and study their optimality.
