张量分解算法研究与应用综述
画日记熊李艳;何雄;黄晓辉;黄卫春
【摘 要】张量分解是处理大规模数据的一种方法,它能有效的对数据进行降阶,由于高阶张量具有唯一性、对噪声更鲁棒、不破坏原数据的空间结构和内部潜在信息等优点,被广泛应用于神经科学、信号处理、图像分析、计算机视觉等领域.论文首先对传统的降维方法进行了介绍,指出这些方法存在的问题和不足.其次对张量分解的三种经典算法:CP分解、Tucker分解以及非负张量分解从算法的求解、基本思想、算法框架以及算法应用等方面进行概括分析,对CP分解算法和Tucker分解算法从多角度进行对比分析.最后对张量分解的现状以及实际应用进行了归纳和总结,并对未来的研究发展趋势进行了分析和展望.%Tensor decomposition is a significant method to deal with large-scale data, which can reduce the data effectively.The high-order tensor is widely ud in neuroscience,signal processing,image analysis,computer vi-sion and other fields as it has such advantages as uniqueness, robustness to nois and zero impact on the origi-nal data of the spatial structure and internal potential information. In this paper, the traditional dimensionality reduction methods
were introduced firstly, and their problems and shortcomings were also discusd. Secondly, general analysis of three classical algorithms of tensor decomposition was carried out from the aspects of algo-rithm, basic ideas, algorithm framework and algorithm applications of CP decomposition, Tucker decomposition and non-negative tensor decomposition. Then, The CP decomposition algorithm and the Tucker decomposition algorithm were compared and analyzed from different angles. Finally, the prent situation, practical application and future rearch trends of tensor decomposition were summarized and analyzed.
【期刊名称】《华东交通大学学报》
【年(卷),期】2018(035)002
【总页数】9页(P120-128)
【关键词】张量;CP分解;Tucker分解;非负张量分解
【作 者】熊李艳;何雄;黄晓辉;黄卫春
【作者单位】华东交通大学信息工程学院,江西 南昌330013;华东交通大学信息工程学院,江西 南昌330013;华东交通大学信息工程学院,江西 南昌330013;华东交通大学软件学院,江西 南昌330013
【正文语种】中 文
【中图分类】TP301.6
1 数据降维及张量概述
随着互联网时代的不断发展，数据规模越来越大，数据的结构往往具有高维特性，对高维数据进行处理，人们可以挖掘出有价值的信息。但是数据维度越高，数据处理难度越大，计算复杂度的增加往往会带来“维度灾难（Cur of dimensionlity）”，为了避免“维度灾难”，在传统的处理方法中，人们往往通过维数约简的方法对高维数据进行降维处理。传统的维数约简方法能够对数据进行有效的降维，如独立成分分析（ICA）[4]、主成分分析（PCA）[1-2]、线性判别分析（LDA）[5-6]、局部特征分析（LFA）[7-8]等。 基于核函数的非线性维数约简方法有：基于核函数的独立主成分分析（KICA）[9]、基于核函数的主成
分分析（KPCA）[10-11]、基于核函数的决策分析（KDA）[12]等等。在对数据降维的过程中，传统的维数约简方法不可避免的破坏原数据的几何结构，在对数据降维和特征提取的过程中，往往会对原始数据造成一定的损失，在这种情况下，张量以其不损坏数据的内在结构和潜在信息而受到广泛关注，将数据表示成张量结构能有效的解决高阶数据问题。
张量是一个多维数组，一阶张量是向量，二阶张量是矩阵，三阶及以上张量称之为高阶张量[3]。在实际应用中，张量实现了对问题更准确的建模。对于具有张量结构的高阶数据，可以通过对张量数据进行分解以减少数据的损失，降低计算的复杂度，从而保留原始数据的信息和特征。本质上，张量分解是一种高阶数据的分解方法，在社交媒体，学术趋势研究，社区演化等领域均可用张量分解进行数据分析。在学术领域，传统的方法往往研究的是数据的单一特征，如<作者，论文＞的关系。 然而，在现实世界中，数据往往表现的是高阶关系，例如<作者，论文，关键字＞，<用户，产品，标签＞等。
张量分解最经典的分解方法为CP分解和Tucker分解，CP分解的思想是将一个N阶张量分解为若干个秩一张量和的形式，CP分解能够保证分解结果的唯一性，但CP分解对应的秩求解是一个NP难题，在Kolda[3]的文章中给出张量秩的近似求解方法。Tucker分解的思想是黄芪的功效作用
将原张量分解成核心张量和因子矩阵乘积的形式，核心张量保留原张量的主要信息。在现有经典算法的基础上，矩阵的算法和理论思想已经推广到了高阶张量，并取得了一系列的研究成果。近年来，张量分解在神经科学[13-18]、信号处理[19-22]、数据挖掘[23,24]、图像分析[25-26]等领域的发展日趋成熟。
现在已有相关的英文综述文章和论著对张量分解相关算法进行总结和概述[3]，但有关张量分解算法，包括CP分解、Tucker分解和非负张量分解算法及其具体应用方面的资料，尤其是中文综述资料较少。另一方面，对这些理论和技术的典型应用的总结还不多见，本文希望抛砖引玉，为相关领域同行的研究提供一个参考。
在本文中，我们首先对张量分解中最经典的算法CP分解和Tucker分解进行对比分析，对CP分解、Tucker分解和非负张量分解在前人的研究基础上进行了归纳和总结，并给出了这些经典算法的求解方法。最后从人脸识别、信号处理、个性化推荐的领域详细举例说明近来它们的典型的应用。
2 符号参数和相关运算西游记睡前故事
论文中，向量（一阶张量）用小写粗体字母表示，如：a，矩阵（二阶张量）用大写粗体字母表示，如：A，张量（三阶及以上张量）用欧拉粗体字母表示，如：χ，常量用小写不加粗字母表示，如：a。向量a中的第i个元素用 ai表示，矩阵 A 中的第（i，j）个元素用 aij表示，张量 χ 中的第（i，j，k）个元素用 χijk表示，取值范围为（1，I），即：i=1，…，I。 符号“◦”表示向量的外积，序列中的第 n 个元素表示为：A（n）。
对于矩阵 A∈RI×J，B∈RK×L，A⊗B 表示矩阵的 Kronecker积，A∈B 表示矩阵的 K-R 积， A*B 表示矩阵的Hadamard积，运算如下
矩阵 A∈RI×J，B∈RK×L，A⊗B 运算后矩阵的大小为（IK）×（JL），A∈B 运算后矩阵的大小为（IJ）×（K），A*B 运算后矩阵的大小为I×J，‖A‖表示矩阵A的奇异值之和，表示矩阵A的l2，1范数，ai表示矩阵A的第i列。
3 CP分解和Tucker分解比较武术英文
表1 CP分解和Tucker分解比较Tab.1 Comparison of the CP decomposition and the Tucker decomposition?
表1式中：P，Q，R，I，K均为对应矩阵中的维度值；p，q，r均为对应维度值中的参数值。
4 张量分解的三种经典算法
4.1 CP分解及其算法
对于三阶张量，Tucker分解的数学表达式为
若分解后的矩阵A，B，C对应的列被正则化，则分解后存在一个权重向量λ，公式（4）转化如下
CP交叉最小二乘法（CP-ALS）是CP分解应用最经典的算法，算法如下：
对于一般的N阶张量，CP分解的形式为
1）已知：原始张量 χ
2） 初始化：A（n）∈RIn×R，其中 n=1，…，N
3） 循环 n=1，…，N
V←A（1）TA（2）*…*A（n-1）TA（n-1）*A（n+1）TA（n+1）*…*A（N）TA（N）关于元宵节的古诗词
A（n）←X（n）（A（N）*…*A（n+1）*A（n-1）*…*A（1））V
得到规范列 A（n）和 λ
迭代结束
4） 最终输出：λ，A（1），A（2），…，A（N）
程序结束。
4.2 Tucker分解及其算法
对于三阶张量，Tucker分解的数学表达式为
对于一个三阶张量 χ∈RI×J×K，Tucker分解可以将张量 χ 分解成三个因子矩阵 A∈RI×P，B∈RJ×Q，C∈RK×R和一个核心张量G∈RP×Q×R的形式，因子矩阵称为对应模上的基矩阵，
因子矩阵也称为该模上的主成分，因此Tucker分解又称为高阶奇异值分解。
将公式（7）推广到N阶即
写成矩阵形式即
式中：g为G中某一维度上的矩阵。
高阶奇异值分解算法（HOSVD）是Tucker分解应用最经典的算法，算法如下：
1）已知：原始张量χ
2） 张量按模展开 χ（n），n=1，…，N
3） 循环 n=1，…，N：计算奇异值分解得左奇异值Uk循环结束
4） 核心张量 G←χ×1A（1）T×2A（2）T…×NA（N）T
5） 最终输出：G，A（1），A（2），…，A（N）程序结束。
4.3 基于低秩表示的非负张量分解
在实际应用中，如何将样本划分到对应的低维子空间，是一个复杂问题。传统的划分方法有SVD[56]、PCA[1-3]、LDA[5,6]、SSC[54]等，这些方法广泛应用于图像数量、人脸聚类等问题。稀疏表示衍生于压缩感知理论，数学模型表示如下
其中‖Z‖*为矩阵奇异值之和，模型（10）在人脸识别、图像分割等领域中应用广泛，通过不断迭代逼近进行求解，对于3阶张量X=G×1U1×2U2×…×NUN求其最优解可以通过下式得到
对于式（10）中的低秩表示模型，在不考虑噪声的情况下，引入辅助变量Z，式（11）转化如下
对于式（12），其增广拉格朗日函数L为
其中S为拉格朗日乘子，对于式子（13），一般采用ADM方法进行求解。
非负Tucker分解是Tucker分解在非负矩阵分解中的具体应用，算法如下：
1） 已知：输入原始张量 χ，初始化 G≥0，U（n）≥0，n=1，…，N，迭代次数为 T
2） 张量 χ 按模展开得 A（n），n=1，…，N
3）循环 Z
循环 n=1，…，N Z＝G×1U（1）×2…×（n-1）U（n-1）×（n+1）U（n+1）…×NU（N）
4）将Z按n模矩阵化为Zn U（n）≈（U（n）*（XnZnT）） ／（U（n）ZnZnT）
循环结束
5）
循环结束
6） χ 的重构张量：G×1U（1）×2…×NU（N）
程序结束。
时间词
5 张量分解的应用
酒暖回忆思念瘦
5.1 人脸识别
随着信息技术的发展，人脸识别技术的研究取得了显著成果，利用分析比较人脸视觉特征信息进行身份鉴别，人脸识别方法[27-30]在发展的过程中已经走进大众生活。在实际应用中，对于输入的人脸图像或者视频流等数据，数据呈现的往往是高维的，并且这些数据往往由于像素维数较高，容易导致“维数灾难”的发生[31]，从而使问题处理非常困难。因此处理这些高维数据首先需要降维，在传统的降维方法中，一般采用独立成分分析[4]、主成分分析[1-2]、线性判别分析[5-6]等方法进行降维。但是利用传统的降维方法进行降维，由于噪声等因素的影响，不可避免的会丢失一些数据信息。针对上述降维方法中的缺陷，近年来，学者提出将图像数据处理成张量形式，并且这些元素都是非负的。在基于非负张量的人脸识别中，Welling[32]在2011年将NMF推广到非负张量，即正张量分解的不动点算法（PTF），该算法能有效的最小化重构误差，对应任何秩的张量都能被分解，PTF不动点算法的性能优于奇异值分解算法。Kim[33]等人基于张量的Tucker模型，研究了NTF乘性迭代规则，由于数据张量通常具有多种模式并且是大规模的，现有算法在存储和计算时间方面都具有非常高的复杂度，NTF乘性迭代算法能显著的降低存储复杂性和运行时间。Tamir Hazan[34]等人从梯度的角度研究了NMF方法，通过梯度下降进行迭代求解，使数据的收敛速度更快，Chen[35]提出了NMF-ALS方法，该算法概述了数值分析中的强非负约束问题。
