复矩阵截断奇异值分解的一类混合算法

数学物理学报 ›› 2022, Vol. 42 ›› Issue (6): 1898-1921.

• 论文 • 上一篇

复矩阵截断奇异值分解的一类混合算法

张玉心¹,侯文婷¹,周学林^2,^1,*(),李姣芬¹

¹ 桂林电子科技大学数学与计算科学学院, 广西应用数学中心(桂林电子科技大学), 广西高校数据分析与计算重点实验室广西桂林 541004
² 云南大学数学与统计学院昆明 650000

收稿日期:2021-06-19 出版日期:2022-12-26 发布日期:2022-12-16
通讯作者: 周学林 E-mail:zhouxuelin0309@163.com
基金资助:
国家自然科学基金(12261026);国家自然科学基金(11961012);国家自然科学基金(12201149);广西科技基地和人才专项(2021AC06001);2018年广西壮族自治区大学生创新训练项目(201810595215);桂林电子科技大学研究生教育创新计划项目(2022YCXS142);广西自动检测技术与仪器重点实验室基金(YQ21103);广西自动检测技术与仪器重点实验室基金(YQ22106)

A Hybrid Algorithm for Solving Truncated Complex Singular Value Decomposition

Yuxin Zhang¹,Wenting Hou¹,Xuelin Zhou^2,^1,*(),Jiaofen Li¹

¹ School of Mathematics and Computational Science, Center for Applied Mathematics of Guangxi(GUET), Guangxi Colleges and Universities Key Laboratory of Data Analysis and Computation, Guilin University of Electronic Technology, Guangxi Guilin 541004
² School of Mathematics and Statistics, Yunan University, Yunan Kunming 650000

Received:2021-06-19 Online:2022-12-26 Published:2022-12-16
Contact: Xuelin Zhou E-mail:zhouxuelin0309@163.com
Supported by:
the National Natural Science Foundation(12261026);the National Natural Science Foundation(11961012);the National Natural Science Foundation(12201149);the Special Fund for Science and Technological Bases and Talents of Guangxi(2021AC06001);the Guangxi College Student Innovation and Entrepreneurship Training Program(201810595215);the GUET Graduate Innovation Project(2022YCXS142);the Guangxi Key Laboratory of Automatic Detecting Technology and Instruments(YQ21103);the Guangxi Key Laboratory of Automatic Detecting Technology and Instruments(YQ22106)

摘要/Abstract

摘要：

截断奇异值分解是一类非常重要的矩阵分解, 其在病态模型问题分析等领域有广泛的应用.该文主要研究复矩阵截断奇异值分解的有效算法, 将问题转化为复Stiefel乘积流形上的黎曼优化问题, 进而设计基于乘积流形的黎曼混合牛顿法求解.为有效求解黎曼牛顿方程, 从降低系统维数和简化计算入手, 通过克罗内克积和复矩阵拉直算子将其转化为易于求解的标准实对称线性方程组.数值实验和数值比较验证该文所提算法针对复矩阵截断奇异值分解问题是高效可行的.

关键词: 复矩阵, 截断奇异值分解, 黎曼牛顿法, 混合算法

Abstract:

This paper develops an efficient approach for solving the truncated complex singular value decomposition, which is widely applied in ill-posed model problems. The original problem can be formulated as an optimization problem on a corresponding complex product Stiefel manifold. A hybrid Riemannian Newton-type algorithm with globally and quadratically convergent is proposed to solve the underlying problem, in which the involved Newton's equation is transformed into a standard symmetric linear system with a dimension reduction. Numerical experiments and detailed comparisons are provided to illustrate the efficiency of the proposed method.

Key words: Complex matrix, Truncated singular value decomposition, Riemannian Newton's method, Hybrid Algorithm

中图分类号:

O151.1

张玉心,侯文婷,周学林,李姣芬. 复矩阵截断奇异值分解的一类混合算法[J]. 数学物理学报, 2022, 42(6): 1898-1921.

Yuxin Zhang,Wenting Hou,Xuelin Zhou,Jiaofen Li. A Hybrid Algorithm for Solving Truncated Complex Singular Value Decomposition[J]. Acta mathematica scientia,Series A, 2022, 42(6): 1898-1921.

图/表 5

表 1

图 1

表 2

表 3

不同算法的数值比较结果"

	CT.(s)	IT.	Grad.	Obj.	CT.(s)	IT.	Grad.	Obj.
	$m=100, n=20, p=5$				$m=200, n=30, p=5$
Hybrid-Newton	0.32	80/3	1.92$\times 10^{-7}$	-116.67	1.21	134/3	1.29$\times 10^{-10}$	-156.31
Existing-RTR	0.38	13	5.38$\times 10^{-7}$	-116.67	0.83	14	5.35$\times 10^{-8}$	-156.31
Existing-RBFGS	3.93	145	9.87$\times 10^{-7}$	-116.67	5.14	194	8.56$\times 10^{-7}$	-156.31
OptStifelGBB	0.06	199	8.87$\times 10^{-7}$	-116.67	0.16	284	2.14$\times 10^{-7}$	-156.31
RCG-Cayley	0.10	182	8.63$\times 10^{-7}$	-116.67	0.28	293	9.15$\times 10^{-7}$	-156.31
	$m=300, n=40, p=5$				$m=400, n=50, p=5$
