《武汉工程大学学报》  2021年04期 442-447   出版日期:2021-08-31   ISSN:1674-2869   CN:42-1779/TQ
基于张量链分解的低秩张量补全研究


张量作为向量和矩阵的高阶扩展,同时能够保留数据的高维结构,适合用来表示自然中具有多维特征的数据。张量已经在许多领域得到了广泛的应用,包括信号处理[1-2]、计算机视觉[3-4]、神经科学[5]和机器学习[6]。然而实际采集到的高维数据通常是遭到破坏或有部分缺失的,对于这种情况,可以根据已观测到的部分数据来恢复其缺失部分,这就是张量补全研究。本文研究的低秩张量补全问题是通过张量分解获得的潜在低秩表达与数据低秩的特性,利用数据空间中数据的低秩关联结构更有效地预测缺失部分。CANDECOMP/PARAFAC分解[7]和Tucker分解[8]是经典的张量分解方法,已经有许多基于它们的张量补全算法,例如CP分解加权法(CP-weighted optimization,CP-WOPT)[9],完全贝叶斯处理(fully Bayesian CP factorization,FBCP)[10]以及张量同时分解和补全方法(simultaneous tensor decomposition and completion,STDC)[11]。但是,由于经典张量分解模型的局限性,仅在低维张量补全时才能达到较高的精度,并且容易因为维度太大参数过多而遭受“维度诅咒”。近来,已经提出了一种基于矩阵乘积状态(matrix product state,MPS)模型的张量链分解[12],张量链分解能够将高阶张量分解成一组三阶张量,具有很高的数据压缩能力和计算效率,本文将基于张量链分解研究低秩张量补全问题。目前广泛应用的低秩张量框架是将张量每个模展开矩阵的秩作为优化目标,通过求解秩加权和最小化问题来低秩近似原始张量。由于张量低n-秩最小化模型是一个多项式的非确定性问题(non-deterministic polynomial,NP),需要对秩函数进行凸松弛,通常的做法是转换成独立的模展开矩阵的核范数求解,这样每次迭代都需要进行大量的奇异值分解(singular value decomposition,SVD)计算。尽管最近已经提出了许多基于张量链分解的张量补全方法,但是与它们对原始数据施加低秩约束不同,受Tucker分解核心张量核范数[13]的启发,本文在张量链核心张量上引入最小化约束,这可以将大规模张量核范数问题转换为小型核心张量核范数问题来解决,基于张量链分解的核心张量来解决低秩张量补全问题,并且给出了具体算法流程,最后运用交替方向乘子法(alternating direction of method of multipliers,ADMM)[14]求解,使其在迭代过程中具有稳定性能并且计算高效。1 张量链分解采用通用的张量表示方法[15],标量用大小写字母表示,例如[x],[X],矢量和向量用加粗的小写字母表示,例如[x],矩阵由加粗的大写字母表示,例如[X],张量用手写体表示,例如[X]。设[I1,I2,...,IN]表示各维度大小,张量[X∈?I1×I2×?×IN]表示一个大小为[I1×I2×?×IN]的N阶张量。[X (1),X (2),?,X (N)]表示张量序列,其中[X (n)]表示序列中的第n个张量。张量[X∈?I1×I2×?×IN]中第[{i1,i2,?,iN}]个元素可以表示为[xi1i2?iN]或者[X (i1,i2,?,iN)]。[[X](n)∈?In×I1?In?1In+1?IN]表示张量[X ]的模式-n矩阵展开,其反向操作是[fold(n)(X)],表示将[[X](n)]恢复成张量[X]。另外给出张量内积和Frobenius范数定义,两个相同大小张量[X ],[Y]的内积定义如下: [ =i1,i2,?,inXi1,i2,?,inYi1,i2,?,in] (1)张量[X ]的Frobenius范数定义如下:[||X ||F==(i1i2?iNx2i1i2?iN)12] (2)张量链分解 [12]将高阶张量分解为一组三阶张量,这有助于从原始的高阶张量获得低阶核心张量。张量的张量链分解形式可以表示为:[X i1,i2,?,iN=] [α0,…,αNG1α0,i1,α1G2α1,i2,α2?GNαN?1,iN,αN](3)核心张量[G(n)]是大小为[Rn-1×In×Rn]的三阶张量,中间阶大小[In]为原始张量对应阶的维数,剩余两阶的维数称为张量链分解秩。序列[(R0,R1,?,RN)]定义为张量链分解表达的秩,为了最终乘积是一个标量,还需要秩约束为[R0=RN=1]的边界条件。此外对张量中每个元素还有如下分解表达式:[X(i1,i2,?,iN)=G(1)(i1)G(2)(i2)?G(N)(iN)] (4)其中是核心张量的模-2切片矩阵,也可以定义为[G(n)(:,in,:)]。本文中用运算符[Ψ]表示核心张量生成近似张量的的过程,即[X =][Ψ[G(n)]]。2 张量链核心张量核范数最小化方法根据核心张量与原始张量之间的维度大小对应关系,可以得出张量的秩受到其核心张量的秩的约束,意味着如果对核心张量施加低秩约束的同时也对张量自身进行了低秩约束,考虑到核心张量较之原始张量有更低的维度,本算法选择直接把核心张量的秩函数作为优化目标,因此提出基于张量链核心张量的低秩张量补全问题,表达式为:[ minXn=1Nrank(G(n)),s.t.XΩ=TΩ, X=Ψ[G(n)]] (5)其中[X] 表示经过补全算法得到低秩张量,[Ω]表示所有已知元素的集合,[T] 表示张量中可以观测到的部分,[Ψ[G(n)]]表示核心张量生成近似张量的运算。然而上述秩函数问题是一个NP难问题,需要用核心张量的核范数代替秩正则化进行凸松弛。根据张量核范数的定义,又考虑到每个三阶的核心张量分别有3种模展开方式,结合这3种模展开矩阵,可以得到核心张量的核范数定义如下:[||Gn||?=n=1N i=13 αn||Gni||?] (6)其中[||?||?]表示核范数计算,即矩阵所有奇异值的和,[n=1Nαn=1]并且[αn>0]表示各模式矩阵核范数的加权。结合核心张量核范数的定义以及式(5)的补全模型,将条件中的等式约束转换为[λ2||X-Ψ[G(n)]||2F],用来约束恢复的张量[X]与核心张量生成的张量[Ψ[G(n)]]的近似性,[λ]是一个用来平衡低秩约束项与近似约束项的参数,由此得到式(5)的松弛模型,如式(7)所示:[minG(n), Xn=1N i=13 αn||G(n)(i)||?+λ2||X-Ψ[G(n)]||2F,s.t.XΩ=TΩ] (7)式(7)称为基于张量链分解的核心张量核范数的低秩张量补全模型(low-rank tensor-train core tensor nuclear norm minimization,LTTCTNNm),接下来展示算法的具体求解方法。由于优化问题中的变量是相互依赖的,引入辅助张量[M n,i,n=1,?,N,i=1,2,3]来使变量分离,从而转化为如式(8)的问题:[minM n,i,G(n), Xn=1N i=13 αn||M n,i(i)||?+λ2||X-Ψ[G(n)]||2F,s.t.M n,i(i)=G(n)(i),n=1,?,N,XΩ=TΩ] (8)通过将等式约束合并到拉格朗日函数中,得到式(8)的增广拉格朗日函数为:[L(G(n), X, M n,i, Yn)=n=1N i=13(αn||M n,i(i)||?++ρ2||M n,i-G(n)||2F)+λ2||X-Ψ[G(n)]||2F,s.t. X Ω=T Ω] (9)其中[Yn]是拉格朗日乘子张量,运用交替方向乘子法[14],按以下方法迭代更新[Gn],[M n,i],[X],[Yn]:对于每个[G(n),k+1,n=1,?,N],只保留有关的项之后,有如下优化子问题,如式(10)所示:[G(n),k+1=argminG(n)ρ2||M kn,i-G(n)+1ρY kn||2F+] [λ2||X-Ψ[G(n)]||2F] (10)对式(10)求导,取倒数为零的极值点可得式(11):[Gn,k+1=ρM kn,i+Y kn+λX ΨGnNρ+λI] (11)其中[I] 表示单位张量,[ΨG>n],[ΨG[0 50 100 150 200 250 300 350Iteration number][10010-110-210-310-410-510-6][Accuracy][ b ][ a ][0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9Sampling rate][302520151050][P][algorithmHaLRTCTTWOPT][algorithmHaLRTCTTWOPT]图4 (a)图像缺失率50%时各算法收敛性分析对比,(b)算法运行时间随采样率变化的对比Fig. 4 (a)Convergence analysis comparison of algorithms at 50% missing rate,(b)comparison of algorithms running time with different sampling rates 3.2 合成数据考虑用人工合成数据验证该算法的有效性,首先通过张量链分解的方式分别生成四阶和三阶的2个实验张量和,其中核心张量都独立服从标准正态高斯分布,通过对核心张量的运算[Ψ[G(n)]]得到实验张量,对合成数据采用RSE作为性能评估标准。考虑到实验的随机性,每个实验数据的结果都是取10次实验的平均结果。由图5(a)和(b)分别给出了算法在四阶和三阶张量情况下的对比实验结果,结果表明,本文算法除了在采样率极低的情况(20%以下)性能一般,除此以外表现稳定,恢复精度明显高于其他3种算法。而较其他3种算法需要千倍以上迭代次数的TTSGD,由于在本次对比实验中需要的迭代次数太多而被提前终止,表现得极其不稳定并且精度较差。[ b ][ a ][algorithmHaLRTCTTSGDTTWOPT][0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9Sampling rate][10010-1][E][0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9Sampling rate][10010-1][E][algorithmHaLRTCTTSGDTTWOPT]图5 合成张量数据上各算法的RSE随采样率变化的对比:(a)四阶张量,(b)三阶张量Fig. 5 Comparison of RSE of each algorithm on synthetic tensors with different sampling rates: (a) fourth-order tensor, (b) third-order tensor 4 结 论以上对基于张量链分解对缺失张量进行了低秩张量补全的研究,该算法在张量链分解的核心张量上采用了低秩约束方法,并通过凸松弛转换为核心张量核范数最小化求解,这样能够有效降低高阶张量的计算规模。实验表明,本文方法运行时间更短,迭代收敛更快,补全结果也比较好,综合各方面性能均优于对比算法。