两种新的Toeplitz矩阵填充加速临近梯度算法

doi:10.15960/j.cnki.issn.1007-6093.2023.03.007

摘要/Abstract

摘要：

本文提出了两种改进的Toeplitz矩阵填充加速临近梯度算法，使迭代矩阵每一步都保持Toeplitz结构，从而降低了奇异值分解时间。在理论上，证明了新算法在一些合理条件下的收敛性。同时，数值实验表明，在Toeplitz矩阵填充问题中，新算法比加速临近梯度(APG)算法在时间上有明显减少。

关键词: 矩阵填充, Toeplitz矩阵, 加速临近梯度算法

Abstract:

In this paper, we propose two modified accelerated proximal gradient algorithms for Toeplitz matrix completion in which the iterative matrices keep the Toeplitz structure in each step to decrease SVD times. Furthermore, we prove the convergence of the new algorithms under some reasonal conditions. Finally, numerical experiments show that the new algorithms are much more effective than the accelerated proximal gradient (APG) algorithm for Toeplitz matrix completion in CPU times.

Key words: matrix completion, Toeplitz matrix, accelerated proximal gradient algorithm

中图分类号:

O246

王川龙, 牛建华, 申倩影. 两种新的Toeplitz矩阵填充加速临近梯度算法[J]. 运筹学学报, 2023, 27(3): 96-108.

Chuanlong WANG, Jianhua NIU, Qianying SHEN. Two new accelerated proximal gradient algorithms for Toeplitz matrix completion[J]. Operations Research Transactions, 2023, 27(3): 96-108.

图/表 9

表1

表2

表3

表4

表5

表6

表7

表8

图1

参考文献 36

