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

Sep.,2023Vo1.27No.3Operations ResearchTransactions2023年9 月第2 7 卷第3期运筹学学报DOI:10.15960/ki.issn.1007-6093.2023.03.007两种新的Toeplitz矩阵填充加速临近梯度算法*王川龙1,t牛建华1申倩影1摘要本文提出了两种改进的Toeplitz矩阵填充加速临近梯度算法，使迭代矩阵每一步都保持Toeplitz结构，从而降低了奇异值分解时间。在理论上，证明了新算法在一些合理条件下的收敛性。同时，数值实验表明，在Toeplitz矩阵填充问题中，新算法比加速临近梯度(APG）算法在时间上有明显减少。关键词矩阵填充，Toeplitz矩阵，加速临近梯度算法中图分类号0 2 462010数学分类号15A83,15A18,15B05,90C25Two new accelerated proximal gradient algorithmsfor Toeplitz matrix completion*WANG Chuanlongl.tNIU JianhualSHENNQianyinglAbstract In this paper,we propose two modified accelerated proximal gradient al-gorithms for Toeplitz matrix completion in which the iterative matrices keep the Toeplitzstructure in each step to decrease SvD times.Furthermore,we prove the convergence ofthe new algorithms under some reasonal conditions.Finally,numerical experiments showthat the new algorithms are much more effective than the accelerated proximal gradient(APG)algorithm for Toeplitz matrix completion in CPU times.Keywords matrix completion,Toeplitz matrix,accelerated proximal gradient algo-rithmChinese Library Classification O2462010 Mathematics Subject Classification 15A83,15A18,15B05,90C25矩阵填充是近年来矩阵优化的一个研究热点之一，矩阵填充的目的是在样本矩阵元素部分已知的前提下，合理准确地恢复低秩矩阵。矩阵填充在机器学习1,2、控制3、图像修复4、计算机视觉5等方面有重要的应用价值。设X Rn1xn2，M E Rn i x n 2,其中（Mij:(i,j）E),是已知元素下标集。那么低收稿日期：2 0 2 1-0 5-0 6*基金项目：国家自然科学基金(No.11371275)，太原师范学院研究生教育创新项目(No.SYYJSJC-2016)1.太原师范学院数学系，山西晋中0 30 6 19;Department of Mathematics，T a i y u a n No r ma l U n i v e r s i t y,Jinzhong 030619,Shanxi,China+通信作者E-mail:973期两种新的Toeplitz矩阵填充加速临近梯度算法秩矩阵X填充问题可以通过求解以下优化模型来完成：minrank(X),(1)s.t.Xij=Mij,(i,i)E2,其中rank(X)表示矩阵 X 的秩。事实上，由于矩阵的秩函数是不连续的，所以很难直接求解问题(1)。Candes 和Recht6)将问题(1）松弛为如下凸优化模型：minIX，(2)s.t.Xij=Mij,(i,j)E2,其中 X=k(X),ok(X)表示秩为r 的矩阵 X Rn1xn2的第k大奇异值。k=1随后，针对一般的低秩矩阵X，多种算法相继被提出来求解凸优化模型(2)。例如加速临近梯度(APG)9 方法、不动点延拓近似 SVD(FPCA)10 算法、奇异值阅值(SVT)11算法、增广拉格朗日乘子（ALM)12算法。Toeplitz矩阵广泛应用于图像处理13、数字信号处理14、最小二乘估计15、控制理论16 和频谱分析17 等领域。通过对Toeplitz 矩阵行、列的逆变换，可以将Toeplitz矩阵转化为 Hankel 矩阵33,得到了 Toeplitz/Hankel 矩阵填充问题的许多结果。Chen 等人2 提出了基于结构化矩阵填充的增强矩阵填充（EMaC）算法，这并不需要模型顺序的先验知识。Cai 等人2 3在高斯随机采样模型下研究了相同的方法。Fazel 等人2 4 讨论了正则化Hankel 矩阵核范数最小化问题的各种一阶方法。Wang等人提出了均值算法19、改进的增广拉格朗日乘子算法2 0 和保结构算法2 1。在文献19-2 1 中，迭代矩阵保持Toeplitz结构。针对低秩Hankel 矩阵填充问题，提出了PWGD25、IH T、FIH T 2 6 和PGD27 等非凸算法。本文提出了两种改进的APG算法用于Toeplitz矩阵填充。首先，给出一些定义。定义131 一个 n n Toeplitz 矩阵 T e Rnxn 有以下形式：tot1tn-2tn-1t1totn-3tn-2T=t-n+2t-n+3tot1t-n+1t-n+2t-1to注：T由其第一行和第一列决定，,共有(2 n1)个元素。定义2 31)（奇异值分解(SVD)秩为r的矩阵XERn1n2的奇异值分解定义为：X=UZ,V*,Z,=diag(o1,.,or),其中URn1xr和VeRn2xr是是正交的,0 1 2.0r0。定义311(奇异值阈值算子）又对于任意的TO，奇异值阈值算子D定义如下：Dr(X):=UD(2)V*,D(2)=diag(i-T)+),9827卷王川龙，牛建华，申倩影其中X=UZ,V*是秩为r的矩阵X的奇异值分解，oi-T)+=0i-T,如果0T,0,如果QiT。本文的安排如下：第1节详细给出了Toeplitz矩阵填充的两种改进算法，第2 节给出了收敛性分析，第3节通过数值实验将我们的算法与APG算法进行了比较，第4节对本文进行总结。注实数集合由 R 表示，n1n实矩阵集合由 Rn1xm2表示。设X 是一个矩阵，r(X)表示 的秩，Xi；表示X的第（i,）项。矩阵X的列划分用X=（a 1,，a n）表示。矩阵的核范数用IX表示，Frobenius范数用IXIF表示。X*是矩阵X的共轭转置。两个矩阵之间的内积用0,0，L=1,n E(0,1)。令Xo=0,Yo=0,to=1,k:=0。第2 步：计算矩阵Gk的奇异值分解,Gk=Yk-（T k)-1(Pa(Yk）Pa(M),Uk,Zk,Vi k=svd(Gk),Tk993期两种新的Toeplitz矩阵填充加速临近梯度算法Th=Lf。令Xh+1=UkDk(2k)VT。Tk第3步：如果X+1-XkllF/Xk+1llF0,0,Lf=1,n(0,1),令Xo=0,Y=0,to=1,k:=0。第2 步：计算矩阵Gk的奇异值分解,Gk=Yk-（T k)-1(Pa(Ys）-Pn(M),Uk,Zk,Va k=lansvd(Gk),Tk10027卷王川龙，牛建华，申倩影Tk=Lf。X k+1=U k D u k(2k)VT。Tk第3步：计算al=mean(diag(Xk+1,l),l E 2,令Xk+1=ZaRt。第4步：如果IXk+1-XllF/Xk+1lF0,0,Lf=1,n(0,1)，令X=0,Y=0,to=1,k:=0。第2 步：计算矩阵Gk的奇异值分解，Gk=Yh-（T k)-1(Pa(Yk）-Pa(M),Uk,Zk,Vh uk=lansvd(Gk),TKk=Lf。X k+1=U k D u k(2%)VT。Tk第3步：计算al=(max(diag(Xh+1,l)+min(diag(Xh+1,l)/2,l E 2,令Xk+1=ZaiRt。第4步：如果Xk+1-XllF/Xk+1F，停止；否则，转第5步。第5步：计算1+V1+4(tk)2t一tk+1=k+1=max(nk,),Yk+1=Xk+1+(Xk+1-Xk)2tk+1转第2 步。2收敛性分析在这一节中，我们将讨论算法2 和算法3的收敛性。首先，从罚函数法的理论出发，下面的结果直接成立：引理3令X是问题（4)的最优解。如果0,则lim Xk=X*,k-80其中X*是问题(3）的最优解。为了方便起见，我们将介绍一些在后续文章中需要的符号，如下所示。F(X,)=lXI*+lPa(X-M)/,2f(X)=Pa(X-M)Ie,g(X,)=llXI*,IX=Ak+1I=k+1101两种新的Toeplitz矩阵填充加速临近梯度算法3期Q(X,Y,)=f(Y)+(X-Y,Vf(Y)+IX-Y/&+X,(5)2Xk+1=arg min Q(X,Yk,k),XXk+1=E(Xk+1),其中E(Xk+1）是算法2 中的均值运算或算法3中的最大最小值运算。引理436)对于任意YRmxn，函数Q(X,Y,)存在最小值点对于部分Wag(Z,u）以下等式成立Vf(Y)+(Z-Y)+W=0,或者OQ(X,Y,)(U-2)T0,UERmxnX=2引理5令Xk+1是问题页(5)的最优解，Xk+1=E(Xk+1),有aQ(X,Yk,k)0g(X,k)0g(X,k)EEEX=Xk+1X=Xk+1X=Xk+1证明aQ(X,Yk,k)og(X,k)Vf(Yk)+(Xk+1-Yk)+8XX=Xk+18XX=Xk+1ag(X,k)8g(X,k)Xk+1-Xk+1+ax所以，aQ(X,Yk,k)og(X,k)Og(X,k)EEE8XX=Xk+1X=Xk+18XX=Xk+1假设对于Xk+1，给出以下假设(其中k=0,1,2,.)：(1)Xk-Xh+1,E(aQ(X,Yk,Mk)0,8XX=Xk+1=(Xk-Xi+1,E(）X=Xk+1X=Xk+1式(6)成立，式(7)也是如此。定理1令（X,Yk,uk是由算法2 产生的序列。如果假设成立，有2Xo-X*/F(Xk+1)-F(X*)(8)(k+1)2其中X*是极小化矩阵。进一步，如果k=o()，有a/xl+/R(Xx-M)/-x l/0()。证明与文献36 中定理4.4的证明方法相同，有lXil+Po(Xk-M)/Q(Xk,Yk)Q(X*,Yk)f(Y)+(X*-Yk,V f(Yk)+IX*-Yel/+kllX*。所以(Xl+/Pa(Xk-M)/-1X*)一k21(f(Yk)+(X*-Yh,Vf(Yk)+IX*-Yhl/)k其中0 Ck1，式(8)成立。103两种新的Toeplitz矩阵填充加速临近梯度算法3期3数值实验在本节中，通过与文献9中的APG算法比较来评估改进的加速临近梯度算法（MAPG、MMAPG）的性能，所有实验的计算环境都相同。在实验中，设置p=m/(2n1）作为采样密度，其中m 是观测到的对角线数。由于Toeplitz矩阵的特殊结构，得到0 m2n-1（注：在Toeplitz长方矩阵中，p=m/(n1+n-1)，0 m n 1+n-1)。用D表示待填充矩阵，表示输出矩阵,真实的Toeplitz矩阵用M表示。在数值实验中参数设置如下：o=Po(M)l2,=10-4o,=0.8,Lf=1,=10-5。表18 对三种算法进行了简要比较。表13是秩为10 的Toeplitz矩阵的填充，表46 是秩为2 0 的Toeplitz矩阵的填充，表7 8 是针对Toeplitz长方矩阵的填充。为了更直观地表示算法的有效性，在图1中，使用折线图给出了表1和表4的数值结果。表1MAPG、M M A PG 和APG的计算结果比较(p=0.3)Size(n n)rank(D)algorithm#itertime/sIY-MIEIMIF100010APG657570.86101.052510-3MAPG3525.99122.351910-4MMAPG3934.107 12.486710-4200010APG519426.186 63.531410-3MAPG5732.89733.848210-4MMAPG6841.32352.725610-4300010APG303305.13521.259310-3MAPG3429.44152.881110-4MMAPG3527.520 42.929310-4400010APG11672824.14201.306510-2MAPG161423.08757.509610-4MMAPG124285.75945.626610-45 00010APG452943.97927.537710-3MAPG68102.69284.421110-4MMAPG7098.75655.263710-41000010APG4243202.56257.336510-4MAPG34189.72821.500810-4MMAPG48308.70581.039610-4表2 MAPG、M M A PG 和APG的计算结果比较(p=0.4)Size(n n)rank(D)algorithm#itertime/sIY-MEIMIE100010APG215240.75011.115710-3MAPG4143.81943.623710-4MMAPG5968.72003.808110-4200010APG416370.88121.630710-3MAPG3526.05452.969310-4MMAPG3625.01683.160510-4300010APG286300.10823.098810-3MAPG5460.77762.661510-4MMAPG3935.03662.835410-4400010APG9011572.75316.630210-3MAPG5878.60413.316610-4MMAPG7198.771 24.725410-4500010APG260733.80973.151410-3MAPG35102.71823.323410-4MMAPG4387.17263.113210-41000010APG3993239.85151.026310-3MAPG40238.62042.756510-4MMAPG44279.44781.503310-410427卷王川龙，牛建华，申倩影表3MAPG、M M A PG 和APG的计算结果比较(p=0.5)IY-MIESize(n x n)rank(D)algorithm#itertime/sIMIF100010APG8884.64052.311910-4MAPG2924.20652.144710-4MMAPG3226.87202.184410-4200010APG386311.39111.336610-3MAPG3922.77452.532210-4MMAPG3217.76323.068410-4300010APG4442.906 46.467510-4MAPG2927.08241.501810-4MMAPG2926.39781.922410-4400010APG5021152.05939.443310-4MAPG4297.230 22.475010-4MMAPG3372.50712.793710-4500010APG5241645.83501.979310-3MAPG3882.86602.212810-4MMAPG3685.31642.567910-41000010APG3342740.48425.967010-4MAPG30192.01121.273710-4MMAPG28176.69801.054910-4表4MAPG、M M A PG 和APG的计算结果比较(p=0.3)Size(n n)rank(D)algorithm#itertime/sIY-MIEIMIF100020APG707608.95611.258510-3MAPG5229.69033.516610-4MMAPG6542.58693.264810-4200020APG12961508.76407.781210-3MAPG116116.88626.054110-4MMAPG108109.63986.152310-4300020APG836927.44212.818210-3MAPG5345.22064.333710-4MMAPG6862.68934.256310-4400020APG7091301.72484.550710-3MAPG6087.66384.285610-4MMAPG95151.90384.672710-4500020APG941.2462.59052.340010-3MAPG66138.69713.020510-4MMAPG70246.04913.746110-41000020APG6746008.43281.998710-3MAPG61388.94783.775 410-4MMAPG55342.70024.619210-4表5MAPG、M M A PG 和APG的计算结果比较(p=0.4)Size(n n)rank(D)algorithm#itertime/sIY-MIEIMIF100020APG589354.20931.227710-3MAPG4621.09642.757510-4MMAPG5025.89553.375810-4200020APG544473.85961.076110-3MAPG3625.88082.928610-4MMAPG3717.22723.494310-4300020APG778998.83971.049310-2MAPG90105.17968.599810-4MMAPG4136.88343.486610-4400020APG6841180.01065.414810-3MAPG70108.78025.244110-4MMAPG74117.68634.553510-4500020APG4871256.63771.214810-3MAPG3664.19922.160010-4MMAPG41144.70302.717110-41000020APG7945919.22795.706510-3MAPG75528.90835.149610-4MMAPG3222473.32565.199610-41053期两种新的Toeplitz矩阵填充加速临近梯度算法表6 MAPG、M M A PG 和APG的计算结果比较(p=0.5)Size(n n)rank(D)algorithm#itertime/sIY-MIEIMIF100020APG520408.93959.386710-4MAPG3112.84352.062 110-4MMAPG3116.35882.746210-4200020APG852910.45291.062910-2MAPG9180.20467.972910-4MMAPG9986.42757.065 710-4300020APG496896.78336.830610-4MAPG3129.54082.163 8 10-4MMAPG3133.673 62.941 010-4400020APG621340.01386.672 010-4MAPG3447.959 42.354510-4MMAPG3551.46733.230910-4500020APG6691555.83532.290 410-3MAPG48102.48072.166 210-4MMAPG34100.78742.573910-41000020APG5914094.78621.799 410-3MAPG54363.656 73.428 110-4MMAPG54368.55833.703 410-4表7 MAPG、M M A PG 和APG的计算结果比较(长方矩阵，p=0.3)Size(n1 n2)rank(D)algorithm#itertime/sIY-MEIMIE100 9010APG30134.68478.534210-4MAPG5011.09522.735 810-4MMAPG625.06952.964010-4300 25015APG88196.12052.496 410-3MAPG594.53354.035 810-4MMAPG1698.53824.224510-450040020APG77985.19944.160710-3MAPG675.90403.473 010-4MMAPG8315.19304.315110-41000 80020APG580566.80381.222310-3MAPG3931.80823.132810-4MMAPG4237.706 43.659 010-42 000 150020APG871940.66015.606010-3MAPG97128.45424.433 810-4MMAPG99130.31925.129 510-43000 2 00020APG10361501.89708.636 0 10-3MAPG7758.45704.890010-4MMAPG8263.59606.293 110-45 000 3 50020APG7793025.27252.666 210-3MAPG50145.89213.147510-4MMAPG60139.83323.836310-410627卷王川龙，牛建华，申倩影表8 MAPG、M M A PG 和APG的计算结果比较(长方矩阵，p=0.5)rank(D)Size(n1 n2)algorithm#itertime/sIY-MIFIMIF1009010APG42835.28565.808 410-4MAPG331.78831.621 010-4MMAPG311.46981.597810-4300 25015APG51736.40639.624710-4MAPG291.15231.872 110-4MMAPG331.66592.818 210-450040020APG61457.37699.184610-4MAPG392.69502.605 8 10-4MMAPG3813.84963.429 710-4100080020APG561378.37291.154010-3MAPG3343.929 42.293 410-4MMAPG3219.45882.800 610-42000 150020APG461262.33808.906 010-4MAPG3112.90592.147 410-4MMAPG3320.39012.929 410-43 000 2 00020APG771661.01174.235910-3MAPG4949.49972.691210-4MMAPG5056.99453.915910-45000350020APG4521473.82547.245 810-4MAPG3149.33971.821610-4MMAPG3163.71132.376 810-470007000-APG-x-APG6000F6000-M A PG-M A PG5000-O-MMAPG5000-o-MMAPG上4000400030003000齐20002000100010000002000400060008000100000200040006000800010000Size(nxn)Size(nxn)(a)p=0.3,rank=10(b)p=0.3,rank=20图1MAPG、M M A PG 和APG的计算时间比较4结论和展望本文在APG算法的基础上，提出了两种改进的Toeplitz 矩阵填充加速临近梯度算法，即MAPG和MMAPG。在我们算法的每一步中都保留了Toeplitz结构。与APG算法相比，新算法具有更好的收敛性和更高的精度。另外，由于使用Toeplitz矩阵的快速奇异值分解，算法的时间比APG算法少的多。因此，两种改进方法都比APG算法更有效。107两种新的Toeplitz矩阵填充加速临近梯度算法3期参考文献1 Amit Y,Fink M,Srebro N,et al.Uncovering shared structures in multiclass classificationC/Processings of the 24th International Conference on Machine Learing,2007:17-24.2 Argyriou A,Evgeniou T,Pontil M.Multi-task feature learing J.Advances in Neural Infor-mation Processing Systems,2007,19:41-48.3 Mesbahi M,Papavassilopoulos G P.On the rank minimization problem over a positive semidef-inite linear matrix inequality J.IEEE Transactions on Automatic Control,1997,42(2):239-243.4 Bertalmio M,Sapiro G,Caselles V,et al.Image inpainting J.Computer Grapher,2000,34(9):417-424.5 Tomasi C,Kanade T.Shape and motion from image streams under orthography:a factorizationmethod J.International Journal of Computer Vision,1992,90(2):137-154.6 Candes E J,Recht B.Exact matrix completion via convex optimization J.Foundations ofComputational 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 toHankel and Euclidean distance matrices C/Proceedings of the American Control Conference,2003:2156-2162.9 Toh K C,Yun S.An accelerated proximal gradient algorithm for nuclear norm regularized leastsquares problems J.Pacific Journal of Optimization,2010,6(3):615-640.10 Ma S,Goldfarb D,Chen L.Fixed point and Bregman iterative methods for matrix rank mini-mization J.Mathematical Programming,2011,128(1/2):321-353.11 Cai J F,Candes E J,Shen Z.A singular value thresholding algorithm for matrix completionJ.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 ofcorrupted low-rank matrices J.2010,arxiv:1009.5055.13 Mukhexjee B N,Maiti S S.On some properties of positive definite Toeplitz matrices and theirpossible applications J.Linear Algebra with Applications,1988,102:211-240.14 Grenander U,Szego G,Kac M.Toeplitz forms and their applications J.Physics Today,1958,11(10):38-38.15 Chillag D.Regular representations of semisimple algebras,separable field extensions,groupcharacters,generalized cirulants,and generalized cyclic codes J.Linear Algebra with Applica-tions,1995,218(3):147-183.16 Bunch J.Stability of methods for solving Toeplitz systems of equations J.SIAM Journal onScientific and Statistical Computing,1985,6:349-364.17 Ku T,Kuo C.Design and analysis of Toeplitz preconditioners J.IEEE Transactions on SignalProcessing,1992,40(1):129-141.18 AKaike H.Block Toeplitz matrix inversion J.SIAM Journal on Applied Mathematics,1973,24(2):234-241.19 Wang C L,Li C.A mean value algorithm for Toeplitz matrix completion J.Applied Mathe-matics Letters,2015,41:35-40.20 Wang C L,Li C,Wang J.A modified augmented Lagrange multiplier algorithm for Toeplitzmatrix completion J.Advances in Computational Mathematics,2016,42(5):1209-1224.10827卷王川龙，牛建华，申倩影21 Wang C L,Li C.A structure-preserving algorithm for Toeplitz matrix completion(in Chinese)J.Scienta Sinica Mathematica,2016,46:1-16.22 Chen Y,Chi Y.Robust spectral compressed sensing via structured matrix completion J.IEEETransactions on Information Theory,2011,59:2182-2195.23 Cai J F,Qu X,Xu W,et al.Robust recovery of complex exponential signals from randomGaussian projections via low rank Hankel matrix reconstruction J.Applied&ComputationalHarmonic Analysis,2016,41:470-490.24 Fazel M,Pong T K,Sun D,et al.Hankel matrix rank minimization with applications to systemidentification and realization J.SIAM Journal on Matria 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 Cai J F,Wang T,Wei K.Fast and provable algorithms for spectrally sparse signal reconstructionvia low-rank Hankel matrix completion J.Applied&Computational Harmonic Analysis,2019:S1063520317300295.27 Cai J F,Wang T,Wei K.Spectral compressed sensing via projected gradient descent J.SIAMJournal on Optimization,2018,28(3):2625-2653.28 Chen Y X,Chi Y J.Robust spectral compressed sensing via structured matrix completion J.IEEE Transactions on Information Theory,2014,60(10):6576-6600.29 Luk F T,Qiao S.A fast singular value algorithm for Hankel matrices J.Contemporary Math-ematics,2003.30 Xu W,Qiao S.A fast SVD algorithm for square Hankel matrices J.Linear Algebra and ItsApplications,2008,428(2):550-563.31 Golub G H,VanLoan C F.Matric Computations M.Baltimore:The Johns Hopkins UniversityPress,1996.32 Van Loan C.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 forIndustrial and Applied Mathematics,Philadelphia:University City Science