广义特征值极小扰动问题的一类黎曼共轭梯度法

doi:10.12286/jssx.j2021-0793

计算数学 ›› 2022, Vol. 44 ›› Issue (4): 508-533.DOI: 10.12286/jssx.j2021-0793

广义特征值极小扰动问题的一类黎曼共轭梯度法

孔令畅¹, 魏科洋¹, 周学林^2,3, 李姣芬⁴

1. 桂林电子科技大学数学与计算科学学院, 桂林 541004;
2. 云南大学数学与统计学院, 昆明 650500;
3. 桂林电子科技大学国际学院, 桂林 541004;
4. 桂林电子科技大学数学与计算科学学院, 广西高校数据分析与计算重点实验室, 广西应用数学中心 (桂林电子科技大学), 广西自动检测技术与仪器重点实验室, 桂林 541004

收稿日期:2021-03-25 出版日期:2022-11-14 发布日期:2022-11-08
通讯作者: 周学林,Email:zhouxuelin0309@163.com.
基金资助:
国家自然科学基金资助项目（12261026，11961012，12201149），广西自然科学基金资助项目（2016GXNSFAA380074，2017GXNSFBA198082），广西科技基地和人才专项（2021AC06001），2022年桂林电子科技大学校级研究生创新项目（2022YCXS142），广西自动检测技术与仪器重点实验室基金（YQ21103，YQ22106）资助.

PDF ( 99 ) 引用

孔令畅, 魏科洋, 周学林, 李姣芬. 广义特征值极小扰动问题的一类黎曼共轭梯度法[J]. 计算数学, 2022, 44(4): 508-533.

Kong Lingchang, Wei Keyang, Zhou Xuelin, Li Jiaofen. A RIEMANNIAN CONJUGATE GRADIENT APPROACH FOR SOLVING THE GENERALIZED EIGENVALUE PROBLEM WITH MINIMAL PERTURBATION[J]. Mathematica Numerica Sinica, 2022, 44(4): 508-533.

A RIEMANNIAN CONJUGATE GRADIENT APPROACH FOR SOLVING THE GENERALIZED EIGENVALUE PROBLEM WITH MINIMAL PERTURBATION

Kong Lingchang¹, Wei Keyang¹, Zhou Xuelin^2,3, Li Jiaofen⁴

1. School of Mathematics and Computing Science, Guilin University of Electronic Technology, Guilin 541004, China;
2. School of Mathematics and Statistics, Yunan University, Kunming 650000, China;
3. College of International Exchange, Guilin University of Electronic Technology, Guilin 541004, China;
4. School of Mathematics and Computing Science, Guangxi Colleges and Universities Key Laboratory of Data Analysis and Computation, Center for Applied Mathematics of Guangxi (GUET), Guangxi Key Laboratory of Automatic Detecting Technology and Instruments, Guilin University of Electronic Technology, Guilin, 541004, China

Received:2021-03-25 Online:2022-11-14 Published:2022-11-08

研究含参数$l$非方矩阵对广义特征值极小扰动问题所导出的一类复乘积流形约束矩阵最小二乘问题.与已有工作不同,本文直接针对复问题模型,结合复乘积流形的几何性质和欧式空间上的改进Fletcher-Reeves共轭梯度法,设计一类适用于问题模型的黎曼非线性共轭梯度求解算法,并给出全局收敛性分析.数值实验和数值比较表明该算法比参数$l=1$的已有算法收敛速度更快,与参数$l=n$的已有算法能得到相同精度的解.与部分其它流形优化相比与已有的黎曼Dai非线性共轭梯度法具有相当的迭代效率,与黎曼二阶算法相比单步迭代成本较低、总体迭代时间较少,与部分非流形优化算法相比在迭代效率上有明显优势.

关键词： 矩阵最小二乘问题, 广义特征值, 黎曼共轭梯度法, 乘积流形

This paper presents an efficient approach for solving a kind of complex product manifold constrained matrix least squares problem, which derived from the $l$ parameterized generalized eigenvalue problem for nonsquare matrix pencils with minimal perturbation. Different from the existing work, the paper directly focuses on the complex problem model, combining the geometric properties of the considered complex product manifold and basing on the modified Fletcher-Reeves nonlinear conjugate gradient method on Euclidean space, a class of Riemannian nonlinear conjugate gradient algorithm is designed for solving the underlying problem, and the global convergence analysis is given. Numerical experiments and numerical comparisons are given to show that the proposed algorithm converges faster than the existing algorithm with parameter $l=1$, and can get the same accuracy as the existing algorithm with parameter $l=n$. Detailed comparisons with some latest methods, including some other gradient-based methods, some Riemannian second-order algorithms, and two non-manifold optimization algorithms are also provided to show the merits of the proposed approach.

Key words: Matrix least-squares problem, Generalized eigenvalue, Riemannian conjugate gradient, Product manifold

MR(2010)主题分类:

15A24

分享此文:

