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

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

Abstract

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

CLC Number:

O246

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.

Figures/Tables 9

References 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} $

Two new accelerated proximal gradient algorithms for Toeplitz matrix completion

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 9

References 36

Related Articles 0

Recommended Articles

Metrics

Comments

Size$ (n_{1}\times n_{2}) $	rank$ (D) $	algorithm	#iter	time/s	$ \frac{\\|\hat{Y}-M\\|_{F}}{\\|M\\|_{F}} $
100$ \times $ 90	10	APG	301	34.684 7	8.534 2$ \times10^{-4} $
		MAPG	50	11.095 2	2.735 8$ \times10^{-4} $
		MMAPG	62	5.069 5	2.964 0$ \times10^{-4} $
300$ \times $ 250	15	APG	881	96.120 5	2.496 4$ \times10^{-3} $
		MAPG	59	4.533 5	4.035 8$ \times10^{-4} $
		MMAPG	169	8.538 2	4.224 5$ \times10^{-4} $
500$ \times $ 400	20	APG	779	85.199 4	4.1607$ \times10^{-3} $
		MAPG	67	5.904 0	3.473 0$ \times10^{-4} $
		MMAPG	83	15.193 0	4.315 1$ \times10^{-4} $
1 000$ \times $ 800	20	APG	580	566.803 8	1.2223$ \times10^{-3} $
		MAPG	39	31.808 2	3.132 8$ \times10^{-4} $
		MMAPG	42	37.706 4	3.659 0$ \times10^{-4} $
2 000$ \times $ 1500	20	APG	871	940.660 1	5.6060$ \times10^{-3} $
		MAPG	97	128.454 2	4.433 8$ \times10^{-4} $
		MMAPG	99	130.319 2	5.129 5$ \times10^{-4} $
3 000$ \times $ 2 000	20	APG	1036	1 501.897 0	8.636 0$ \times10^{-3} $
		MAPG	77	58.457 0	4.890 0$ \times10^{-4} $
		MMAPG	82	63.596 0	6.293 1$ \times10^{-4} $
5 000$ \times $ 3 500	20	APG	779	3 025.272 5	2.666 2$ \times10^{-3} $
		MAPG	50	145.892 1	3.147 5$ \times10^{-4} $
		MMAPG	60	139.833 2	3.836 3$ \times10^{-4} $

Size$(n_{1}\times n_{2})$	rank$(D)$	algorithm	#iter	time/s	$\frac{\\|\hat{Y}-M\\|_{F}}{\\|M\\|_{F}}$
100$\times$ 90	10	APG	428	35.285 6	5.808 4$\times10^{-4}$
		MAPG	33	1.788 3	1.621 0$\times10^{-4}$
		MMAPG	31	1.469 8	1.597 8$\times10^{-4}$
300$\times$ 250	15	APG	517	36.406 3	9.624 7$\times10^{-4}$
		MAPG	29	1.152 3	1.872 1$\times10^{-4}$
		MMAPG	33	1.665 9	2.818 2$\times10^{-4}$
500$\times$ 400	20	APG	614	57.376 9	9.184 6$\times10^{-4}$
		MAPG	39	2.695 0	2.605 8$\times10^{-4}$
		MMAPG	38	13.849 6	3.429 7$\times10^{-4}$
1 000$\times$ 800	20	APG	561	378.372 9	1.154 0$\times10^{-3}$
		MAPG	33	43.929 4	2.293 4$\times10^{-4}$
		MMAPG	32	19.458 8	2.800 6$\times10^{-4}$
2 000$\times$ 1 500	20	APG	461	262.338 0	8.906 0$\times10^{-4}$
		MAPG	31	12.905 9	2.147 4$\times10^{-4}$
		MMAPG	33	20.390 1	2.929 4$\times10^{-4}$
3 000$\times$ 2 000	20	APG	771	661.011 7	4.235 9$\times10^{-3}$
		MAPG	49	49.499 7	2.691 2$\times10^{-4}$
		MMAPG	50	56.994 5	3.915 9$\times10^{-4}$
5 000$\times$ 3 500	20	APG	452	1 473.825 4	7.245 8$\times10^{-4}$
		MAPG	31	49.339 7	1.821 6$\times10^{-4}$
		MMAPG	31	63.711 3	2.376 8$\times10^{-4}$