中文

Operations Research Transactions >

2023 , Vol. 27 >Issue 3: 96 - 108

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2023.03.007

Two new accelerated proximal gradient algorithms for Toeplitz matrix completion

Expand
  • 1. Department of Mathematics, Taiyuan Normal University, Jinzhong 030619, Shanxi, China

Received date: 2021-05-06

  Online published: 2023-09-14

Fold

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

Cite this article

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 . DOI: 10.15960/j.cnki.issn.1007-6093.2023.03.007

References

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.
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.
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.
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.
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.
17 KuT,KuoC.Design and analysis of Toeplitz preconditioners[J].IEEE Transactions on Signal Processing,1992,40(1):129-141.
18 AKaikeH.Block Toeplitz matrix inversion[J].SIAM Journal on Applied Mathematics,1973,24(2):234-241.
19 WangC L,LiC.A mean value algorithm for Toeplitz matrix completion[J].Applied Mathematics Letters,2015,41,35-40.
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.
21 WangC L,LiC.A structure-preserving algorithm for Toeplitz matrix completion (in Chinese)[J].Scienta Sinica Mathematica,2016,46,1-16.
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.
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.
28 ChenY X,ChiY J.Robust spectral compressed sensing via structured matrix completion[J].IEEE Transactions on Information Theory,2014,60(10):6576-6600.
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.
Options
Outlines

/

〈 〉