DOI:10.19789/j.1004-9398.2022.05.002

文献引用:肖云,温瑞萍.Toeplitz矩阵填充的尾端修正增广拉格朗日乘子算法[J].首都师范大学学报(自然科学版),2022,43(5):8-15.XIAO Y,WEN R P.Tailed-modification augmented Lagrange multiplier algorithm for Toeplitz matrix completion[J].Journal of Capital Normal University(Natural Science Edition),2022,43(5):8-15.

Toeplitz矩阵填充的尾端修正增广拉格朗日乘子算法*

肖 云,温瑞萍**

(太原师范学院工程科学计算山西省高等学校重点实验室,山西晋中 030619)

摘要:基于均值的增广拉格朗日乘子(MALM)算法,提出了一种尾端修正的Toeplitz矩阵填充新算法.该算法利用增广拉格朗日乘子(ALM)算法迭代速度较快的优点,对迭代矩阵序列进行结构化与尾端修正.在一定程度上减少了每步均值处理所产生的数据传输量,从而降低了计算代价.同时详细讨论了新算法的收敛性.最后通过数值实验证明了新算法比l步修正的增广垃格朗日乘子(l-MALM)、MALM以及ALM算法在计算时间上有较大程度的减少.

关键词:Toeplitz矩阵;增广拉格朗日乘子算法;均值;矩阵填充

Tailed-modification augmented Lagrange multiplier algorithm for Toeplitz matrix completion*

XIAO Yun,WEN Ruiping**
(Key Laboratory for Engineering&Computing Science,Shanxi Provincial Department of Education,Taiyuan Normal University,Jinzhong Shanxi 030619)

Abstract:Based on the mean augmented Lagrange multiplier(MALM)algorithm,a tail modified Toeplitz matrix completion algorithm is proposed.The algorithm uses the advantage of the augmented Lagrange multiplier(ALM)algorithm to structure and modify the iteration matrix sequence.To some extent,the data transmission generated by each step of mean processing is reduced,and thus reduces the computational cost.The convergence of the new algorithm is discussed in detail.Finally,the numerical experiments show that the new algorithm has a greater reduction in computing time than l-MALM,MALM and ALM algorithm.

Keywords:Toeplitz matrix;augmented Lagrange multiplier algorithm;mean value;matrix completion

CLC:O241.6

中图分类号:O241.6

收稿日期:2021-05-17

*国家自然科学基金项目(11371275);山西省自然科学基金项目(201901D211423)

**通信作者:wenrp@163.com

0 引 言

矩阵填充问题假设当目标矩阵具有低秩或近似低秩的特性时,其能够对含有大量缺失元素的矩阵进行近乎完美的填充.填充一个未知的低秩或近似低秩采样矩阵是一个具有挑战性的问题.目前,矩阵填充在机器学习[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是一个零向量.

1 相关算法

低秩Toeplitz矩阵的填充问题.为了方便比较,先简单回顾ALM算法,并将其应用到Toeplitz矩阵填充问题中.

1.1 ALM[11]

当问题(1)中的m=n时,即矩阵A,E,D ∈ Rn×n为Toeplitz矩阵时,求解式(1)的等价形式为

数值实验表明,ALM算法在理论和实际应用中均有较好的效果,且该算法迭代快,具有线性全局收敛速度,但奇异值分解时间较长,精度较低,收敛效果不是很理想.

1.2 对偶算法(dual algorithm)[21]

对偶算法是为了通过其对偶性求解问题(4),即首先要解决的问题是

对于最优增广拉格朗日乘子Y,有最速上升算法的约束集为{Y}可以用来解决问题(6),其中被约束的最速上升方向是通过将D投影在凸的目标区域{Y}上而获得.结果表明在寻找被约束的最速上升方向的过程中可以得到原问题(4)的最优解.

1.3 MALM[15]

填充Toeplitz矩阵的MALM,其思想是在ALM算法的基础上,将迭代矩阵的对角元素均值化后重新赋值,使其保持Toeplitz结构.问题表述为

数值实验表明,与ALM和SVT算法相比,MALM算法的精度较高,收敛效果较好,对于在迭代过程中进行结构化处理的MALM算法保持了Toeplitz矩阵的结构,从而可以利用快速奇异值分解,使得在奇异值分解时间上要远短于其他2种算法;但是相比ALM算法,MALM算法在均值步增加了数据的传输.而对于一些计算机来讲,数据传输频繁会造成数据堆积而拖延计算时间,因此,基于减少数据传输量的思考,在迭代的尾端,即接近目标矩阵时再进行结构化处理是增效的选择.

1.4 l-TMALM

对矩阵利用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阶段,对迭代矩阵序列进行尾部修正并结构化,结构化使迭代矩阵与目标矩阵保持同样结构,从而可利用快速奇异值分解,修正使迭代矩阵从数值上更加逼近目标矩阵,以便快速地达到可行解.该算法不仅减少了频繁的数据传输量,而且在一定程度上节省了奇异值分解时间.

2 收敛性分析

3 数值实验

通过数值实验比较了 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

4 结束语

对于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.

(责任编辑:马田田)