Locally unitarily invariantizable NEPv and convergence analysis of SCF
HTML articles powered by AMS MathViewer
- by Ding Lu and Ren-Cang Li;
- Math. Comp. 93 (2024), 2291-2329
- DOI: https://doi.org/10.1090/mcom/3925
- Published electronically: January 9, 2024
- HTML | PDF | Request permission
Abstract:
We consider a class of eigenvector-dependent nonlinear eigenvalue problems (NEPv) without the unitary invariance property. Those NEPv commonly arise as the first-order optimality conditions of a particular type of optimization problems over the Stiefel manifold, and previously, special cases have been studied in the literature. Two necessary conditions, a definiteness condition and a rank-preserving condition, on an eigenbasis matrix of the NEPv that is a global optimizer of the associated optimization problem are revealed, where the definiteness condition has been known for the special cases previously investigated. We show that, locally close to the eigenbasis matrix satisfying both necessary conditions, the NEPv can be reformulated as a unitarily invariant NEPv, the so-called aligned NEPv, through a basis alignment operation — in other words, the NEPv is locally unitarily invariantizable. Numerically, the NEPv is naturally solved by a self-consistent field (SCF)-type iteration. By exploiting the differentiability of the coefficient matrix of the aligned NEPv, we establish a closed-form local convergence rate for the SCF-type iteration and analyze its level-shifted variant. Numerical experiments confirm our theoretical results.References
- 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
- E. Anderson, Z. Bai, C. Bischof, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney, S. Ostrouchov, and D. Sorensen, LAPACK Users’ Guide, SIAM, Philadelphia, 3rd edition, 1999.
- Zhaojun Bai, James Demmel, Jack Dongarra, Axel Ruhe, and Henk van der Vorst (eds.), Templates for the solution of algebraic eigenvalue problems, Software, Environments, and Tools, vol. 11, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2000. A practical guide. MR 1792141, DOI 10.1137/1.9780898719581
- Zhaojun Bai, Ren-Cang Li, and Ding Lu, Sharp estimation of convergence rate for self-consistent field iteration to solve eigenvector-dependent nonlinear eigenvalue problems, SIAM J. Matrix Anal. Appl. 43 (2022), no. 1, 301–327. MR 4386481, DOI 10.1137/20M136606X
- Zhaojun Bai, Ding Lu, and Bart Vandereycken, Robust Rayleigh quotient minimization and nonlinear eigenvalue problems, SIAM J. Sci. Comput. 40 (2018), no. 5, A3495–A3522. MR 3866568, DOI 10.1137/18M1167681
- Weizhu Bao and Qiang Du, Computing the ground state solution of Bose-Einstein condensates by a normalized gradient flow, SIAM J. Sci. Comput. 25 (2004), no. 5, 1674–1697. MR 2087331, DOI 10.1137/S1064827503422956
- Adi Ben-Israel and Thomas N. E. Greville, Generalized inverses, 2nd ed., CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, vol. 15, Springer-Verlag, New York, 2003. Theory and applications. MR 1987382
- I. Borg and J. Lingoes, Multidimensional Similarity Structure Analysis, Springer-Verlag, New York, 1987.
- 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
- Yunfeng Cai, Lei-Hong Zhang, Zhaojun Bai, and Ren-Cang Li, On an eigenvector-dependent nonlinear eigenvalue problem, SIAM J. Matrix Anal. Appl. 39 (2018), no. 3, 1360–1382. MR 3853608, DOI 10.1137/17M115935X
- Eric Cancès, Rachida Chakir, and Yvon Maday, Numerical analysis of nonlinear eigenvalue problems, J. Sci. Comput. 45 (2010), no. 1-3, 90–117. MR 2679792, DOI 10.1007/s10915-010-9358-1
- Éric Cancès, Gaspard Kemlin, and Antoine Levitt, Convergence analysis of direct minimization and self-consistent iterations, SIAM J. Matrix Anal. Appl. 42 (2021), no. 1, 243–274. MR 4223219, DOI 10.1137/20M1332864
- Moody T. Chu and Nickolay T. Trendafilov, The orthogonally constrained regression revisited, J. Comput. Graph. Statist. 10 (2001), no. 4, 746–771. MR 1938978, DOI 10.1198/106186001317243430
- John P. Cunningham and Zoubin Ghahramani, Linear dimensionality reduction: survey, insights, and generalizations, J. Mach. Learn. Res. 16 (2015), 2859–2900. MR 3450527
- Chandler Davis and W. M. Kahan, The rotation of eigenvectors by a perturbation. III, SIAM J. Numer. Anal. 7 (1970), 1–46. MR 264450, DOI 10.1137/0707001
- J. P. Van de Geer, Linear relations among $k$ sets of variables, Psychometrika 49 (1984), 70–94.
- James W. Demmel, Applied numerical linear algebra, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. MR 1463942, DOI 10.1137/1.9781611971446
- 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
- Gene H. Golub and Charles F. Van Loan, Matrix computations, 4th ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 2013. MR 3024913, DOI 10.56021/9781421407944
- J. C. Gower and G. B. Dijksterhuis, Procrustes problems, Oxford Statistical Science Series, vol. 30, Oxford University Press, Oxford, 2004. MR 2051013, DOI 10.1093/acprof:oso/9780198510581.001.0001
- Nicholas J. Higham, Functions of matrices, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2008. Theory and computation. MR 2396439, DOI 10.1137/1.9780898717778
- J. R. Hurley and R. B. Cattell, The Procrustes program: producing direct rotation to test a hypothesized factor structure, Comput. Behav. Sci. 7 (1962), 258–262.
- Elias Jarlebring, Simen Kvaal, and Wim Michiels, An inverse iteration method for eigenvalue problems with eigenvector nonlinearities, SIAM J. Sci. Comput. 36 (2014), no. 4, A1978–A2001. MR 3249374, DOI 10.1137/130910014
- Leonardo Jost, Simon Setzer, and Matthias Hein, Nonlinear eigenproblems in data analysis: balanced graph cuts and the RatioDCA-prox, Extraction of quantifiable information from complex systems, Lect. Notes Comput. Sci. Eng., vol. 102, Springer, Cham, 2014, pp. 263–279. MR 3329341, DOI 10.1007/978-3-319-08159-5_{1}3
- K. Kreutz-Delgado, The Complex Gradient Operator and the CR-Calculus, Technical Report Course Lecture Suppl. ECE275A., Dept. Elect. Comput. Eng., University of California San Diego, San Diego, CA, 2005. Available at arXiv:0906.4835.
- Ren Cang Li, A perturbation bound for the generalized polar decomposition, BIT 33 (1993), no. 2, 304–308. MR 1326021, DOI 10.1007/BF01989752
- Ren Cang Li, New perturbation bounds for the unitary polar factor, SIAM J. Matrix Anal. Appl. 16 (1995), no. 1, 327–332. MR 1311436, DOI 10.1137/S0895479893256359
- Leslie Hogben (ed.), Handbook of linear algebra, 2nd ed., Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL, 2014. MR 3013937
- Wen Li and Weiwei Sun, Perturbation bounds of unitary and subunitary polar factors, SIAM J. Matrix Anal. Appl. 23 (2002), no. 4, 1183–1193. MR 1920940, DOI 10.1137/S0895479801394623
- Xin Liu, Xiao Wang, Zaiwen Wen, and Yaxiang Yuan, On the convergence of the self-consistent field iteration in Kohn-Sham density functional theory, SIAM J. Matrix Anal. Appl. 35 (2014), no. 2, 546–558. MR 3199420, DOI 10.1137/130911032
- Xin-Guo Liu, Xue-Feng Wang, and Wei-Guo Wang, Maximization of matrix trace function of product Stiefel manifolds, SIAM J. Matrix Anal. Appl. 36 (2015), no. 4, 1489–1506. MR 3418225, DOI 10.1137/15M100883X
- R. M. Martin, Electronic Structure: Basic Theory and Practical Methods, Cambridge University Press, 2004.
- Renate Meyer, Nonlinear eigenvector algorithms for local optimization in multivariate data analysis, Linear Algebra Appl. 264 (1997), 225–246. MR 1465868, DOI 10.1016/S0024-3795(96)00635-0
- T. T. Ngo, M. Bellalij, and Y. Saad, The trace ratio optimization problem for dimensionality reduction, SIAM J. Matrix Anal. Appl. 31 (2010), no. 5, 2950–2971. MR 2763712, DOI 10.1137/090776603
- T. T. Ngo, M. Bellalij, and Y. Saad, The trace ratio optimization problem, SIAM Rev. 54 (2012), no. 3, 545–569. Revised reprint of “The trace ratio optimization problem for dimensionality reduction” [MR2763712]. MR 2966725, DOI 10.1137/120864799
- Jorge Nocedal and Stephen J. Wright, Numerical optimization, 2nd ed., Springer Series in Operations Research and Financial Engineering, Springer, New York, 2006. MR 2244940
- V. R. Saunders and I. H. Hillier, A level–shifting method for converging closed shell Hartree–Fock wave functions, Int. J. Quantum Chem. 7 (1973), no. 4, 699–705.
- R. E. Stanton, Intrinsic convergence in closed-shell SCF calculations. A general criterion, J. Chem. Phys. 75 (1981), no. 11, 5416–5422.
- G. W. Stewart and Ji Guang Sun, Matrix perturbation theory, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1990. MR 1061154
- S. Sun, L. Mao, Z. Dong, and L. Wu, Multiview Machine Learning, Springer, 2019.
- A. Szabo and N. S. Ostlund, Modern Quantum Chemistry: Introduction to Advanced Electronic Structure Theory, Courier Corporation, 2012.
- Z. Teng and R.-C. Li, Variations of orthonormal basis matrices of subspaces, Numer. Alg., Contr. Optim. 2023, to appear.
- L. Thøgersen, J. Olsen, D. Yeager, P. Jørgensen, P. Sałek, and T. Helgaker, The trust-region self-consistent field method: Towards a black-box optimization in Hartree–Fock and Kohn–Sham theories, J. Chem. Phys. 121 (2004), no. 1, 16–27.
- Francesco Tudisco and Desmond J. Higham, A nonlinear spectral method for core-periphery detection in networks, SIAM J. Math. Data Sci. 1 (2019), no. 2, 269–292. MR 3949376, DOI 10.1137/18M1183558
- Parikshit Upadhyaya, Elias Jarlebring, and Emanuel H. Rubensson, A density matrix approach to the convergence of the self-consistent field iteration, Numer. Algebra Control Optim. 11 (2021), no. 1, 99–115. MR 4236696, DOI 10.3934/naco.2020018
- L. Wang, L.-H. Zhang, Z. Bai, and R.-C. Li. Orthogonal canonical correlation analysis and applications. Opt. Methods Soft., 35(4):787–807, 2020.
- Li Wang, Lei-Hong Zhang, and Ren-Cang Li, Trace ratio optimization with an application to multi-view learning, Math. Program. 201 (2023), no. 1-2, Ser. A, 97–131. MR 4620225, DOI 10.1007/s10107-022-01900-w
- Chao Yang, Weiguo Gao, and Juan C. Meza, On the convergence of the self-consistent field iteration for a class of nonlinear eigenvalue problems, SIAM J. Matrix Anal. Appl. 30 (2008/09), no. 4, 1773–1788. MR 2486864, DOI 10.1137/080716293
- Chao Yang, Juan C. Meza, and Lin-Wang Wang, A trust region direct constrained minimization algorithm for the Kohn-Sham equation, SIAM J. Sci. Comput. 29 (2007), no. 5, 1854–1875. MR 2350010, DOI 10.1137/060661442
- LeiHong Zhang and RenCang Li, Maximization of the sum of the trace ratio on the Stiefel manifold, I: Theory, Sci. China Math. 57 (2014), no. 12, 2495–2508. MR 3275399, DOI 10.1007/s11425-014-4824-0
- LeiHong Zhang and RenCang Li, Maximization of the sum of the trace ratio on the Stiefel manifold, II: Computation, Sci. China Math. 58 (2015), no. 7, 1549–1566. MR 3353990, DOI 10.1007/s11425-014-4825-z
- Lei-Hong Zhang, Li-Zhi Liao, and Michael K. Ng, Fast algorithms for the generalized Foley-Sammon discriminant analysis, SIAM J. Matrix Anal. Appl. 31 (2009/10), no. 4, 1584–1605. MR 2595539, DOI 10.1137/080720863
- Lei-Hong Zhang, Li-Zhi Liao, and Michael K. Ng, Superlinear convergence of a general algorithm for the generalized Foley-Sammon discriminant analysis, J. Optim. Theory Appl. 157 (2013), no. 3, 853–865. MR 3047034, DOI 10.1007/s10957-011-9832-4
- L.-H. Zhang, L. Wang, Z. Bai, and R.-C. Li. A self-consistent-field iteration for orthogonal canonical correlation analysis. IEEE Trans. Pattern Anal. Mach. Intell., 44(2):890–904, 2022.
- Lei-Hong Zhang, Wei Hong Yang, Chungen Shen, and Jiaqi Ying, An eigenvalue-based method for the unbalanced Procrustes problem, SIAM J. Matrix Anal. Appl. 41 (2020), no. 3, 957–983. MR 4118339, DOI 10.1137/19M1270872
- Zhenyue Zhang and Keqin Du, Successive projection method for solving the unbalanced Procrustes problem, Sci. China Ser. A 49 (2006), no. 7, 971–986. MR 2266198, DOI 10.1007/s11425-006-0971-2
Bibliographic Information
- Ding Lu
- Affiliation: Department of Mathematics, University of Kentucky, Lexington, Kentucky 40506
- MR Author ID: 1123421
- Email: Ding.Lu@uky.edu
- Ren-Cang Li
- Affiliation: Department of Mathematics, University of Texas at Arlington, Arlington, Texas 76019-0408
- MR Author ID: 256016
- ORCID: 0000-0002-4388-3398
- Email: rcli@uta.edu
- Received by editor(s): December 27, 2022
- Received by editor(s) in revised form: October 3, 2023
- Published electronically: January 9, 2024
- Additional Notes: The first author was supported in part by NSF DMS-2110731. The second author was supported in part by NSF DMS-2009689.
- © Copyright 2024 American Mathematical Society
- Journal: Math. Comp. 93 (2024), 2291-2329
- MSC (2020): Primary 65F15, 65H17
- DOI: https://doi.org/10.1090/mcom/3925
- MathSciNet review: 4759376