运筹学学报 >
2023 , Vol. 27 >Issue 3: 96 - 108
DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2023.03.007
两种新的Toeplitz矩阵填充加速临近梯度算法
收稿日期: 2021-05-06
网络出版日期: 2023-09-14
基金资助
国家自然科学基金(11371275);太原师范学院研究生教育创新项目(SYYJSJC-2016)
Two new accelerated proximal gradient algorithms for Toeplitz matrix completion
Received date: 2021-05-06
Online published: 2023-09-14
本文提出了两种改进的Toeplitz矩阵填充加速临近梯度算法，使迭代矩阵每一步都保持Toeplitz结构，从而降低了奇异值分解时间。在理论上，证明了新算法在一些合理条件下的收敛性。同时，数值实验表明，在Toeplitz矩阵填充问题中，新算法比加速临近梯度(APG)算法在时间上有明显减少。
关键词： 矩阵填充; Toeplitz矩阵; 加速临近梯度算法
王川龙, 牛建华, 申倩影 . 两种新的Toeplitz矩阵填充加速临近梯度算法[J]. 运筹学学报, 2023 , 27(3) : 96 -108 . DOI: 10.15960/j.cnki.issn.1007-6093.2023.03.007
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.
| 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. |
/
| 〈 |
|
〉 |
