I will present and analyze nonconvex low-rank Burer-Monteiro factored approaches to Max-Cut--like SDPs for orthogonal group synchronization. In this problem, we want to estimate orthogonal group elements from (potentially noisy) pairwise relative measurements. A nonconvex least-squares estimator over the (product) orthogonal group can be lifted and relaxed to an SDP with block-diagonal constraints. However, this lifting (approximately) squares the number of variables. To reduce the dimension, we then consider a low-rank nonconvex factored formulation, which can be viewed as a partial relaxation of the original group problem. We show that, due to the problem structure, increasing the number of variables by a small constant factor results in a benign landscape in the sense that every second-order critical point yields the SDP solution; furthermore, our analysis shows that the SDP relaxation is tight (i.e., yields a solution to the original group synchronization problem), and therefore so is the nonconvex partial relaxation. Key novelties in our results are applicability to general measurement graphs, reaching the optimal relaxation dimension, and extensions to clustering problems. Joint work with Nicolas Boumal, published (in part) in https://doi.org/10.1137/23M1584642.

Let $G$ be a compact group and let $f_{ij}$ be bandlimited functions over $G$. We define the non-unique games (NUG) problem as finding a set of group elements $g_1, ..., g_n$ of $G$ that minimize $\sum_{i,j=1}^n f_{ij}(g_i g_j^{-1})$ . We introduce a convex relaxation of the NUG problem to a semidefinite program (SDP) by taking the Fourier transform of $f_{ij}$ over $G$. The NUG framework can be seen as a generalization of the little Grothendieck problem over the orthogonal group and the unique games problem and includes many practically relevant problems, such as the maximum likelihood estimator to registering bandlimited functions over the unit sphere in d-dimensions and orientation estimation of noisy cryo-electron microscopy (cryo-EM) projection images. We implement an SDP solver for the NUG cryo-EM problem using the alternating direction method of multipliers (ADMM). Numerical study with synthetic datasets indicate that while our ADMM solver is slower than existing methods, it can estimate the rotations more accurately, especially at low signal-to-noise ratio (SNR). If time permits we will also discuss generalization to orbit estimation in the case of non-trivial point group symmetry. Joint work with Afonso Bandeira, Yutong Chen, Roy Lederman, and Ruiyi Yang.

Constructing a hexahedral mesh of a domain is an essential prerequisite in many techniques for simulating physical systems, but automatic hexahedral meshing remains a challenge. A promising approach is to compute a frame field as a proxy for the overall geometry of the mesh. While this decouples geometric optimization from the combinatorics of the meshing problem, frame field optimization is still challenging due to the presence of singularities, i.e., topological defects. I will outline our work on alleviating these “topological barriers” using SDP-based projection onto spaces of symmetric frames. Along the way, we will explore the geometry of frame fields and their singularities. Time permitting, I will discuss our recent work on lifting and current relaxation of frame field optimization and offer some speculation on global SDP relaxation of field optimization problems.