Tightness of the semidefinite relaxation for orthogonal trace-sum maximization

2019/11/20 by Zhang, Teng
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1911.08700

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.

Related

• Orthogonal Trace-Sum Maximization: Tightness of the Semidefinite Relaxation and Guarantee of Locally Optimal Solutions
• Orthogonal Trace-Sum Maximization: Applications, Local Algorithms, and Global Optimality
• On the Tightness of Semidefinite Relaxations for Rotation Estimation
• Stable rank one matrix completion is solved by two rounds of semidefinite programming relaxation
• The Constant Trace Property in Noncommutative Optimization