Session II.2 - Continuous Optimization
Poster
The rank-relaxed optimization landscape for orthogonal group synchronization on a general graph
Andrew McRae
EPFL, Switzerland - This email address is being protected from spambots. You need JavaScript enabled to view it.
To overcome nonconvexity in quadratically constrained quadratic programs (QCQPs), it is common to relax. Typical SDP relaxations square the dimension of the problem. Burer-Monteiro relaxations give more control over the dimension increase, but general guarantees typically still require a superlinear increase in dimension. Yet, for some problems, when the data is sufficiently structured, it is observed that merely doubling or tripling the dimension is sufficient to dissolve all bad local minima. We show this formally for special settings in synchronization of rotations, with connections to simultaneous localization and mapping (SLAM) in robotics and to synchronizing oscillators in the Kuramoto model.
Specifically, we consider the estimation of $r \times r$ orthogonal matrices $Z_1, \dots, Z_n$ from relative measurements of the form $R_{ij} \approx Z_i Z_j^T$ for $(i,j)$ corresponding to the edges of a connected graph $G$. The least-squares estimator can be expressed as a QCQP $\max_{Y \in \mathbf{R}^{nr \times r}}~\langle C, Y Y^T \rangle$ subject to $Y_i Y_i^T = I_r$ for each $r$-row block of $Y$. For $p \geq r$, the rank-$p$ relaxation of this problem allows $Y \in \mathbf{R}^{nr \times p}$, which makes the above problem an optimization program over a product of $n$ Stiefel manifolds. We show that, in the noiseless case, the rank-$p$ relaxation has no spurious local minima and yields an exact solution to the original rank-$r$ problem whenever $p \geq r+2$. This is optimal for general graphs; the best prior results require $2p \geq 3(r + 1)$. Furthermore, we prove that the absence of spurious local minima is robust to measurement error, where the amount of error tolerated depends on the relaxation rank $p$ and the spectral properties of $G$.
Joint work with Nicolas Boumal (EPFL, Switzerland).