  This paper studies the problem of maximizing the sum of traces of matrix
quadratic forms on a product of Stiefel manifolds. This orthogonal trace-sum
maximization (OTSM) problem generalizes many interesting problems such as
generalized canonical correlation analysis (CCA), Procrustes analysis, and
cryo-electron microscopy of the Nobel prize fame. For these applications
finding global solutions is highly desirable but it has been unclear how to
find even a stationary point, let alone testing its global optimality. Through
a close inspection of Ky Fan's classical result (1949) on the variational
formulation of the sum of largest eigenvalues of a symmetric matrix, and a
semidefinite programming (SDP) relaxation of the latter, we first provide a
simple method to certify global optimality of a given stationary point of OTSM.
This method only requires testing whether a symmetric matrix is positive
semidefinite. A by-product of this analysis is an unexpected strong duality
between Shapiro-Botha (1988) and Zhang-Singer (2017). After showing that a
popular algorithm for generalized CCA and Procrustes analysis may generate
oscillating iterates, we propose a simple fix that provably guarantees
convergence to a stationary point. The combination of our algorithm and
certificate reveals novel global optima of various instances of OTSM.
