Tailed-modification augmented Lagrange multiplier algorithm for Toeplitz matrix completion*
矩阵填充问题假设当目标矩阵具有低秩或近似低秩的特性时,其能够对含有大量缺失元素的矩阵进行近乎完美的填充.填充一个未知的低秩或近似低秩采样矩阵是一个具有挑战性的问题.目前,矩阵填充在机器学习[1-2]、推荐系统[3]、图像处理[4]、控制理论[5]和计算机视觉[6]等数据科学领域中都有非常重要的应用.
在 2009 年,Candès和 Recht[7]建立了关于矩阵填充问题的凸优化模型:
式中:D∈Rm×n是缺失部分元素的已知矩阵,A∈Rm×n是逼近目标矩阵D的未知矩阵,核范数
表示秩为r的矩阵A∈Rm×n的第k大奇异值,且σ1≥σ2≥…≥σk≥…≥σr>0.
对于求解问题(1),通常算法中的每次迭代都需要计算一个m×n阶矩阵的奇异值分解(singular value decomposition,SVD).近年来,基于核范数最小化的研究,有不少的成果.如文献[8]提出了一种易于实现的奇异值阈值算法(singular value thresholding,SVT),该算法可以得到具有低秩结构的最优解,并保证了填充矩阵的稀疏性,一定程度上节省了存储空间,可以有效地处理低秩的大规模矩阵填充问题.但当秩较大时,此算法收敛速度缓慢甚至效果不是很理想,在文献[9]给出了加速SVT算法.与此同时,Toh和Yun[10]提出了加速临近梯度算法(accelerated proximal gradient,APG);Lin 等[11]提出了比APG算法速度快、精度高的增广拉格朗日乘子算法(augmented lagrange multiplier,ALM),该算法具有很好的操作性和收敛性,并且需要较小的存储空间.
由以上算法结果报告,SVD计算花费占去整个算法花费的80%以上,而Toeplitz矩阵的SVD具有较低的算法复杂度,且一个n×n阶的Toeplitz矩阵T ∈ Rn×n表达形式为
那是由2n-1个元素决定的,即表达式(2)的第一行和第一列元素.近年来,针对Toeplitz矩阵填充问题,方云兰和郑慧娆[12]研究了Toeplitz块矩阵填充的快速正交三角分解算法;于益华和李云翔[13]研究了基于快速小波变换的Toeplitz矩阵填充算法;Wang 和 Li[14-16]提出了 Toeplitz矩阵填充的均值算法、修正的ALM算法、保结构算法[16];刘丽霞和王川龙[17]进一步提出了子空间算法;Wen 等[18]、Wen和Li[19]研究了逐步结构化的ALM算法以及l步结构化的ALM算法.
本文主要是基于均值的增广拉格朗日乘子算法(ALM based on mean value,MALM)算法,对中小型规模的低秩矩阵进行填充.为了减少MALM算法中频繁的数据传输量与结构化操作所增加的计算量,采用ALM算法,当迭代矩阵逐渐靠近目标矩阵时,开始对矩阵进行尾部修正并结构化,修正使迭代矩阵从数值上更加靠近目标矩阵,结构化使迭代矩阵与目标矩阵保持同样结构,可利用快速奇异值分解,从而减少迭代步数,缩短奇异值分解时间,节约算法的整体花费.同时给出了算法收敛性分析,并通过数值实验验证了算法的有效性.下面给出一些定义:
可见,Γ(A)是由矩阵A派生的Toeplitz矩阵.换句话说,∀A∈Rn×n,都可以通过结构化算子 Γ(·)转化为一个Toeplitz矩阵.
本文拟简单回顾ALM和MALM,并分别比较2种算法所具有的优缺点,介绍关于Toeplitz矩阵填充的尾端修正ALM算法(Tailed-modification ALM,l-TMALM);运用核范数的性质给出新算法的收敛性分析;通过与l-MALM,MALM以及ALM算法作比较得出新算法的有效性.
符号说明.为方便起见,Rm×n表示的是m×n阶的实数矩阵.矩阵A的核范数用‖A ‖ *表示,而‖A ‖ F表示矩阵A的Frobenius范数.AT表示矩阵A的转置.对于一个Toeplitz矩阵A ∈ Rn×n,diag(A ,l)表示矩阵A的第l条对角线元素,l=-n+1,…,n-1.Ω⊂{ - n+1,…,n-1}是采样集,PΩ是相应矩阵在Ω上的投影算子,满足
其中0是一个零向量.
低秩Toeplitz矩阵的填充问题.为了方便比较,先简单回顾ALM算法,并将其应用到Toeplitz矩阵填充问题中.
当问题(1)中的m=n时,即矩阵A,E,D ∈ Rn×n为Toeplitz矩阵时,求解式(1)的等价形式为
数值实验表明,ALM算法在理论和实际应用中均有较好的效果,且该算法迭代快,具有线性全局收敛速度,但奇异值分解时间较长,精度较低,收敛效果不是很理想.
对偶算法是为了通过其对偶性求解问题(4),即首先要解决的问题是
对于最优增广拉格朗日乘子Y,有最速上升算法的约束集为{Y}可以用来解决问题(6),其中被约束的最速上升方向是通过将D投影在凸的目标区域{Y}上而获得.结果表明在寻找被约束的最速上升方向的过程中可以得到原问题(4)的最优解.
填充Toeplitz矩阵的MALM,其思想是在ALM算法的基础上,将迭代矩阵的对角元素均值化后重新赋值,使其保持Toeplitz结构.问题表述为
数值实验表明,与ALM和SVT算法相比,MALM算法的精度较高,收敛效果较好,对于在迭代过程中进行结构化处理的MALM算法保持了Toeplitz矩阵的结构,从而可以利用快速奇异值分解,使得在奇异值分解时间上要远短于其他2种算法;但是相比ALM算法,MALM算法在均值步增加了数据的传输.而对于一些计算机来讲,数据传输频繁会造成数据堆积而拖延计算时间,因此,基于减少数据传输量的思考,在迭代的尾端,即接近目标矩阵时再进行结构化处理是增效的选择.
对矩阵利用ALM算法[11]的快速迭代l步之后,进行尾部修正及结构化处理.一方面,避免了均值步产生的频繁数据传输;另一方面,尾部修正使得迭代矩阵更加靠近目标矩阵,从而快速达到可行解,减少奇异值分解时间.算法步骤如下:
第1阶段:ALM算法步.
第1步:给定下标集合Ω,样本Toeplitz矩阵D,参数 ρ> 1,μ0> 0,以及初始矩阵 Y0,0=O,E0,0=O,k:=0,q=1,2,···,l-1.
该算法分为2个阶段执行:第1阶段,使用ALM算法,利用ALM算法本身迭代速度快的性质,当其迭代到一定程度,即迭代矩阵逐渐靠近目标矩阵时;进入第2阶段,对迭代矩阵序列进行尾部修正并结构化,结构化使迭代矩阵与目标矩阵保持同样结构,从而可利用快速奇异值分解,修正使迭代矩阵从数值上更加逼近目标矩阵,以便快速地达到可行解.该算法不仅减少了频繁的数据传输量,而且在一定程度上节省了奇异值分解时间.
通过数值实验比较了 l-TMALM、l-MALM[19]、MALM[15]以及 ALM 算法[11],所有的数值实验均在相同工作环境中完成.实验中,通过对迭代步数(IT)、计算时间(time,单位为 s)、收敛误差 1和 2(E1,E2)的分析和比较,表明l-TMALM算法无论在迭代步数上还是在奇异值的分解时间上,明显优于其他3种算法.E1和E2的计算式分别为
在数值实验中,M ∈Rn×n是Toeplitz矩阵(M是原始矩阵).在l-TMALM算法中,选取参数μ=
Ω是目标集,其他3种算法参数的选取与l-TMALM算法一致.
选取的样本矩阵阶数为m=n∈{800,1500,2 000,3000,4 000},经过多次数据实验得出当第1阶段迭代步数l=6时,计算出的总迭代时间以及误差均可达到最小,所以第1阶段ALM算法步中的迭代步数l取值为6,采样率为p∈{0 .6,0.5,0.4} ,样本矩阵的秩为10.
4种算法的数值实验结果列于表1,4种算法均可成功地计算出满足规定停止准则的迭代矩阵.且l-TMALM算法在保证迭代步数和奇异值分解时间上均优于l-MALM,MALM以及ALM算法的情况下,其迭代矩阵与原始矩阵的逼近程度最好,即E2最小,收敛效果最好.同一采样率下,4种算法的时间比较如图1所示.表明同一矩阵阶数下,l-TMALM算法所用计算时间最短.
表1 不同采样率时4种算法比较
注:ALM为增广拉格朗日乘子;MALM为基于均值的增广拉格朗日乘子;l-MALM为l步修正的增广拉格朗日乘子;l-TMALM为Toeplitz矩阵填充的尾端修正的增广拉格朗日乘子.
p=0.6 p=0.5 p=0.4算法收敛误差2 0.0 1 4 4 0.0 0 6 2 0.0 0 1 5 0.0 0 3 5 0.0 0 2 2 1.5 8 7 5×1 0-7 1.2 4 7 5×1 0-6 1.7 3 1 0×1 0-7 5.2 5 6 5×1 0-8 9.4 1 0 1×1 0-8 1.5 6 1 4×1 0-7 1.2 3 0 4×1 0-6 1.7 2 2 4×1 0-7 5.3 2 6 1×1 0-8 1.1 0 2 8×1 0-7 7.2 8 7 3×1 0-8 3.2 5 5 0×1 0-7 6.1 8 0 5×1 0-8 2.7 6 4 1×1 0-9 6.0 4 2 1×1 0-9矩阵阶数/1 0 2收敛误差2 0.0 1 2 3 0.0 0 2 6 7.9 6 0 6×1 0-4 0.0 0 2 0 6.8 4 2 8×1 0-4 2.3 1 1 0×1 0-7 5.6 1 6 3×1 0-7 2.7 6 6 2×1 0-8 8.1 0 6 5×1 0-8 7.0 1 5 5×1 0-8 2.6 9 8 2×1 0-7 5.3 5 3 4×1 0-7 2.6 0 4 5×1 0-8 6.8 4 9 4×1 0-8 5.0 3 6 9×1 0-8 2.3 1 3 1×1 0-8 1.5 4 4 3×1 0-8 1.8 9 8 3×1 0-9 2.6 5 8 2×1 0-8 2.5 7 3 1×1 0-9迭代步数7 0 4 7 5 1 0 2 3 2 8 1 4 0 7 3 3 2 1 9 5 1 7 7 1 6 2 6 7 2 7 6 9 4 1 4 7 1 6 2 5 5 1 7 5 7 0 8 6 8 5计算时间/s 2 0.2 0 2 5 2 4 9.8 5 1 2 5 8.5 5 2 5 5 6 4.2 9 6 7 2 9 2.1 5 0 6 9.5 2 0 0 1 1 5.2 5 6 3 6 0.7 9 0 0 2 1 7.4 5 3 6 3 3 6.0 1 3 0 8.2 6 6 0 9 9.5 2 9 8 5 8.8 3 5 1 1 7 7.0 2 8 9 3 3 2.0 3 7 9 7.8 8 9 3 8 7.4 2 3 8 5 1.8 2 9 1 1 3 8.4 6 7 0 2 7 7.8 3 5 4计算时间/s 2 0.3 5 1 8 3 9 0.5 8 8 1 6 5.3 7 6 2 6 1 7.9 8 2 9 4 0 3.1 3 6 3 2 0.3 6 1 7 1 2 9.4 2 8 3 9 9.1 7 9 7 2 6 4.6 7 5 7 5 6 7.6 8 4 3 1 9.8 6 9 0 1 2 2.9 5 4 7 9 4.5 2 2 3 2 2 6.1 0 4 0 5 5 7.2 3 0 7 1 3.0 9 1 6 6 5.3 7 7 1 6 5.1 0 0 7 1 8 0.6 2 4 9 3 6 0.3 9 7 7迭代步数7 4 4 5 5 1 1 0 3 2 0 1 8 4 1 2 5 2 9 4 1 6 9 1 9 5 2 6 0 1 2 7 2 7 3 1 6 6 1 7 0 2 5 7 6 7 1 1 6 8 3 1 0 2 1 0 8收敛误差2 0.0 1 7 0 0.0 0 3 1 0.0 0 1 3 0.0 0 3 4 0.0 0 3 1 1.4 8 1 2×1 0-5 2.0 6 8 4×1 0-7 9.9 0 1 5×1 0-7 2.0 0 4 4×1 0-7 4.8 9 6 1×1 0-7 1.5 1 1 4×1 0-5 1.9 6 4 1×1 0-7 9.8 0 5 3×1 0-7 1.4 1 0 8×1 0-7 4.8 4 3 3×1 0-7 7.6 9 1 7×1 0-6 7.9 9 6 6×1 0-9 4.0 1 1 0×1 0-7 1.7 0 4 7×1 0-8 3.5 1 5 7×1 0-8 A L M 8 M A L M l-M A L M l-T M A L M 1 5 2 0 3 0 4 0 8 1 5 2 0 3 0 4 0 8 1 5 2 0 3 0 4 0 8 1 5 2 0 3 0 4 0迭代步数7 1 4 6 4 1 5 3 3 5 0 1 6 5 9 2 4 7 8 2 4 3 2 4 0 1 8 7 9 0 4 6 1 2 4 2 1 7 4 1 8 3 5 7 3 1 2 1 0 1 9 7 9 5计算时间/s 1 8.1 2 8 3 3 0 0.0 4 9 1 1 3 0.8 4 0 4 1 0 2 4.5 0 0 0 3 5 8.8 2 9 0 1 3.5 9 5 3 2 2 3.3 9 1 3 1 6 6.2 7 0 5 3 2 5.5 5 4 3 4 1 5.6 3 5 1 1 3.0 0 8 3 2 8 8.6 7 2 6 1 6 1.3 4 5 5 2 3 3.5 6 6 5 3 9 4.2 0 1 6 1 0.5 4 9 0 2 0 7.4 5 6 6 9 1.7 8 1 6 1 8 1.0 7 9 7 3 2 2.6 0 9 0
图1 不同采样率时4种算法时间比较(a)p=0.4;(b)p=0.5;(c)p=0.6
对于Toeplitz矩阵填充问题,本文基于MALM提出了一种l-TMALM算法.算法通过尾部修正再结构化,加速迭代矩阵与目标矩阵的逼近过程,以便快速地达到可行解,较大程度地缩短迭代步数;结构化使迭代矩阵与目标矩阵保持原有的Toeplitz结构,从而可利用快速奇异值分解缩短算法运行时间,降低计算代价.因此,新算法不仅克服了原始ALM算法较长的奇异值分解时间,也避免了MALM算法额外的数据传输量;此外,新算法的收敛效果要优于l-MALM,MALM以及ALM算法.基于新算法的合理性和有效性,建立了与之相对应的收敛性理论.理论分析和数值结果表明,l-TMALM算法是求解矩阵填充问题的一种有效算法.另外,未来拟将研究推广到高维的张量填充问题,比如将其修正的思想进一步推广到张量填充问题,从而求解出对于具有Toeplitz结构矩阵的张量填充算法.
[1]史劲.人工智能领域的机器学习算法研究[J].中国新通信,2021,23(24):48-49.
[2] ARGYRIOU A,EVGENIOU T,PONTIL M.Multi-task feature learning[J].Advances in Neural Information Processing Systems,2007,19:41-48.
[3]潘伟.矩阵填充在推荐系统中的应用研究[D].赣州:江西理工大学,2021.
[4]BERTALMIO M,SAPIRO G,CASELLES V,et al.Multi-task feature learing,image inpainting[J].Computer Graphics,2000,34:417-424.
[5]MESBAHI M,PAPAVASSILOPOULOS G P.On the rank minimization problem over a positive semidefinite linear matrix inequality[J].IEEE Transactions on Automatic Control,1997,42(2):239-243.
[6] TOMASI C,KANADE T.Shape and motion from image streams under orthography:a factorization method[J].International Journal of Computer Vision,1992,9(2):137-154.
[7] CANDÈS E J,RECHT B.Exact matrix completion via convex optimization[J].Foundations of Computational Mathematics,2009,9(6):717-772.
[8] CAI J F,CANDÈS E J,SHEN Z W.A singular value thresholding method for matrix completion[J].Society for Industrial and Applied Mathematics Journal of Optimization,2010,20(4):1956-1982.
[9] LI W,HU J,CHEN C.On accelerated singular value thresholding algorithm for matrix completion [J].Applied Mathematics,2014,5(21):3445-3451.
[10]TOH K C,YUN S.An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems[J].Pacific Journal of Optimization,2010,6(3):615-640.
[11]LIN Z,CHEN M,MA Y.The augmented lagrange multiplier method for exact recovery of corrupted lowrank matrices[R/OL].(2010-09-26)[2021-03-02].http://arxiv.org/abs/1009.5055.
[12]方云兰,郑慧娆.TOEPLITZ-块矩阵的快速QR分解算法及其并行实现[J].武汉大学学报(自然科学版),1995,41(3):287-293.
[13]于益华,李云翔.Toeplitz矩阵的快速小波变换与性能分析[J].湖南城市学院学报(自然科学版),2004,13(2):37-40.
[14] WANG C L,LI C.A mean value algorithm for Toeplitz matrix completion[J].Applied Mathematics Letters,2015,41:35-40
[15]WANG C L,LI C,WANG J.A modified augmented larange multiplier algorithm for toeplitz matrix completion[J].Advances in Computational Mathematics,2016,42:1209-1224.
[16]王川龙,李超.Toeplitz矩阵填充的保结构算法[J].中国科学(数学),2016,46:1-16.
[17]刘丽霞,王川龙.基于均值的Toeplitz矩阵填充的子空间算法[J].计算数学,2017,39(2):179-188.
[18] WEN R P,LI S Z,ZHOU F.Toeplitz matrix completion via smoothing augmented Lagrange multiplier algorithm[J].Applied Mathematics and Computation,2019,355:299-310.
[19]WEN R P,LI S Z.Anl-step modified augmented lagrange multiplier algorithm for completing a Toeplitz matrix[J].Applied Mathematics and Computation,2019,32(4):887-899.
[20]GOLUB G H,VAN LOAN C F.Matrix computations[M].4th ed.Baltimore:the Johns Hopkins University Press,1996,47:392-396.
[21]CHEN M M,GANESH A,LIN Z C,et al.Fast convex optimization algorithms for exact recovery of a corrupted low-rank matrix [J].Marine Biological Association of the UK,2009,56(3):707-722.
[22]温瑞萍,王俊霞.应用矩阵分析[M].太原:山西人民出版社,2018:177-179.