基于张量环分解的非精确的低秩填充算法

孟翔宇，温瑞萍

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

0 引言

大规模数据通常以泛数组的张量形式存储，在信号处理[1]、数据挖掘[2]、计算机视觉[3]以及模式识别[4]等领域都有广泛运用.而在采集、存储、传输、处理高维数据等环节，往往会造成数据丢失.因此，数据填充是必不可少的.现实生活的数据之间往往是有关联性的，所以存放数据的张量就表现为低秩[5].利用数据间的关联性可以由已知的数据信息去估计未知或丢失的数据信息，也就是利用低秩张量填充去实现数据恢复.

一般的低秩张量填充模型如下:

(1)

张量分解是研究张量填充问题的关键.目前已知的张量分解模型有基于CP(Canonical Polyadic)秩的张量分解模型[6]，基于Tucker秩的张量分解模型[7]，基于矩阵乘积态/张量链式分解(tensor train/matrix product states)[8]的模型，还有在张量链式分解的基础上进行改进的基于张量环分解的模型[9]，以及新的全连接张量网络分解模型[10]等.

在以上分解模型的基础上，常见的张量填充问题的优化算法有：文献[11]中提出利用块坐标下降的方法求得全局最优解的简单低秩张量填充算法(SiLRTC);将原始非光滑问题转变为光滑问题的快速低秩张量填充算法(FaLRTC); 文献[12]提出一种将n维张量填充模型展成n个矩阵填充的问题，再将求解得到的矩阵恢复成张量的低秩多线性张量填充模型(LMRTC).文献[13]提出的利用块坐标下降实现分别求解的加速近端梯度算法等.

本文主要基于文献[14]张量环分解的低秩填充算法，提出一种非精确的填充方法，与文献[14]算法相比，本文特点是不要求找到每一步迭代的最优解，只保证迭代整体下降.最后通过数值实验验证了算法的有效性.

1 预备知识

(2)

(3)

(4)

定义3(张量模-kcanonical矩阵化)[9，16]∈(I1×…×In)按第k-模展开的矩阵为则

(5)

(6)

2 相关算法

基于张量环分解的低秩张量填充有两个途径[16].第一种是直接基于张量环分解，需要预先给定秩来实现低秩; 另一种是在张量环分解的基础上约束秩最小，所以需要通过凸松弛秩函数来实现低秩.在这一节，我们沿着途径二进行研究，在原始优化模型基础上，添加秩函数正则化项，实现低秩张量填充.

2.1 问题描述

基于张量环分解的张量填充模型如下:

(7)

式(7)添加秩函数正则化项，

(8)

为了方便找到它的最优解，将秩函数凸松弛为张量的核范数.文献[17]中将填充张量的秩定义为其模-k展开秩的和，

(9)

文献[14]中利用张量秩和所对应张量核秩的关系提出了一种新的模型，通过张量核因子的模-2展开的核范数来刻画低秩，再考虑对TR核因子的低秩约束，得到模型(10)，

(10)

(11)

对式(11)使用增广拉格朗日函数进行处理得到模型(12)，实现交替方向分步求解.

(12)

2.2 相关算法

为了提高计算的速度，每一步迭代不需要求到最好的下降效果，只要保证整体下降即可.于是我们利用张量核因子存储信息的2-模展开来代替控制结构的1-模和3-模.根据模型(12)得到了非精确的TRLRF算法.

3 数值实验

本节将通过数值实验来验证本文算法的有效性.所有数值实验均在处理器为Intel(R) Core(TM)i7-3770 CPU @ 3.40 GHz的Windows 10系统的计算机上利用Matlab(R2019b)运行.在图像填充实验中，选择一张大小为509×609×3遥感图像，一张在2003年ICCV会议上的图像数据集里大小为256×384×3的建筑图像以及一小段yuv格式的视频大小为144×176×3×10 进行实验验证(见图1).实验结果见表1、表2、表3.

图1 分辨率为(176×144)的Qcif视频转化为10帧大小为(144×176×3)的图像

遥感图像(509×609×3)缺失率TR秩算法迭代次数运行时间RES(相对平方误差)0.66×6×60.69×9×90.8 6×6×60.8 9×9×9TRLRF8312.972 40.093ieTRLRF284.403 70.102TRLRF7925.766 40.089ieTRLRF5116.579 40.100TRLRF12426.065 60.120ieTRLRF408.230 00.125TRLRF5521.937 70.120ieTRLRF3012.369 60.123

表2 TRLRF与ieTRLRF实验数据比较

表3 TRLRF与ieTRLRF实验数据比较

从实验结果可以看出在图像像素缺失率为0.6以及0.8的情况下，非精确的低秩填充算法(ieTRLRF)与精确(TRLRF)算法相比，填充效果一致，但是在耗费时间上TRLRF是ieTRLRF算法的近三倍.除此之外，两种算法的相对平方误差相差不大并且ieTRLRF算法的迭代次数远远少于TRLRF算法的迭代次数．这些都说明本文算法的有效性和可行性.

4 总结

本文提出了一种非精确的基于张量环分解的低秩填充算法.它不要求每次迭代下降取最优，只考虑整体下降.利用张量核因子中起到存储信息的模-2展开来代替控制结构的模-1和模-3.在保证填充效果差异很小的情况下，减少了计算时间，提高了填充效率.最后通过数值实验验证了本文的算法能够较好地填充缺失数据，充分证明了本文算法的有效性.