Nearly Optimal Bounds for Orthogonal Trace-Sum Maximization

Orthogonal trace-sum maximization (OTSM) problems arise in a wide range of data processing applications, including canonical correlation analysis and cryogenic electron microscopy. Despite their practical importance, the existing theoretical understanding of these problems remains incomplete. In this paper, we show that the generalized power method (GPM) converges linearly to the global optimal solution with high probability under an additive Gaussian noise model, provided that the noise level satisfies the nearly optimal bound $(O(\sqrt{n/\log n}))$. In addition, we prove that the semidefinite programming (SDP) relaxation of OTSM is tight and admits a unique optimal solution under the same noise regime, improving upon the best known theoretical guarantee of $(O(n^{1/4}))$. Extensive numerical experiments further demonstrate that our theoretical predictions closely match empirical observations.