2018/11/08 by Joong‐Ho Won, Hua Zhou, Won, Joong-Ho +3
Computer Science · Engineering · #Blind Source Separation Techniques #Computation (stat.CO) #FOS: Computer and information sciences #FOS: Mathematics #Face and Expression Recognition #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.1811.03521
openalex publication_date 2018/11/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.