1	Amit Y, Fink M, Srebro N, et al. Uncovering shared structures in multiclass classification[C]//Processings of the 24th International Conference on Machine Learing, 2007: 17-24.
2	ArgyriouA,EvgeniouT,PontilM.Multi-task feature learing[J].Advances in Neural Information Processing Systems,2007,19,41-48.
3	MesbahiM,PapavassilopoulosG P.On the rank minimization problem over a positive semidefinite linear matrix inequality[J].IEEE Transactions on Automatic Control,1997,42(2):239-243. doi: 10.1109/9.554402
4	BertalmioM,SapiroG,CasellesV,et al.Image inpainting[J].Computer Grapher,2000,34(9):417-424.
5	TomasiC,KanadeT.Shape and motion from image streams under orthography: a factorization method[J].International Journal of Computer Vision,1992,90(2):137-154.
6	CandèsE J,RechtB.Exact matrix completion via convex optimization[J].Foundations of Computational Mathematics,2009,9(6):717-772. doi: 10.1007/s10208-009-9045-5
7	Fazel M. Matrix rank minimization with applications[D]. Stanford: Stanford University, 2002.
8	Fazel M, Hindi H, Boyd S P. Log-det heuristic for matrix rank minimization with applications to Hankel and Euclidean distance matrices[C]//Proceedings of the American Control Conference, 2003: 2156-2162.
9	TohK C,YunS.An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems[J].Pacific Journal of Optimization,2010,6(3):615-640.
10	MaS,GoldfarbD,ChenL.Fixed point and Bregman iterative methods for matrix rank minimization[J].Mathematical Programming,2011,128(1/2):321-353.
11	CaiJ F,CandèsE J,ShenZ.A singular value thresholding algorithm for matrix completion[J].SIAM Journal Optimization,2010,20(4):1956-1982. doi: 10.1137/080738970
12	Lin Z, Chen M, Wu L, et al. The augmented Lagrange multiplier method for exact recovery of corrupted low-rank matrices[J]. 2010, arxiv: 1009.5055.
13	MukhexjeeB N,MaitiS S.On some properties of positive definite Toeplitz matrices and their possible applications[J].Linear Algebra with Applications,1988,102,211-240. doi: 10.1016/0024-3795(88)90326-6
14	GrenanderU,SzegöG,KacM.Toeplitz forms and their applications[J].Physics Today,1958,11(10):38-38.
15	ChillagD.Regular representations of semisimple algebras, separable field extensions, group characters, generalized cirulants, and generalized cyclic codes[J].Linear Algebra with Applications,1995,218(3):147-183.
16	BunchJ.Stability of methods for solving Toeplitz systems of equations[J].SIAM Journal on Scientific and Statistical Computing,1985,6,349-364. doi: 10.1137/0906025
17	KuT,KuoC.Design and analysis of Toeplitz preconditioners[J].IEEE Transactions on Signal Processing,1992,40(1):129-141. doi: 10.1109/78.157188
18	AKaikeH.Block Toeplitz matrix inversion[J].SIAM Journal on Applied Mathematics,1973,24(2):234-241. doi: 10.1137/0124024
19	WangC L,LiC.A mean value algorithm for Toeplitz matrix completion[J].Applied Mathematics Letters,2015,41,35-40. doi: 10.1016/j.aml.2014.10.013
20	WangC L,LiC,WangJ.A modified augmented Lagrange multiplier algorithm for Toeplitz matrix completion[J].Advances in Computational Mathematics,2016,42(5):1209-1224. doi: 10.1007/s10444-016-9459-y
21	WangC L,LiC.A structure-preserving algorithm for Toeplitz matrix completion (in Chinese)[J].Scienta Sinica Mathematica,2016,46,1-16. doi: 10.1360/N012014-00278
22	ChenY,ChiY.Robust spectral compressed sensing via structured matrix completion[J].IEEE Transactions on Information Theory,2011,59,2182-2195.
23	CaiJ F,QuX,XuW,et al.Robust recovery of complex exponential signals from random Gaussian projections via low rank Hankel matrix reconstruction[J].Applied & Computational Harmonic Analysis,2016,41,470-490.
24	FazelM,PongT K,SunD,et al.Hankel matrix rank minimization with applications to system identification and realization[J].SIAM Journal on Matrix Analysis and Applications,2013,34,946-977. doi: 10.1137/110853996
25	Cai J F, Liu S, Xu W. A fast algorithm for reconstruction of spectrally sparse signals in super-resolution[C]//Wavelets & Sparsity XVI. International Society for Optics and Photonics, 2015: 95970A.
26	CaiJ F,WangT,WeiK.Fast and provable algorithms for spectrally sparse signal reconstruction via low-rank Hankel matrix completion[J].Applied & Computational Harmonic Analysis,2019,
27	CaiJ F,WangT,WeiK.Spectral compressed sensing via projected gradient descent[J].SIAM Journal on Optimization,2018,28(3):2625-2653. doi: 10.1137/17M1141394
28	ChenY X,ChiY J.Robust spectral compressed sensing via structured matrix completion[J].IEEE Transactions on Information Theory,2014,60(10):6576-6600. doi: 10.1109/TIT.2014.2343623
29	LukF T,QiaoS.A fast singular value algorithm for Hankel matrices[J].Contemporary Mathematics,2003,
30	XuW,QiaoS.A fast SVD algorithm for square Hankel matrices[J].Linear Algebra and Its Applications,2008,428(2):550-563.
31	GolubG H,VanLoanC F.Matrix Computations[M].Baltimore:The Johns Hopkins University Press,1996.
32	Van LoanC.Computational Frameworks for the Fast Fourier Transform[M].Philadelphia:Society for Industrial and Applied Mathematics,1992:1-75.
33	Kailath T, Sayed A H. Fast reliable algorithms for matrices with structure[M]//Society for Industrial and Applied Mathematics, Philadelphia: University City Science Center Philadelphia, 1999.
34	WangC L,ZhangJ M.Strcuture-preserving thresholding algorithm based on F-norm for Hankel matrix completion (in Chinese)[J].Journal on Numerical Methods and Computer Applications,2017,39(1):60-72.
35	ZhangJ M,WangC L.Strcuture-preserving thresholding algorithm based on $l_{\infty}$-norm for Hankel matrix completion (in Chinese)[J].Acta Mathematicae Applicatae Sinica,2019,42(1):55-70.
36	BeckA,TebouleM.A fast iterative shrinkage-thresholding algorithm for linear inverse problems[J].Society for Industrial and Applied Mathematics,2009,2(1):183-202.

