Jacobi-type algorithms for homogeneous polynomial optimization on Stiefel manifolds with applications to tensor approximations

Sheng, Zhou; Li, Jianze; Ni, Qin

doi:10.1090/mcom/3834

Jacobi-type algorithms for homogeneous polynomial optimization on Stiefel manifolds with applications to tensor approximations
HTML articles powered by AMS MathViewer

by Zhou Sheng, Jianze Li and Qin Ni HTML | PDF

Math. Comp. 92 (2023), 2217-2245 Request permission

Abstract:

This paper mainly studies the gradient-based Jacobi-type algorithms to maximize two classes of homogeneous polynomials with orthogonality constraints, and establish their convergence properties. For the first class of homogeneous polynomials subject to a constraint on a Stiefel manifold, we reformulate it as an optimization problem on a unitary group, which makes it possible to apply the gradient-based Jacobi-type (Jacobi-G) algorithm. Then, if the subproblem can always be represented as a quadratic form, we establish the global convergence of Jacobi-G under any one of three conditions. The convergence result for the first condition is an easy extension of the result by Usevich, Li, and Comon [SIAM J. Optim. 30 (2020), pp. 2998–3028], while other two conditions are new ones. This algorithm and the convergence properties apply to the well-known joint approximate symmetric tensor diagonalization. For the second class of homogeneous polynomials subject to constraints on the product of Stiefel manifolds, we reformulate it as an optimization problem on the product of unitary groups, and then develop a new gradient-based multiblock Jacobi-type (Jacobi-MG) algorithm to solve it. We establish the global convergence of Jacobi-MG under any one of the above three conditions, if the subproblem can always be represented as a quadratic form. This algorithm and the convergence properties are suitable to the well-known joint approximate tensor diagonalization. As the proximal variants of Jacobi-G and Jacobi-MG, we also propose the Jacobi-GP and Jacobi-MGP algorithms, and establish their global convergence without any further condition. Some numerical results are provided indicating the efficiency of the proposed algorithms.

References

