Tightness of the semidefinite relaxation for orthogonal trace-sum maximization

Abstract

This paper studies an optimization problem on the sum of traces of matrix quadratic forms on $m$ orthogonal matrices, which can be considered as a generalization of the synchronization of rotations. While the problem is nonconvex, the paper shows that its semidefinite programming relaxation can solve the original nonconvex problems exactly, under an additive noise model with small noise in the order of $O(-m^{1/4})$, where $m$ is the number of orthogonal matrices. This result can be considered as a generalization of existing results on phase synchronization.

References in corpus (8)

• Nonconvex phase synchronization
• Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
• Near-optimal bounds for phase synchronization
• Cramér-Rao bounds for synchronization of rotations
• Message-passing algorithms for synchronization problems over compact groups
• Synchronization over $Z_2$ and community detection in multiplex signed networks with constraints
• Distributed methods for synchronization of orthogonal matrices over graphs
• Orthogonal Trace-Sum Maximization: Applications, Local Algorithms, and Global Optimality

Cited by in corpus (1)

• Generalized Orthogonal Procrustes Problem under Arbitrary Adversaries