Hybrid-Newton	2.64	149/5	1.33$\times 10^{-7}$	-189.95	4.80	173/3	4.90$\times 10^{-10}$	-223.22
Existing-RTR	0.99	15	2.62$\times 10^{-8}$	-189.95	1.37	15	5.17$\times 10^{-8}$	-223.22
Existing-RBFGS	6.70	239	9.54$\times 10^{-7}$	-189.95	6.51	216	9.83$\times 10^{-7}$	-223.22
OptStifelGBB	0.37	396	4.04$\times 10^{-7}$	-189.95	0.47	430	9.49$\times 10^{-7}$	-223.22
RCG-Cayley	0.50	362	9.08$\times 10^{-7}$	-189.95	0.64	363	9.98$\times 10^{-7}$	-223.22
	$m=500, n=60, p=5$				$m=600, n=70, p=5$
Hybrid-Newton	5.26	148/2	2.80$\times 10^{-7}$	-245.29	10.95	210/ 4	2.46$\times 10^{-10}$	-272.71
Existing-RTR	1.45	14	3.48$\times 10^{-7}$	-245.29	1.51	15	3.14$\times 10^{-8}$	-272.71
Existing-RBFGS	9.60	304	2.45$\times 10^{-7}$	-245.29	9.49	285	1.30$\times 10^{-7}$	-272.71
OptStifelGBB	0.61	408	3.60$\times 10^{-7}$	-245.29	0.75	423	8.00$\times 10^{-7}$	-272.71
RCG-Cayley	0.84	406	7.70$\times 10^{-7}$	-245.29	1.15	471	8.49$\times 10^{-7}$	-272.71
	$m=700, n=80, p=5$				$m=800, n=100, p=5$
Hybrid-Newton	16.85	159/4	6.93$\times 10^{-10}$	-293.84	21.11	265/3	2.21$\times 10^{-9}$	-316.66
Existing-RTR	2.26	15	2.24$\times 10^{-11}$	-293.84	3.11	15	4.91$\times 10^{-8}$	-316.66
Existing-RBFGS	11.99	275	2.59$\times 10^{-7}$	-293.84	18.02	355	7.76$\times 10^{-7}$	-316.66
OptStifelGBB	0.89	408	8.12$\times 10^{-7}$	-293.84	2.62	587	9.07$\times 10^{-7}$	-316.66
RCG-Cayley	1.32	438	8.16$\times 10^{-7}$	-293.84	5.44	835	8.26$\times 10^{-7}$	-316.66

表 3

图 2

参考文献 22

1	Hansen P C . Truncated singular value decomposition solutions to discrete ill-posed problems with ill-determined numerical rank. SIAM Journal on Scientific and Statistical Computing, 1990, 11 (3): 503- 518 doi: 10.1137/0911028
2	Noschese S , Reichel L . A modified truncated singular value decomposition method for discrete ill-posed problems. Numerical Linear Algebra with Applications, 2014, 21 (6): 813- 822 doi: 10.1002/nla.1938
3	余景景, 刘芳, 焦李成等. 截断奇异值分解的生物发光断层成像重建问题. 西北大学学报(自然科学版), 2009, 39(5): 755-760
	Yu J, Liu F, Jiao L, He X. Research on the reconstruction for bioluminescence tomography using truncated singular value decomposition method. Journal of Northwest University (Natural Science Edition), 2009, 39(5): 755-760
