ORTHOGONAL TRACE-SUM MAXIMIZATION: TIGHTNESS OF THE SEMIDEFINITE RELAXATION AND GUARANTEE OF LOCALLY OPTIMAL SOLUTIONS

This paper studies an optimization problem on the sum of traces of matrix quadratic forms in m semiorthogonal matrices, which can be considered as a generalization of the synchronization of rotations. While the problem is nonconvex, this paper shows that its semidefinite programming relaxation solves the original nonconvex problems exactly with high probability under an additive noise model with small noise in the order of O(m(1/4)). In addition, it shows that, with high probability, the sufficient condition for global optimality considered in Won, Zhou, and Lange [SIAM J. Matrix Anal. Appl., 2 (2021), pp. 859-882] is also necessary under a similar small noise condition. These results can be considered as a generalization of existing results on phase synchronization.

Automated summary

This paper studies an optimization problem on the sum of traces of matrix quadratic forms in m semiorthogonal matrices, which can be considered as a generalization of the synchronization of rotations. The paper shows that its semidefinite programming relaxation solves the original nonconvex problems exactly with high probability under an additive noise model with small noise in the order of O(m(1/4)). In addition, it shows that the sufficient condition for global optimality considered in a previous paper is also necessary under a similar small noise condition.