Traian E. Abrudan, Jan Eriksson, and Visa Koivunen, Steepest descent algorithms for optimization under unitary matrix constraint, IEEE Trans. Signal Process. 56 (2008), no. 3, 1134–1147. MR 2451154, DOI 10.1109/TSP.2007.908999
P.-A. Absil, C. G. Baker, and K. A. Gallivan, Trust-region methods on Riemannian manifolds, Found. Comput. Math. 7 (2007), no. 3, 303–330. MR 2335248, DOI 10.1007/s10208-005-0179-9
P.-A. Absil, R. Mahony, and B. Andrews, Convergence of the iterates of descent methods for analytic cost functions, SIAM J. Optim. 16 (2005), no. 2, 531–547. MR 2197994, DOI 10.1137/040605266
P.-A. Absil, R. Mahony, and R. Sepulchre, Optimization algorithms on matrix manifolds, Princeton University Press, Princeton, NJ, 2008. With a foreword by Paul Van Dooren. MR 2364186, DOI 10.1515/9781400830244
B. W. Bader, T. G. Kolda, et al., Matlab tensor toolbox version 2.6, February 2015, http://www.sandia.gov/~tgkolda/TensorToolbox/.
Nicolas Boumal, An introduction to optimization on smooth manifolds, Cambridge University Press, Cambridge, 2023. MR 4533407, DOI 10.1017/9781009166164
N. Boumal, B. Mishra, P.-A. Absil, and R. Sepulchre, Manopt, a Matlab toolbox for optimization on manifolds, J. Mach. Learn. Res. 15 (2014), 1455–1459.
D. H. Brandwood, A complex gradient operator and its application in adaptive array theory, Proc. IEE-H 130 (1983), no. 1, 11–16. MR 698589, DOI 10.1049/ip-h-1.1983.0004
J. F. Cardoso and A. Souloumiac, Blind beamforming for non-Gaussian signals, IEE Proc. F Radar Signal Process. 6 (1993), no. 140, 362–370.
Jie Chen and Yousef Saad, On the tensor SVD and the optimal low rank orthogonal approximation of tensors, SIAM J. Matrix Anal. Appl. 30 (2008/09), no. 4, 1709–1734. MR 2486861, DOI 10.1137/070711621
P. Comon, Independent component analysis, a new concept?, Signal Process. 36 (1994), no. 3, 287–314.
P. Comon and C. Jutten (eds.), Handbook of Blind Source Separation, Academic Press, Oxford, 2010.
L. De Lathauwer, B. De Moor, and J. Vandewalle, Blind source separation by simultaneous third-order tensor diagonalization, 1996 8th European Signal Processing Conference (EUSIPCO 1996), 1996, pp. 1–4.
L. De Lathauwer, B. De Moor, and J. Vandewalle, Independent component analysis and (simultaneous) third-order tensor diagonalization, IEEE Trans. Signal Process. 49 (2001), no. 10, 2262–2271.
Hans De Sterck and Alexander J. M. Howse, Nonlinearly preconditioned L-BFGS as an acceleration mechanism for alternating least squares with application to tensor decomposition, Numer. Linear Algebra Appl. 25 (2018), no. 6, e2202, 30. MR 3890982, DOI 10.1002/nla.2202
Alan Edelman, Tomás A. Arias, and Steven T. Smith, The geometry of algorithms with orthogonality constraints, SIAM J. Matrix Anal. Appl. 20 (1999), no. 2, 303–353. MR 1646856, DOI 10.1137/S0895479895290954
Lars Eldén and Haesun Park, A Procrustes problem on the Stiefel manifold, Numer. Math. 82 (1999), no. 4, 599–619. MR 1701831, DOI 10.1007/s002110050432
Lars Eldén and Berkant Savas, A Newton-Grassmann method for computing the best multilinear rank-$(r_1,r_2,r_3)$ approximation of a tensor, SIAM J. Matrix Anal. Appl. 31 (2009), no. 2, 248–271. MR 2496418, DOI 10.1137/070688316
Walter Gander, Gene H. Golub, and Urs von Matt, A constrained eigenvalue problem, Linear Algebra Appl. 114/115 (1989), 815–839. MR 986908, DOI 10.1016/0024-3795(89)90494-1
Bin Gao, Xin Liu, Xiaojun Chen, and Ya-xiang Yuan, A new first-order algorithmic framework for optimization problems with orthogonality constraints, SIAM J. Optim. 28 (2018), no. 1, 302–332. MR 3757115, DOI 10.1137/16M1098759
Gene H. Golub and Charles F. Van Loan, Matrix computations, 3rd ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1996. MR 1417720
Simai He, Zhening Li, and Shuzhong Zhang, Approximation algorithms for homogeneous polynomial optimization with quadratic constraints, Math. Program. 125 (2010), no. 2, Ser. B, 353–383. MR 2733568, DOI 10.1007/s10107-010-0409-z
Shenglong Hu, An inexact augmented Lagrangian method for computing strongly orthogonal decompositions of tensors, Comput. Optim. Appl. 75 (2020), no. 3, 701–737. MR 4078366, DOI 10.1007/s10589-019-00128-3
S. Hu and K. Ye, Linear convergence of an alternating polar decomposition method for low rank orthogonal tensor approximations, Math. Program., Series A (2022), DOI 10.1007/s10107-022-01867-8, https://link.springer.com/article/10.1007/s10107-022-01867-8.
Mariya Ishteva, P.-A. Absil, and Paul Van Dooren, Jacobi algorithm for the best low multilinear rank approximation of symmetric tensors, SIAM J. Matrix Anal. Appl. 34 (2013), no. 2, 651–672. MR 3062583, DOI 10.1137/11085743X
Mariya Ishteva, P.-A. Absil, Sabine Van Huffel, and Lieven De Lathauwer, Best low multilinear rank approximation of higher-order tensors, based on the Riemannian trust-region scheme, SIAM J. Matrix Anal. Appl. 32 (2011), no. 1, 115–135. MR 2811294, DOI 10.1137/090764827
Bo Jiang and Yu-Hong Dai, A framework of constraint preserving update schemes for optimization on Stiefel manifold, Math. Program. 153 (2015), no. 2, Ser. A, 535–575. MR 3397072, DOI 10.1007/s10107-014-0816-7
Tamara G. Kolda and Brett W. Bader, Tensor decompositions and applications, SIAM Rev. 51 (2009), no. 3, 455–500. MR 2535056, DOI 10.1137/07070111X
Steven G. Krantz, Function theory of several complex variables, AMS Chelsea Publishing, Providence, RI, 2001. Reprint of the 1992 edition. MR 1846625, DOI 10.1090/chel/340
Steven G. Krantz and Harold R. Parks, A primer of real analytic functions, 2nd ed., Birkhäuser Advanced Texts: Basler Lehrbücher. [Birkhäuser Advanced Texts: Basel Textbooks], Birkhäuser Boston, Inc., Boston, MA, 2002. MR 1916029, DOI 10.1007/978-0-8176-8134-0
Rongjie Lai and Stanley Osher, A splitting method for orthogonality constrained problems, J. Sci. Comput. 58 (2014), no. 2, 431–449. MR 3150266, DOI 10.1007/s10915-013-9740-x
Jianze Li, Konstantin Usevich, and Pierre Comon, Globally convergent Jacobi-type algorithms for simultaneous orthogonal symmetric tensor diagonalization, SIAM J. Matrix Anal. Appl. 39 (2018), no. 1, 1–22. MR 3743743, DOI 10.1137/17M1116295
—, On the convergence of Jacobi-type algorithms for independent component analysis, 2020 IEEE 11th Sensor Array and Multichannel Signal Processing Workshop (SAM), IEEE, 2020, pp. 1–5.
Jianze Li, Konstantin Usevich, and Pierre Comon, Jacobi-type algorithm for low rank orthogonal approximation of symmetric tensors and its convergence analysis, Pac. J. Optim. 17 (2021), no. 3, 357–379. MR 4374130
J. Li and S. Zhang, Polar decomposition-based algorithms on the product of Stiefel manifolds with applications in tensor approximation, J. Oper. Res. Soc., (2023), DOI: 10.1007/s40305-023-00462-8.
Z. Li, S. He, and S. Zhang, Approximation methods for polynomial optimization: model, algorithms, and applications, SpringerBriefs in Optimization, Springer, New York, 2012.
Chen Ling, Jiawang Nie, Liqun Qi, and Yinyu Ye, Biquadratic optimization over unit spheres and semidefinite programming relaxations, SIAM J. Optim. 20 (2009), no. 3, 1286–1310. MR 2546345, DOI 10.1137/080729104
S. Łojasiewicz, Ensembles semi-analytiques, IHES Notes (1965), https://perso.univ-rennes1.fr/michel.coste/Lojasiewicz.pdf.
Stanislas Łojasiewicz, Sur la géométrie semi- et sous-analytique, Ann. Inst. Fourier (Grenoble) 43 (1993), no. 5, 1575–1595 (French, with English and French summaries). MR 1275210, DOI 10.5802/aif.1384
Zhi-Quan Luo and Shuzhong Zhang, A semidefinite relaxation scheme for multivariate quartic polynomial optimization with quadratic constraints, SIAM J. Optim. 20 (2010), no. 4, 1716–1736. MR 2600236, DOI 10.1137/090772952
J. H. Manton, Modified steepest descent and Newton algorithms for orthogonally constrained optimisation. Part I. The complex Stiefel manifold, Proceedings of the Sixth International Symposium on Signal Processing and its Applications, vol. 1, 2001, pp. 80–83.
Carla D. Moravitz Martin and Charles F. Van Loan, A Jacobi-type method for computing orthogonal tensor decompositions, SIAM J. Matrix Anal. Appl. 30 (2008), no. 3, 1219–1232. MR 2447449, DOI 10.1137/060655924
Jiawang Nie and Zi Yang, Hermitian tensor decompositions, SIAM J. Matrix Anal. Appl. 41 (2020), no. 3, 1115–1144. MR 4129977, DOI 10.1137/19M1306889
B. Pesquet-Popescu, J. C. Pesquet, and A. P. Petropulu, Joint singular value decomposition-a new tool for separable representation of images, Proceedings of the IEEE International Conference on Image Processing, Thessaloniki, Greece, 2001, pp. 569–572.
Reinhold Schneider and André Uschmajew, Convergence results for projected line-search methods on varieties of low-rank matrices via Łojasiewicz inequality, SIAM J. Optim. 25 (2015), no. 1, 622–646. MR 3323551, DOI 10.1137/140957822
André Uschmajew, A new convergence proof for the higher-order power method and generalizations, Pac. J. Optim. 11 (2015), no. 2, 309–321. MR 3350202
Konstantin Usevich, Jianze Li, and Pierre Comon, Approximate matrix and tensor diagonalization by unitary transformations: convergence of Jacobi-type algorithms, SIAM J. Optim. 30 (2020), no. 4, 2998–3028. MR 4164076, DOI 10.1137/19M125950X
Zaiwen Wen and Wotao Yin, A feasible method for optimization with orthogonality constraints, Math. Program. 142 (2013), no. 1-2, Ser. A, 397–434. MR 3127080, DOI 10.1007/s10107-012-0584-1
Yuning Yang, The epsilon-alternating least squares for orthogonal low-rank tensor approximation and its global convergence, SIAM J. Matrix Anal. Appl. 41 (2020), no. 4, 1797–1825. MR 4176896, DOI 10.1137/19M1303113