4 papers
Phase Transition in Convex Relaxations for Graph Alignment
Laurent Massoulié, Sushil Mahavir Varma, Louis Vassaux +1
We study the graph alignment problem for correlated Gaussian Orthogonal Ensemble (GOE) matrices, where the goal is to recover a hidden vertex permutation given two correlated symme…
Graph Alignment via Birkhoff Relaxation
Sushil Mahavir Varma, Irène Waldspurger, Laurent Massoulié
We consider the graph alignment problem, wherein the objective is to find a vertex correspondence between two graphs that maximizes the edge overlap. The graph alignment problem is…
Projected gradient descent accumulates at Bouligand stationary points
Guillaume Olikier, Irène Waldspurger
This paper considers the projected gradient descent (PGD) algorithm for the problem of minimizing a continuously differentiable function on a nonempty closed subset of a Euclidean…
Benign landscape for Burer-Monteiro factorizations of MaxCut-type semidefinite programs
Faniriana Rakoto Endor, Irène Waldspurger
We consider MaxCut-type semidefinite programs (SDP) which admit a low rank solution. To numerically leverage the low rank hypothesis, a standard algorithmic approach is the Burer-M…