4	Doğu S , Akıncı M N , Çayören M , Akduman İ . Truncated singular value decomposition for through-the-wall microwave imaging application. IET Microwaves, Antennas & Propagation, 2019, 14 (4): 260- 267
5	Francischello R , Geppi M , Flori A , et al. Application of low-rank approximation using truncated singular value decomposition for noise reduction in hyperpolarized ¹³C NMR spectroscopy. NMR in Biomedicine, 2021, 34 (5): e4285
6	Sato H . Riemannian Optimization and Its Applications. Switzerland: Springer Nature, 2021
7	Sato H , Iwai T . A Riemannian optimization approach to the matrix singular value decomposition. SIAM Journal on Optimization, 2013, 23 (1): 188- 212 doi: 10.1137/120872887
8	Sato H. Riemannian conjugate gradient method for complex singular value decomposition problem. 53rd IEEE Conference on Decision and Control, 2015, pages 5849-5854
9	Sato H, Iwai T. A complex singular value decomposition algorithm based on the Riemannian Newton method[C]//52nd IEEE Conference on Decision and Control. Firenze: IEEE, 2013: 2972-2978
10	Aihara K , Sato H . A matrix-free implementation of Riemannian Newton's method on the Stiefel manifold. Optimization Letters, 2017, 11, 1729- 1741 doi: 10.1007/s11590-016-1090-9
11	Xu W W , Li W , Zhu L , Huang X P . The analytic solutions of a class of constrained matrix minimization and maximization problems with applications. SIAM Journal on Optimization, 2019, 29 (2): 1657- 1686 doi: 10.1137/17M1140777
12	Wen Z , Yin W . A feasible method for optimization with orthogonality constraints. Mathematical Programming, 2013, 142 (1/2): 397- 434
13	Absil P A , Mahony R , Sepulchre R . Optimization Algorithms on Matrix Manifolds. Princeton: Princeton University Press, 2008,
14	Hu J , Liu X , Wen Z W , Yuan Y X . A brief introduction to manifold optimization. Journal of the Operations Research Society of China, 2020, 8 (2): 199- 248 doi: 10.1007/s40305-020-00295-9
15	Absil P A, Mahony R, Trumpf J. An extrinsic look at the Riemannian Hessian[C]//International Conference on Geometric Science of Information. Berlin: Springer, 2013: 361-368
16	Henderson H V , Searle S R . The vec-permutation matrix, the vec operator and Kronecker products: A review. Linear and Multilinear Algebra, 1981, 9 (4): 271- 288 doi: 10.1080/03081088108817379
17	Yuan S , Liao A , Lei Y . Least squares Hermitian solution of the matrix equation (AXB, CXD)=(E, F) with the least norm over the skew field of quaternions. Mathematical and Computer Modelling, 2008, 48 (1/2): 91- 100
18	Saad Y . Iterative Methods for Sparse Linear Systems. Philadelphia: SIAM, 2003
19	Boumal N , Mishra B , Absil P A , Sepulchre R . Manopt, a Matlab toolbox for optimization on manifolds. Journal of Machine Learning Research, 2014, 15 (1): 1455- 1459
20	Zhu X . A Riemannian conjugate gradient method for optimization on the Stiefel manifold. Computational Optimization and Applications, 2017, 67 (1): 73- 110 doi: 10.1007/s10589-016-9883-4
21	Dai Y . A nonmonotone conjugate gradient algorithm for unconstrained optimization. Journal of System Science and Complexity, 2002, 15, 139- 145
22	Li J F , Li W , Vong S W , et al. A Riemannian optimization approach for solving the generalized eigenvalue problem for nonsquare matrix pencils. Journal of Scientific Computing, 2020, 82 (3): 1- 43

	CT.(s)	IT.	Grad.	Obj.	CT.(s)	IT.	Grad.	Obj.
	$(U^{(0)}, V^{(0)})$取(a)				$(U^{(0)}, V^{(0)})$取(b)
Hybrid-Newton	3.31	96/5	1.38$\times 10^{-10}$	-56.23	1.38	157/3	3.81$\times 10^{-10}$	-56.23
	$(U^{(0)}, V^{(0)})$取(c)				$(U^{(0)}, V^{(0)})$取(d)
Hybrid-Newton	3.14	159/5	1.74$\times 10^{-8}$	-56.22	3.66	187/7	6.03$\times 10^{-7}$	-56.23

L	CT.(s)	IT.	$\\|r^{(k)}_L\\|_2/\\|g^{(k)}\\|_2$	L	CT.(s)	IT.	$\\|r^{(k)}_L\\|_2/\\|g^{(k)}\\|_2$
$(U^{(0)}, V^{(0)})$取(a)				$(U^{(0)}, V^{(0)})$取(b)
1	0.75	130	1.78$\times 10^{-2}$	1	0.49	123	2.45$\times 10^{-3}$
2	0.60	161	5.78$\times 10^{-6}$	2	0.39	95	1.27$\times 10^{-3}$
3	0.53	140	3.82$\times 10^{-4}$	3	0.29	72	5.67$\times 10^{-5}$
4	0.30	71	9.47$\times 10^{-5}$
5	0.33	86	3.49$\times 10^{-5}$
$(U^{(0)}, V^{(0)})$取(c)				$(U^{(0)}, V^{(0)})$取(d)
1	0.84	148	7.49$\times 10^{-5}$	1	0.26	69	2.77$\times 10^{-2}$
2	0.75	142	5.82$\times 10^{-6}$	2	0.50	129	5.91$\times 10^{-3}$
3	0.44	113	8.08$\times 10^{-4}$	3	0.47	118	3.28$\times 10^{-3}$
4	0.49	132	4.50$\times 10^{-4}$	4	0.63	147	9.80$\times 10^{-7}$
5	0.23	59	6.50$\times 10^{-5}$	5	0.43	112	2.45$\times 10^{-3}$
				6	0.59	149	1.24$\times 10^{-4}$
				7	0.29	77	4.70$\times 10^{-4}$

[1]	孙晓林,王华. 几类广义Sylvester算子方程的可解性[J]. 数学物理学报, 2022, 42(6): 1640-1652.
[2]	刘月园,王凯,秦树娟,李姣芬. 列正交约束下广义Sylvester方程极小化问题的有效算法[J]. 数学物理学报, 2021, 41(2): 479-495.

复矩阵截断奇异值分解的一类混合算法

A Hybrid Algorithm for Solving Truncated Complex Singular Value Decomposition

RichHTML

PDF (PC)

摘要/Abstract

引用本文

使用本文

图/表 5

参考文献 22

相关文章 2

Metrics

本文评价

推荐阅读 10