低秩Toeplitz张量的高精度随机填充算法.pdf

第 43 卷第 3 期2023 年 9 月数学理论与应用MATHEMATICAL THEORY AND APPLICATIONSVol.43No.3Sep.2023低秩 Toeplitz 张量的高精度随机填充算法温瑞萍*李文韦(太原师范学院数学与统计学院,晋中,030619)摘要本文基于高精度填充算法,考虑低秩 Toeplitz 张量填充问题的求解,通过在每步迭代中将张量随机地按第 n 模展开并且对它的奇异值分解(Singular Value Decomposition,简记作 SVD)进行修正,给出一种具有随机思想的高精度填充算法,并讨论其收敛性.通过对 Toeplitz 张量及 Toeplitz 均值张量的数值实验,结果表明新算法比低秩 Toeplitz 张量的高精度填充算法在计算代价上有明显改进.关键词张量填充低秩 Toeplitz 张量随机算法Highaccuracy Randomized Completion Algorithm for theLow Rank Toeplitz TensorWen RuipingLi Wenwei(College of Mathematics and Statistics,Taiyuan Normal University,Jinzhong 030619,China)AbstractIn this paper,we consider the solution for the completion problem of low rank Toeplitz tensors,and basedonthehighaccuracycompletionalgorithm,presentahighaccuracycompletionalgorithmwithrandomizedtechnique,in which the nmode tensor is stochastically unfolded and the corresponding singular value decomposition(SVD)ismodified in each iteration.Moreover,the convergence of the new algorithm is established.The results of numericalexperiments on the Toeplitz tensor and the Toeplitz mean tensor show that the new algorithm is significantly betterthan the highaccuracy completion algorithm for low rank Toeplitz tensors in terms of computational cost.Key wordsTensor completionLow rank toeplitz tensorRandomized algorithmdoi:10.3969/j.issn.10068074.2023.03.0051引言由于张量在多模态结构信息表中具有优势,所以对张量的研究成为近些年来的热点问题.一个已经引起学界高度关注的现象是:在张量数据的采集、存储、传输与处理等环节,常常会发生数据的丢失或腐蚀,因此张量数据的填充与恢复问题的研究就尤为重要.低秩张量填充问题作为低秩矩阵填充问题的推广,主要是根据已知的部分张量数据信息来填充其未知或缺失的数据.张量填充方山西省回国留学人员科研项目(No.2022169),山西省科技创新人才团队重点项目(No.202204051002018),智能优化计算与区块链技术山西省重点实验室建设项目资助通信作者:温瑞萍(1965 ),教授,从事矩阵数据分析与科学计算研究 Email:收稿日期:2023 年 6 月 1 日96数学理论与应用法已经广泛应用于图像处理1、数据挖掘2、信号处理3及机器学习4等领域.低秩张量填充的数学模型一般为:minTrank(T),s.t.P(T)=P(C),(1.1)其中,C RI1I2In为待填充张量,T RI1I2In为 C 的低秩逼近张量,为基数为 m 的采样元素指标集,P()为相应张量在指标集 上的正交投影,即P(T)=C(i1i2.iN),当(i1,i2,iN),0,当(i1,i2,iN)/.类似于矩阵填充的秩极小化模型,问题(1.1)属于非凸优化模型,是 NP 难问题.如果待填充张量 C的秩已知或容易估计,一些学者提出了类似于求解矩阵填充秩极小化模型的解法,但填充效果不甚理想.因而,在实际处理中,通常用逼近张量 T 的一个最紧凸包 T 来代替 rank(T),将问题(1.1)转化为下列凸优化模型,即张量填充的核范数极小化数学模型:minTT,s.t.P(T)=P(C),(1.2)其中 表示相应张量的核范数.求解(1.2)通常的作法是将张量按照不同的模展开成矩阵,对矩阵进行填充操作后再折叠复原回张量形式.针对矩阵填充的核范数极小化问题求解,常见的经典算法有:Toh 等学者提出的加速近端梯度(APG)算法5 Cai 等提出的奇异值阈值(SVT)算法6 Lin 等提出的增广拉格朗日乘子(ALM)算法等7.因为张量的分解方式有 CP 分解、Tucker 分解、张量链分解、张量环分解和 tSVD 分解等8,所以张量填充问题的求解要比矩阵填充问题的求解复杂得多.根据各种分解,许多学者提出了求解问题(1.2)的有效方法.比如,Kolda 等提出了高阶 SVD 算法9.Gandy 等提出了采用 ADM 的框架求解低秩稀疏张量恢复问题10.Liu 等基于 Tucker 分解提出了三种张量填充方法11:利用松弛技术,采用块坐标下降(BCD)方法求全局最优解的简单低秩张量填充算法(SiLRTC)将原非光滑问题转化为光滑问题,进而求解张量迹范数极小化问题的快速低秩张量填充算法(FaLRTC)在 SiLRTC 算法的基础上应用交替方向乘子方法的高精度低秩张量填充算法(HaLRTC).由于待填充矩阵往往具有特殊结构,Toeplitz 矩阵填充问题近年来受到许多学者的关注.比如,王川龙等提出了 Toeplitz 矩阵填充的均值算法12、修正的增广拉格朗日乘子算法13、保结构算法14、子空间算法15等.温瑞萍等提出了求解 Toeplitz 矩阵填充问题的逐步结构化增广拉格朗日乘子算法16、l 步结构化增广拉格朗日乘子算法17、均值修正增广拉格朗日乘子算法18及尾端修正增广拉格朗日乘子算法19.同样地,在张量填充的某些应用问题中,虽然待填充数据表的规模很大,但是填充问题本身往往具有对称,Hankel 及 Toeplitz 等特殊结构,因而,结构化张量的填充和恢复在实际问题中的应用是很有意义且非常必要的.诸如,Badeac 等针对 Hankel 张量、对称张量、Toeplitz 张量填充问题分别提出了奇异值分解快速算法20 聂家旺等学者讨论了 Hankel 张量分解和秩,证明了 Hankel 张量的 CP 秩、对称秩及 Vandermonde 秩的一致性21 王川龙等提出了一种快速且具有较高精度的 Hankel 张量填充算法22.低秩 Toeplitz 张量的高精度随机填充算法97本文采用 HaLRTC 算法11求解 Toeplitz 张量填充问题,即当(1.2)中的待填充张量 C 恰好具有 Toeplitz 结构时的情形.由于 HaLRTC 算法在 N 次迭代的每一步均包括了需要较大计算花费的奇异值分解(SVD),本研究主要从以下两个方面改进它以降低其每次迭代中计算奇异值分解的代价:一方面是利用具有特殊结构的 Toeplitz 张量的快速奇异值分解方法,缩减奇异值分解的时间另一方面是应用随机化思想,将在每一步迭代需按全部模展开 Toeplitz 张量的操作改进为按第 n模随机展开一次,减少奇异值分解的次数,从而达到提高算法效率的目的.最后通过数值实验验证改进算法的有效性.2预备知识设 RI1I2表示规模为 I1 I2的实矩阵集.对任意两个实矩阵 X=(xij),Y=(yij)RI1I2,其内积定义为 X,Y =tr(XTY)=i,jxijyij,矩阵的核范数 X和 F范数 XF分别定义为 X=rk=1k(X),其中,k(X)是矩阵 X Rmn的第 k 大奇异值 XF=tr(XX)12=(i,j=1x2ij)12.X RI1I2In表示 n 阶张量,它按第 n 模展开后的矩阵记为 Xn,X 的元素xi1,i2,in相应地映射为矩阵元素Xinj,其中 j=1+Nk=1,k=n(ik 1)Jk,Jk=k1m=1,m=nnm.张量 X 的展开运算定义为 unfoldn(X)=Xn RnnIn,其中 In=Nm=1,m=nnk,其逆运算定义为 foldn(Xn)=X.对任意两个实张量 X=(xi1i2in),Y=(yi1i2in)RI1I2In,其内积定义为 X,Y=i1,i2,inXi1i2inYi1i2in=i1,i2,inxi1i2inyi1i2inX 的F范数定义为 XF=(i1,i2,inx2i1i2in)12=X,X,X 的核范数定义为 X=Ni=1iXi,其中 Xi表示张量 X 按模 i 展开的矩阵核范数 X 的 Tucker 秩定义为rank(X)=(rank(X1),rank(X2),rank(Xn).定义 2.1(奇异值分解(SVD),23)如果秩为 r 的矩阵 A Rmn的全部非零奇异值依次为1 2 r 0,则 A 的奇异值分解定义为:A=UrVT,r=diag(1,2,.,r),其中 U=u1,u2,.,ur Rmr和 V=v1,v2,.,vr Rnr分别为矩阵 A 的前 r 个左、右奇异向量构成的列正交矩阵.定义 2.2(奇异值阈值算子,6)对于任意参数 k 0,奇异值阈值算子 D1k定义为:D1k(A):=UD1k(i,k)VT,D1k(i,k)=diag(i 1k+),其中 A=UrVT Rmn,i 1k+=i 1k,当 i 1k时,0,当 i 1k时.定义 2.3(Toeplitz 矩阵,12)形如T=t0t1tn2tn1t1t0tn3tn2.tn+2tn+3t0t1tn+1tn+2t1t0 Rnn的矩阵称为一个 n n 的 Toeplitz 矩阵.98数学理论与应用显然,T 由其第一行和第一列决定,共有 tn+1,tn+2,.,tn1至多 2n 1 个互异元素,它们分布于 T 的 2n 1 条对角线上.若用 l 表示 Toeplitz 矩阵对角线的指标,则有 l n+1,n+2,.,n 1.相应地,Toeplitz 矩阵填充问题的元素采样指标集 n+1,n+2,.,n 1.用 diag(T,l)表示 Toeplitz 矩阵 T 的第 l 条对角线元素构成的向量,则diag(P(T),l)=diag(T,l),l ,0,l/.定义 2.4(Toeplitz 均值结构化算子,12)对于任意矩阵 X=(xij)Rnn,Toeplitz 均值结构化算子 T 定义如下:T(X)=n1l=n+1alTl,其中,al=average(diag(P(X,l),l ,Tl=(tij)nn=1,i j=l,0,i j=l,l=n+1,.,n 1.可见,T(X)是由矩阵 X 派生的 Toeplitz 矩阵,即任意矩阵都可以通过结构化算子 T()转化为一个 Toeplitz 矩阵.定义 2.5(Toeplitz 张量,20)给定张量 X RI1I2In.若它满足性质:对一切的 i10,.,I1 1,i2 0,.,I2 1,in 0,.,In 1 及 k 0,.,min(I1 i1,I2i2,.,In in)1,有Ai1+k,i2+k,.,in+k=Ai1i2.in,则称 X 为 Toeplitz 张量.类似于矩阵的情形,将任意张量 X 进行 Toeplitz 结构化的运算表示为(X)=T.3Toeplitz 张量的填充算法本节将文献 11 给出的高精度低秩张量填充算法(算法 3.1)进行修改,应用于求解模型(1.2)中的待填充张量 C 恰好具有 Toeplitz 结构的低秩 Toeplitz 张量填充问题(算法 3.2).算法算法 3.1 高精度低秩张量填充算法高精度低秩张量填充算法(Highaccuracy Low Rank Tensor Completion Algorithm,HaLRTC)11初始化初始化:给定下标集合,参数,0,t,X0=P(C),Yi,0=0,k:=0;第第 1 步步:计算for i=1:N doUi,k,i,k,Vi,k=svd(Xi,k+1kYi,k),Mi,k+1=FoldiUi,kD1k(i,k)VTi,k,低秩 Toeplitz 张量的高精度随机填充算法99end for第第 2 步步:计算 Xk+1=1NP(Ni=1(Mi,k+11kYi,k)+P(C);第第 3 步步:若 Xk+1 XkF/XkF,则停止迭代,否则,转 第 4 步第第 4 步步:计算 Yi,k+1=Yi,k k(Mi,k+1 Xk+1),k+1=tk,k:=k+1,转 第 1 步.算法算法3.2高精度低秩张量随机填充算法高精度低秩张量随机填充算法(HighaccuracyLowRankTensorRandomCompletionAlgorithm,HaLRTRC)初始化初始化:给定下标集合,参数,0,t,X0=P(C),Yi,0=0,k:=0;第第 1 步步:随机生成一整数 i=randperm(N,1),并计算Ui,k,i,k,Vi,k=svd(Xi,k+1kYi,k),Mi,k+1=FoldiUi,kD1k(i,k)VTi,k;第第 2 步步:令 Ti,k+1=(Mi,k+1);第第 3 步步:计算 Xi,k+1=P(Ti,k+11kYi,k)+P(C);第第 4 步步:若 Xi,k+1 Xi,kF/Xi,kF,则停止迭代,否则,转 第 4 步第第 5 步步:计算 Yi,k+1=Yi,k k(Ti,k+1 Xi,k+1),k+1=tk,k=k+1,转 第 1 步.算法 3.1 与算法 3.2 的主要区别在于算法 3.2 利用张量结构的同时应用了随机思想.将算法3.1 的每步迭代中张量按每个 n 模展开修改为算法 3.2 中的张量随机地仅按某一 k 模展开一次.虽然算法的迭代步数和计算复杂度有所增加,但是避免了算法 3.1 每步迭代中 N 次展开后带来的奇异值分解计算量,进而体现出算法 3.2 在计算时间上具有优势.结构化张量不仅在数据传输和算法中能够减少存储空间,而且在算法中每次迭代均可保持 Toeplitz 结构.这一方面提高了迭代矩阵的精度,另一方面可以用快速算法进行结构化矩阵的奇异值分解.4收敛性分析引理 4.1由算法 3.2 产生的序列 Yi,k+1 是有界的.证明 令 B=k(Xi,k+1kYi,k Mi,k+1).首先证明 Yi,k和 Xi,k(k=1,2,)是 Toeplitz 张量.由算法 3.2 可知,Yi,0=0 和 Xi,0=0 是Toeplitz 张量.假设 Yi,k和 Xi,k是 Toeplitz 张量,则根据 Xi,k+1=P(Ti,k+11kYi,k)+P(C),Xi,k+1是 Toeplitz 张量.因此 Yi,k+1也是 Toeplitz 张量.由算法 3.2 的第 5 步可得Yi,k+1=Yi,k k(Ti,k+1 Xi,k+1)=Yi,k k(Ti,k+1 Xi,k+Xi,k Xi,k+1)=Yi,k k(Ti,k+1 Xi,k)k(Xi,k Xi,k+1).100数学理论与应用此外,k(Xi,k Xi,k+1)=kP(Xi,k Xi,k+1)=kP(Xi,k(Ti,k+11kYi,k)=kP(Xi,k(Mi,k+1)1kYi,k)=kP(Xi,k(Xi,k+1kYi,k1k(k(Xi,k1kYk Mi,k)+1kYi,k)=P(k(Xi,k1kYk Mi,k)=P(B).再由算法 3.2 的第 2 步可知Xi,k+1kYi,k=Ui,ki,kVTi,k+Ui,ki,kVTi,k,其中Ui,k和Vi,k是大于 1k的奇异值对应的奇异向量,Ui,k和Vi,k是小于等于 1k的奇异值对应的奇异向量,i,k和i,k的对角元素分别大于 1k和小于等于 1k,故 Mi,k+1=Ui,k(i,k 1kI)VTi,k.由 F范数的性质,有BF=k(Xi,k1kYi,k Mi,k+1)F=k(Ui,ki,kVTi,k+Ui,ki,kVTi,kUi,k(i,k 1kI)VTi,k)F=k(1kUi,kVTi,k+Ui,ki,kVTi,k)Fn.再由文献 7 中引理 1 和引理 4 可得 Yi,k+1=Yi,k k(Ti,k+1 Xi,k+1)Ti,k+1.令 Ti,k+1=UVT.再由文献 6 可知Ti,k+1=UVT+W:W Rmn,VTW=0,WV=0,W2 1,UVT+W2F=tr(UVT+W)T(UVT+W)=tr(VVT+WWT)n.因此,Yi,k+1 k(Ti,k+1 Xi,k+1)Fn,P(B)F(B)F BFn,所以序列 Yi,k+1 是有界的.定理 4.1如果 k 且k=11k=+,则序列 Ti,k+1,Xi,k+1 收敛于(1.2)的最优解.证明 由于 1k(Yi,k+1Yi,k)=(Ti,k+1Xi,k+1),由引理 4.1 知(Yi,k+1Yi,k+1)是有界的,所以limk1k(Yi,k+1 Yi,k+1)=limk(Ti,k+1 Xi,k+1)=0.低秩 Toeplitz 张量的高精度随机填充算法101令(T,X)为问题(1.2)的最优解,Y是文献 7 中的对偶问题的最优解.我们首先证明Xi,k+1 X2F+rho2kYi,k+1 Y2F=Xi,k X2F+2kYi,k Y2F(Xi,k+1 Xi,k2F+2kYi,k+1 Yi,k2F)21kTi,k+1 T,Yi,k+1 Y,(4.1)其中Yi,k+1=Yi,k k(Ti,k+1 Xi,k+1).事实上,由于 Xi,k+1,Ti,k+1,Yi,k+1(k=1,2,)是 Toeplitz 张量,我们有Xi,k+1 X2F+2kYi,k+1 Y2F=Xi,k X2F+2kYi,k Y2F(Xi,k+1 Xi,k2F+2kYi,k+1 Yi,k2F)2Xi,k+1 X,Xi,k+1 Xi,k+22kYi,k+1 Y,Yi,k+1 Yi,k=Xi,k X2F+2kYi,k Y2F(Xi,k+1 Xi,k2F+2kYi,k+1 Yi,k2F)2Xi,k+1 X,Xi,k+1 Xi,k+21kYi,k+1 Y,Xi,k+1 Ti,k=Xi,k X2F+2kYi,k Y2F(Xi,k+1 Xi,k2F+2kYi,k+1 Yi,k2F)2Xi,k+1 X,Xi,k+1 Xi,k+21kYi,k+1 Y,Xi,k+1 X+21kYi,k+1 Y,T Ti,k+1=Xi,k X2F+2kYi,k Y2F(Xi,k+1 Xi,k2F+2kYi,k+1 Yi,k2F)21kTi,k+1 T,Yi,k+1 Y,所以(4.1)式成立.再由Yi,k+1 Ti,k+1,Ti,k+1 T,Yi,k+1 Y 0,可得k=1Ti,k+1 T,Yi,k+1Y +,且 Xi,k+1 X2F+2kYi,k+1 Y2F是非递增的.由算法 3.2 可知Yi,k+1,Xi,k+1 X=0,Y,Xi,k+1 X=0.类似于文献 7 中定理 2 的证明即可得 T是(1.2)的最优解.根据文献 20,可得下列平凡的结论.定理 4.2设 M RI1I2In,(M)是 Toeplitz 张量.则对于任意的 Toeplitz 张量 Y,有M (M),Y=0.定理 4.3设 Ti,k+1是在算法 3.2 中由 Mi,k+1所生成的 Toeplitz 张量.则有Ti,k+1 TF Mi,k+1 TF,其中 T是问题(1.2)的最优解.102数学理论与应用证明 由于Mi,k+1 TF=Mi,k+1 Ti,k+1+Ti,k+1 TF=Mi,k+1 Ti,k+12F+Ti,k+1 T2F+2Mi,k+1 Ti,k+1,Ti,k+1 T=Mi,k+1 Ti,k+12F+Ti,k+1 T2F,因此,Ti,k+1 TF Mi,k+1 TF.5数值实验本节通过数值实验验证算法3.1与算法3.2的有效性.实验包括两个部分:分别利用THaLRTC与 THaLRTRC 算法求解 Toeplitz 张量填充问题及分别利用 MTHaLTRC 与 MTHaLRTRC 算法求解 Toeplitz 均值张量填充问题.所有数值实验均在戴尔(DELL)PowerEdge R740 xd 高性能 2U 机架式并行计算服务器上,MATLAB(R2019b)环境下运行实现.从算法的迭代步数、CUP 总的计算时间(单位:秒(s)及精度三个方面进行比较.在实验中,p 表示采样率,参数 i=1n,0=107,其余参数均采用文献 11 的建议.另外,利用随机方法生成秩不同且维数分别为 50 50 50,100 100 100,150 150 150,200200200,250250250 和 300300300 且秩为(10,10,10)的 Toeplitz 张量和 Toeplitz均值张量.5.1Toeplitz 张量两种算法在采样率分别为 0.6,0.5,0.4,0.3,0.2 时的实验结果分别见表 1 至表 5.下文中 X表示输出的 Toeplitz 张量,C 为原始的 Toeplitz 张量 加速比 SP 和相对误差 RSE 的计算式如下:SP=新算法运行的时间其它算法运行的时间,RSE=X CFCF.(5.1)包括 11 在内的文献中的数值实验,通常只针对 maxI1,I2,I3 小于或等于 100 的张量数据进行数值测试,而本文的数值实验规模达到了 I1=I2=I3=300.由表 1 至表 5 可知,在采样率p 0.2,0.3,0.4,0.5,0.6 时,THaLRTC 算法与算法 3.2 均收敛,两个算法都满足了规定的停止准则.虽然新算法 3.2 的迭代步数总是大于 THaLRTC 算法的迭代步数,但是由于嵌入 Toeplitz 结构化操作,使得精度提高,而且加入随机思想减少了奇异值分解的计算量,从而总的运行时间显著地缩短,新算法 3.2 比 THaLRTC 算法花费更少.特别是当张量的采样率较小而秩比较大的时候,算法 3.2 更彰显优势,其加速比高达约 50%.此外,两个算法的计算时间比较图(图 1)更加直观地体现了新算法的有效性,其中图 1(a),(b),(c),(d)分别显示在不同采样率下,THaLRTC 算法与 THaLRTRC 算法在不同维数且秩为(10,10,10)时对应的 CPU 耗时.从图 1 可知,THaLRTRC 算法的 CPU 时间显著少于 THaLRTC 算法的 CPU时间,表明 THaLRTRC 算法比 THaLRTC 算法在总计算代价方面更具有优势.低秩 Toeplitz 张量的高精度随机填充算法103表 1当 p=0.6 时,算法 THaLRTC 和 THaLRTRC 的比较I1 I2 I3秩算法迭代步数CPU 时间(s)RSEp=0.650 50 50(2,2,2)THaLRTC1720.97600.2399THaLRTRC1900.49220.239050 50 50(5,5,5)THaLRTC1690.99320.4805THaLRTRC1870.49300.479550 50 50(10,10,10)THaLRTC1681.73200.4821THaLRTRC1890.85680.4824100 100 100(10,10,10)THaLRTC1715.06250.3780THaLRTRC1822.75480.3761150 150 150(10,10,10)THaLRTC16814.39870.3240THaLRTRC1868.83090.3280200 200 200(10,10,10)THaLRTC16654.32040.2877THaLRTRC18030.67860.2865250 250 250(10,10,10)THaLRTC165110.25050.2653THaLRTRC17570.02060.2627300 300 300(10,10,10)THaLRTC163165.43980.2459THaLRTRC179111.11860.2467表 2当 p=0.5 时,算法 THaLRTC 和 THaLRTRC 的比较I1 I2 I3秩算法迭代步数CPU 时间(s)RSEp=0.550 50 50(2,2,2)THaLRTC1730.99390.2249THaLRTRC1930.49320.226550 50 50(5,5,5)THaLRTC1690.99320.4805THaLRTRC1870.48260.463150 50 50(10,10,10)THaLRTC1741.71870.4904THaLRTRC1880.88560.4624100 100 100(10,10,10)THaLRTC1634.70560.3650THaLRTRC1822.73840.3638150 150 150(10,10,10)THaLRTC16613.73200.3150THaLRTRC1798.28180.3137200 200 200(10,10,10)THaLRTC16251.63910.2775THaLRTRC17930.14620.2761250 250 250(10,10,10)THaLRTC164104.54330.2578THaLRTRC17662.74960.2561300 300 300(10,10,10)THaLRTC158168.05220.2360THaLRTRC17595.40950.2339104数学理论与应用表 3当 p=0.4 时,算法 THaLRTC 和 THaLRTRC 的比较I1 I2 I3秩算法迭代步数CPU 时间(s)RSEp=0.450 50 50(2,2,2)THaLRTC1740.98170.2154THaLRTRC1920.46290.215550 50 50(5,5,5)THaLRTC1610.93940.4539THaLRTRC1900.48090.452750 50 50(10,10,10)THaLRTC1701.60120.4484THaLRTRC1920.84290.4490100 100 100(10,10,10)THaLRTC1504.30450.3504THaLRTRC1842.73810.3497150 150 150(10,10,10)THaLRTC15512.61310.3024THaLRTRC1798.19060.3016200 200 200(10,10,10)THaLRTC15445.88630.2693THaLRTRC18126.75860.2691250 250 250(10,10,10)THaLRTC15181.33600.2460THaLRTRC18248.82520.2478300 300 300(10,10,10)THaLRTC155156.77130.2299THaLRTRC177104.96790.2296表 4当 p=0.3 时,算法 THaLRTC 和 THaLRTRC 的比较I1 I2 I3秩算法迭代步数CPU 时间(s)RSEp=0.350 50 50(2,2,2)THaLRTC1650.91520.2038THaLRTRC1920.44520.203950 50 50(5,5,5)THaLRTC1570.88210.4466THaLRTRC1910.44590.443750 50 50(10,10,10)THaLRTC1591.55140.4525THaLRTRC1900.86200.4486100 100 100(10,10,10)THaLRTC1514.28470.3423THaLRTRC1852.69980.3417150 150 150(10,10,10)THaLRTC14812.13000.2904THaLRTRC1827.67620.2903200 200 200(10,10,10)THaLRTC14343.87990.1817THaLRTRC17528.22240.8491250 250 250(10,10,10)THaLRTC14375.66780.2353THaLRTRC17544.95130.2345300 300 300(10,10,10)THaLRTC141137.19680.2185THaLRTRC17581.37070.2178低秩 Toeplitz 张量的高精度随机填充算法105表 5当 p=0.2 时,算法 THaLRTC 和 THaLRTRC 的比较I1 I2 I3秩算法迭代步数CPU 时间(s)RSEp=0.250 50 50(2,2,2)THaLRTC1730.89700.2479THaLRTRC1960.39320.435850 50 50(5,5,5)THaLRTC1690.86670.5197THaLRTRC1940.38760.620050 50 50(10,10,10)THaLRTC1711.74080.4904THaLRTRC1960.88850.6175100 100 100(10,10,10)THaLRTC1494.26630.3412THaLRTRC1862.73550.3369150 150 150(10,10,10)THaLRTC14812.33210.2874THaLRTRC1818.11130.2867200 200 200(10,10,10)THaLRTC14342.02800.2500THaLRTRC17424.53090.2596250 250 250(10,10,10)THaLRTC14281.87610.2252THaLRTRC17945.16810.2249300 300 300(10,10,10)THaLRTC138123.92870.2105THaLRTRC18082.11730.2115(a)p=0.5(b)p=0.4(c)p=0.3(d)p=0.2图 1不同采样率下 THaLRTC 算法与 THaLRTRC 算法时间的比较106数学理论与应用5.2Toeplitz 均值张量本小节针对 Toeplitz 均值张量,在采样率分别为 0.5,0.4,0.3,0.2 时对两种算法进行比较,实验结果见表 6 至表 9.本小节针对 Toeplitz 均值张量也进行了大量的数值实验.同 5.1 节的情形,实验规模达到了 I1=I2=I3=300.从表 6 至表 9 可以看出,在采样率 p 0.2,0.3,0.4,0.5 时,MTHaLRTC 算法与本文的新算法 3.2 均收敛,均达到了规定的停止准则.这表明两种数值算法都具有较好的稳定性.虽然增加了随机思想的算法 3.2 的迭代步数总是大于 MTHaLRTC 算法的迭代步数,但是在引入随机思想的同时嵌入了 Toeplitz 结构化操作,这不仅使得精度提高,而且降低了计算量,从而总的运行时间明显缩短,特别是当张量的采样率较小(这意味着原始的已知数据很少)而秩比较大的时候,优势更加显著,其加速比高达 50%.图 2 直观地体现了新算法的有效性,其中,(a),(b),(c),(d)分别显示了在不同采样率下,MTHaLRTC 算法与 MTHaLRTRC 算法在不同规模且秩为(10,10,10)时对应的 CPU 耗时.图 2 表明 MTHaLRTRC 算法比 MTHaLRTC 算法在总计算花费方面更具有优势.表 6当 p=0.5 时,算法 MTHaLRTC 和 MTHaLRTRC 的比较I1 I2 I3秩算法迭代步数CPU 时间(s)RSEp=0.550 50 50(2,2,2)MTHaLRTC1730.99320.0077MTHaLRTRC1840.46930.007650 50 50(5,5,5)MTHaLRTC1610.91590.0448MTHaLRTRC1910.49480.044850 50 50(10,10,10)MTHaLRTC1681.71140.0268MTHaLRTRC1880.88700.0268100 100 100(10,10,10)MTHaLTRC1624.51590.0079MTHaLRTRC1812.71670.0079150 150 150(10,10,10)MTHaLRTC15712.75450.0042MTHaLRTRC1777.84470.0042200 200 200(10,10,10)MTHaLRTC8528.47080.0027MTHaLRTRC17127.77120.0029250 250 250(10,10,10)MTHaLRTC8253.38750.0035MTHaLRTRC17266.10540.0037300 300 300(10,10,10)MTHaLRTC8088.62860.0035MTHaLRTRC171111.11720.0037低秩 Toeplitz 张量的高精度随机填充算法107表 7当 p=0.4 时,算法 MTHaLRTC 和 MTHaLRTRC 的比较I1 I2 I3秩算法迭代步数CPU 时间(s)RSEp=0.450 50 50(2,2,2)MTHaLRTC1730.98190.0076MTHaLRTRC1870.46930.007650 50 50(5,5,5)MTHaLRTC1610.90290.0444MTHaLRTRC1920.44970.038750 50 50(10,10,10)MTHaLRTC1721.74390.0267MTHaLRTRC1860.85900.0267100 100 100(10,10,10)MTHaLRTC1634.49850.0079MTHaLRTRC1822.66670.0079150 150 150(10,10,10)MTHaLRTC16212.62880.0042MTHaLRTRC1757.71800.0042200 200 200(10,10,10)MTHaLRTC16449.75540.0029MTHaLRTRC17525.83990.0029250 250 250(10,10,10)MTHaLRTC15499.41180.0037MTHaLRTRC17159.91920.0037300 300 300(10,10,10)MTHaLRTC150173.49490.0037MTHaLRTRC172103.99790.0037表 8当 p=0.3 时,算法 MTHaLRTC 和 MTHaLRTRC 的比较I1 I2 I3秩算法迭代步数CPU 时间(s)RSEp=0.350 50 50(2,2,2)MTHaLRTC1720.94320.0075MTHaLRTRC1900.44770.007550 50 50(5,5,5)MTHaLRTC1600.87860.0388MTHaLRTRC1920.44970.038750 50 50(10,10,10)MTHaLRTC1741.78200.0266MTHaLRTRC1880.87600.0266100 100 100(10,10,10)MTHaLRTC1634.57690.0079MTHaLRTRC1852.66420.0079150 150 150(10,10,10)MTHaLRTC16512.76290.0042MTHaLRTRC1777.76020.0042200 200 200(10,10,10)MTHaLRTC16449.67260.0029MTHaLRTRC17