Colloquium: "Orthogonal trace-sum maximization: applications, local algorithms, and global optimality"

Abstract: We study 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 test its global optimality. While the problem is nonconvex, 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 solution of a nonconvex algorithm considered in Won, Zhou, and Lange [SIAM J. Matrix Anal. Appl., 2 (2021), pp. 859-882] is also its global solution with high probability under similar conditions. These results can be considered as a generalization of existing results on phase synchronization. This is joint work with Joong-Ho Won (Seoul National University), Teng Zhang (University of Central Florida), and Kenneth Lange (UCLA).

Hosts: Nan Lin

Tea will be available in Cupples I, room 200 at 3:45pm.