Size$ (n\times n) $	rank$ (D) $	algorithm	#iter	time/s	$ \frac{\\|\hat{Y}-M\\|_{F}}{\\|M\\|_{F}} $
1 000	10	APG	657	570.861 0	1.052 5$ \times10^{-3} $
		MAPG	35	25.991 2	2.351 9$ \times10^{-4} $
		MMAPG	39	34.107 1	2.486 7$ \times10^{-4} $
2 000	10	APG	519	426.186 6	3.531 4$ \times10^{-3} $
		MAPG	57	32.897 3	3.848 2$ \times10^{-4} $
		MMAPG	68	41.323 5	2.725 6$ \times10^{-4} $
3 000	10	APG	303	305.135 2	1.259 3$ \times10^{-3} $
		MAPG	34	29.441 5	2.881 1$ \times10^{-4} $
		MMAPG	35	27.520 4	2.929 3$ \times10^{-4} $
4 000	10	APG	1 167	2 824.142 0	1.306 5$ \times10^{-2} $
		MAPG	161	423.087 5	7.509 6$ \times10^{-4} $
		MMAPG	124	285.759 4	5.626 6$ \times10^{-4} $
5 000	10	APG	452	943.979 2	7.537 7$ \times10^{-3} $
		MAPG	68	102.692 8	4.421 1$ \times10^{-4} $
		MMAPG	70	98.756 5	5.263 7$ \times10^{-4} $
10 000	10	APG	424	3 202.562 5	7.336 5$ \times10^{-4} $
		MAPG	34	189.728 2	1.500 8$ \times10^{-4} $
		MMAPG	48	308.705 8	1.039 6$ \times10^{-4} $

Size$ (n\times n) $	rank$ (D) $	algorithm	#iter	time/s	$ \frac{\\|\hat{Y}-M\\|_{F}}{\\|M\\|_{F}} $
1 000	10	APG	215	240.750 1	1.115 7$ \times10^{-3} $
		MAPG	41	43.819 4	3.623 7$ \times10^{-4} $
		MMAPG	59	68.720 0	3.808 1$ \times10^{-4} $
2 000	10	APG	416	370.881 2	1.630 7$ \times10^{-3} $
		MAPG	35	26.054 5	2.969 3$ \times10^{-4} $
		MMAPG	36	25.016 8	3.160 5$ \times10^{-4} $
3 000	10	APG	286	300.108 2	3.098 8$ \times10^{-3} $
		MAPG	54	60.777 6	2.661 5$ \times10^{-4} $
		MMAPG	39	35.036 6	2.835 4$ \times10^{-4} $
4 000	10	APG	901	1 572.753 1	6.630 2$ \times10^{-3} $
		MAPG	58	78.604 1	3.316 6$ \times10^{-4} $
		MMAPG	71	98.771 2	4.725 4$ \times10^{-4} $
5 000	10	APG	260	733.809 7	3.151 4$ \times10^{-3} $
		MAPG	35	102.718 2	3.323 4$ \times10^{-4} $
		MMAPG	43	87.172 6	3.113 2$ \times10^{-4} $
10 000	10	APG	399	3 239.851 5	1.026 3$ \times10^{-3} $
		MAPG	40	238.620 4	2.756 5$ \times10^{-4} $
		MMAPG	44	279.447 8	1.503 3$ \times10^{-4} $

Size$ (n\times n) $	rank$ (D) $	algorithm	#iter	time/s	$ \frac{\\|\hat{Y}-M\\|_{F}}{\\|M\\|_{F}} $
1 000	10	APG	88	84.640 5	2.3119$ \times10^{-4} $
		MAPG	29	24.206 5	2.144 7$ \times10^{-4} $
		MMAPG	32	26.872 0	2.184 4$ \times10^{-4} $
2 000	10	APG	386	311.391 1	1.336 6$ \times10^{-3} $
		MAPG	39	22.774 5	2.532 2$ \times10^{-4} $
		MMAPG	32	17.763 2	3.068 4$ \times10^{-4} $
3 000	10	APG	44	42.906 4	6.467 5$ \times10^{-4} $
		MAPG	29	27.082 4	1.501 8$ \times10^{-4} $
		MMAPG	29	26.397 8	1.922 4$ \times10^{-4} $