[1] Boutry G, Elad M, Golub G H, Milanfar P. The generalized eigenvalue problem for nonsquare pencils using a minimal perturbation approach[J]. SIAM Journal on Matrix Analysis and Applications, 2005, 27(2):582-601.
[2] Chu D, Golub G H. On a generalized eigenvalue problem for nonsquare pencils[J]. SIAM Journal on Matrix Analysis and Applications, 2006, 28(3):770-787.
[3] Kressner D, Mengi E, Nakíc I, Truhar N. Generalized eigenvalue problems with specified eigenvalues[J]. IMA Journal of Numerical Analysis, 2014, 34(2):480-501.
[4] Lecumberri P, Gómez M, Carlosena A. Generalized eigenvalues of nonsquare pencils with structure[J]. SIAM Journal on Matrix Analysis and Applications, 2008, 30(1):41-55.
[5] Ito S, Murota K. An algorithm for the generalized eigenvalue problem for nonsquare matrix pencils by minimal perturbation approach[J]. SIAM Journal on Matrix Analysis and Applications, 2016, 37(1):409-419.
[6] Sun J. Matrix perturbation analysis[M]. Science Press, 2001.
[7] Li J F, Li W, Vong S W, Luo Q L, Xiao M. A Riemannian optimization approach for solving the generalized eigenvalue problem for nonsquare matrix pencils[J]. Journal of Scientific Computing, 2020, 82(3):1-43.
[8] Absil P A, Mahony R, Sepulchre R. Optimization Algorithms on Matrix Manifolds[M]. Princeton University Press, 2009.
[9] Sato H. Riemannian conjugate gradient method for complex singular value decomposition problem[J]. Proceedings of the IEEE Conference on Decision and Control, 2015, 2015:5849-5854.
[10] Dai Y H. A nonmonotone conjugate gradient algorithm for unconstrained optimization[J]. Journal of System Science and Complexity, 2002, 15:139-145.
[11] Zhang L, Zhou W J, Li D H. Global convergence of a modified Fletcher-Reeves conjugate gradient method with Armijo-type line search[J]. Numerische Mathematik, 2006, 104(4):561-572.
[12] Sato H, Iwai T. A Riemannian optimization approach to the matrix singular value decomposition[J]. SIAM Journal on Optimization, 2013, 23(1):188-212.
[13] Vandereycken B. Low-rank matrix completion by Riemannian optimization[J]. SIAM Journal on Optimization, 2013, 23(2):1214-1236.
[14] Sato H, Iwai T. A new, globally convergent Riemannian conjugate gradient method[J]. Optimization, 2015, 64(4):1011-1031.
[15] Sato H. A Dai-Yuan-type Riemannian conjugate gradient method with the weak Wolfe conditions[J]. Computational optimization and Applications, 2016, 64(1):101-118.
[16] Sato, Hiroyuki. A Dai-Yuan-type Riemannian conjugate gradient method with the weak Wolfe conditions[J]. Computational optimization and applications, 2016, 64(1):101-118.
[17] Zhao Z, Jin X Q, Bai Z J. A geometric nonlinear conjugate gradient method for stochastic inverse eigenvalue problems[J]. SIAM Journal on Numerical Analysis, 2016, 54(4):2015-2035.
[18] Yao T T, Bai Z J, Zhao Z, Ching W K. A Riemannian Fletcher-Reeves conjugate gradient method for doubly stochastic inverse eigenvalue problems[J]. SIAM Journal on Matrix Analysis and Applications, 2016, 37(1):215-234.
[19] Yao T T, Bai Z J, Zhao Z. A Riemannian variant of the Fletcher-Reeves conjugate gradient method for stochastic inverse eigenvalue problems with partial eigendata[J]. Numerical Linear Algebra with Applications, 2019, 26(2):e2221.
[20] Zhu X. A Riemannian conjugate gradient method for optimization on the Stiefel manifold[J]. Computational Optimization and Applications, 2017, 67(1):73-110.
[21] Song G J, Wang X Z, Ng M K. Riemannian conjugate gradient descent method for third-crder tensor completion[J]. arXiv preprint arXiv:2011.11417, 2020.
[22] Jiang Y L, Xu K L. Riemannian modified Polak-Ribière-Polyak conjugate gradient order reduced model by tensor techniques[J]. SIAM Journal on Matrix Analysis and Applications, 2020, 41(2):432-463.
[23] Sakai H, Iiduka H. Hybrid Riemannian conjugate gradient methods with global convergence properties[J]. Computational Optimization and Applications, 2020, 77(3):811-830.
[24] Sato H. Riemannian Optimization and Its Applications[M]. Springer Nature, 2021.
[25] Wen Z, Yin W. A feasible method for optimization with orthogonality constraints[J]. Mathematical Programming, 2013, 142(1-2):397-434.
[26] Hu J, Liu X, Wen Z W, Yuan Y X. A brief introduction to manifold optimization[J]. Journal of the Operations Research Society of China, 2020, 8(2):199-248.
[27] Zhang L, Zhou W, Li D H. A descent modified Polak-Ribière-Polyak conjugate gradient method and its global convergence[J]. IMA Journal of Numerical Analysis, 2006, 26(4):629-640.
[28] Sato H, Iwai T. A new, globally convergent Riemannian conjugate gradient method[J]. Optimization, 2013, 64(4):1011-1031.
[29] Li J F, Li W, Duan X F, Xiao M. Newton's method for the parameterized generalized eigenvalue problem with nonsquare matrix pencils[J]. Advances in Computational Mathematics, 2021, 47(2):1-50.
[30] Boumal N, Mishra B, Absil P A, Sepulchre R. Manopt, a Matlab toolbox for optimization on manifolds[J]. Journal of Machine Learning Research, 2014, 15(1):1455-1459.

[1]	刘冬冬, 陈艳美, 黎稳. 关于正规矩阵对广义特征值新的扰动界限[J]. 计算数学, 2015, 37(2): 113-122.
[2]	陈小山. 关于特征值与广义特征值的Bauer-Fike型相对扰动界[J]. 计算数学, 2008, 30(4): 409-416.
[3]	裘渔洋,张振跃,. 对称约束平衡Procrustes问题的一个简单解法[J]. 计算数学, 2007, 29(3): 322-324.

阅读次数

全文

摘要

广义特征值极小扰动问题的一类黎曼共轭梯度法

A RIEMANNIAN CONJUGATE GRADIENT APPROACH FOR SOLVING THE GENERALIZED EIGENVALUE PROBLEM WITH MINIMAL PERTURBATION

扫码分享