ORTHOGONAL TRACE-SUM MAXIMIZATION: APPLICATIONS, LOCAL ALGORITHMS, AND GLOBAL OPTIMALITY.
ORTHOGONAL TRACE-SUM MAXIMIZATION: APPLICATIONS, LOCAL ALGORITHMS, AND GLOBAL OPTIMALITY.
复制标题
DOI：
10.1137/20m1363388
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Lange K
中科院分区：
文献类型：
--
作者：
Won JH;Zhou H;Lange K
本文研究了Stiefel流形乘积上矩阵二次型的迹和的最大化问题。这个正交迹和最大化(OTSM)问题推广了许多有趣的问题，如广义典型相关分析(CCA)、Procrstes分析和诺贝尔奖的冷冻电子显微镜。对于这些应用来说，寻找全局解是非常可取的，但如何找到一个固定点都不清楚，更不用说测试它的全局最优性了。通过仔细检查Ky Fan的经典结果[Proc.娜塔莉。阿卡德。SCI。美国，35(1949)，pp.652-655]关于对称矩阵的最大特征值之和的变分公式，以及后者的半定规划(SDP)松弛，我们首先提供了证明OTSM的给定驻点的全局最优性的简单方法。这种方法只需要测试对称矩阵是否为半正定。这一分析的一个副产品是夏皮罗和博塔之间出人意料的强烈二元性[SIAM J.Matrix anal]。张和兴[线性代数应用，524(2017)，第159-181页].在证明了一种流行的广义CCA和Prorustes分析算法可以产生振荡迭代之后，我们提出了一个简单的修复方法，可以证明它可以保证收敛到一个固定点。我们的算法和证书的结合揭示了OTSM的各种实例的新颖的全局最优。
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 test its global optimality. Through a close inspection of Ky Fan’s classical result [Proc. Natl. Acad. Sci. USA, 35 (1949), pp. 652–655] 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 and Botha [SIAM J. Matrix Anal. Appl., 9 (1988), pp. 378–383] and Zhang and Singer [Linear Algebra Appl., 524 (2017), pp. 159–181]. 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.