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.