4 000	10	APG	502	1 152.059 3	9.443 3$ \times10^{-4} $
		MAPG	42	97.230 2	2.475 0$ \times10^{-4} $
		MMAPG	33	72.507 1	2.793 7$ \times10^{-4} $
5 000	10	APG	524	1 645.835 0	1.979 3$ \times10^{-3} $
		MAPG	38	82.866 0	2.212 8$ \times10^{-4} $
		MMAPG	36	85.316 4	2.567 9$ \times10^{-4} $
10 000	10	APG	334	2 740.484 2	5.967 0$ \times10^{-4} $
		MAPG	30	192.011 2	1.273 7$ \times10^{-4} $
		MMAPG	28	176.698 0	1.054 9$ \times10^{-4} $

Size$ (n\times n) $	rank$ (D) $	algorithm	#iter	time/s	$ \frac{\\|\hat{Y}-M\\|_{F}}{\\|M\\|_{F}} $
1 000	20	APG	707	608.956 1	1.258 5$ \times10^{-3} $
		MAPG	52	29.690 3	3.516 6$ \times10^{-4} $
		MMAPG	65	42.586 9	3.264 8$ \times10^{-4} $
2 000	20	APG	1 296	1 508.764 0	7.781 2$ \times10^{-3} $
		MAPG	116	116.886 2	6.054 1$ \times10^{-4} $
		MMAPG	108	109.639 8	6.152 3$ \times10^{-4} $
3 000	20	APG	836	927.442 1	2.818 2$ \times10^{-3} $
		MAPG	53	45.220 6	4.333 7$ \times10^{-4} $
		MMAPG	68	62.689 3	4.256 3$ \times10^{-4} $
4 000	20	APG	709	1 301.724 8	4.550 7$ \times10^{-3} $
		MAPG	60	87.663 8	4.285 6$ \times10^{-4} $
		MMAPG	95	151.903 8	4.672 7$ \times10^{-4} $
5 000	20	APG	941	2 462.590 5	2.340 0$ \times10^{-3} $
		MAPG	66	138.697 1	3.020 5$ \times10^{-4} $
		MMAPG	70	246.049 1	3.746 1$ \times10^{-4} $
10 000	20	APG	674	6 008.432 8	1.998 7$ \times10^{-3} $
		MAPG	61	388.947 8	3.775 4$ \times10^{-4} $
		MMAPG	55	342.700 2	4.619 2$ \times10^{-4} $

Size$ (n\times n) $	rank$ (D) $	algorithm	#iter	time/s	$ \frac{\\|\hat{Y}-M\\|_{F}}{\\|M\\|_{F}} $
1 000	20	APG	589	354.209 3	1.227 7$ \times10^{-3} $
		MAPG	46	21.096 4	2.757 5$ \times10^{-4} $
		MMAPG	50	25.895 5	3.375 8$ \times10^{-4} $
2 000	20	APG	544	473.859 6	1.076 1$ \times10^{-3} $
		MAPG	36	25.880 8	2.928 6$ \times10^{-4} $
		MMAPG	37	17.227 2	3.494 3$ \times10^{-4} $
3 000	20	APG	778	998.839 7	1.049 3$ \times10^{-2} $
		MAPG	90	105.179 6	8.599 8$ \times10^{-4} $
		MMAPG	41	36.883 4	3.486 6$ \times10^{-4} $
4 000	20	APG	684	1 180.010 6	5.414 8$ \times10^{-3} $
		MAPG	70	108.780 2	5.244 1$ \times10^{-4} $
		MMAPG	74	117.686 3	4.553 5$ \times10^{-4} $
5 000	20	APG	487	1 256.637 7	1.214 8$ \times10^{-3} $
		MAPG	36	64.199 2	2.160 0$ \times10^{-4} $
		MMAPG	41	144.703 0	2.717 1$ \times10^{-4} $
10 000	20	APG	794	5 919.227 9	5.706 5$ \times10^{-3} $
		MAPG	75	528.908 3	5.149 6$ \times10^{-4} $
		MMAPG	322	2 473.325 6	5.199 6$ \times10^{-4} $