随机低秩逼近算法在张量近似中的应用

陈熙 冯月华

摘 要 随着大数据时代的到来，实际应用中出现的张量规模也越来越大，因此求解张量的Tucker分解的算法效率有待提升。本研究基于随机投影算法的技术以及高效的数据访问要求，改进Tucker分解中最重要的矩阵奇异值分解，进而得到一种新的高效求解Tucker分解的算法。借助Matlab软件实现新算法，数值实验结果表明新算法在效率上具有显著的提升优势。

关键词 奇异值分解 随机算法 张量近似 Tucker分解 低秩逼近

中图分类号：TP311 文献标识码：A 文章编号：1007-0745（2021）09-0058-03

张量是一个多维数组。一阶张量是向量，二阶张量是矩阵，三阶或更高阶的张量称为高阶张量。高阶张量的分解在信号处理、数值线性代数、计算机视觉等领域都有大量的应用[1-3]。张量分解可以被认为是矩阵奇异值分解的高阶扩展。常用的两类分解分别是CANDECOMP/PARAFAC（CP）分解[4]和Tucker分解[5]，前者将张量分解为一阶张量的总和，而后者是矩阵奇异值分解（SVD）的高阶形式，本文主要研究的是Tucker分解。

在计算 Tucker 分解的各种算法中，一个关键步骤是计算张量的每种可能模式展开的精确或近似的奇异值分解，这将在后面定义。为了有效地计算给定张量的可靠Tucker分解，本文基于随机算法策略以及高效数据访问的要求，提出一种新的高效算法求解Tucker分解，并用Matlab软件实现该算法。

1 随机算法

任意给定一个向量，Diag（x）表示对角元为向量x的对角矩阵。对于任意的矩阵，其SVD为：

在大数据分析和机器学习中，SVD 已成为一种关键的分析工具[6]。但是这些经典算法需要高内存消耗且计算复杂度高，已经无法满足时代发展的需求。近年来随机算法的出现为构造近似SVD算法提供了强有力的支撑。与古典数值算法比较，随机算法具有简单易实现，更高运行效率，更具鲁棒性，更少内存空间等优点。Tropp等人[7]基于随机投影策略提出了单步随机奇异值分解（SPRSVD）得到给定矩阵的近似SVD，具体内容见算法1。由于原始数据集只在算法最开始的时候用到，因此算法具有高效率。

2 张量近似问题

在这里回顾一些张量的基本符号和概念，这些符号将应用于后面的数值实验。关于张量性质和应用的更详细讨论见文献[8]。张量是一个d维数组，通常用符号来表示，其元素为。

张量X按第n维展开用矩阵表示。由于这个张量有d维，所以一共有d种展开的可能性。张量的第n维展示与矩阵的乘积得到一个张量，即：

方程（1）称为Tucker 分解。HOSVD的计算成本和内存消耗对于大规模问题令人望而却步，因此顺序截断的 HOSVD（ST-HOSVD）算法被用来提高HOSVD 的效率[10]，该算法保留了截断HOSVD算法的几个有利特性，同时降低了计算分解的计算成本。STHOSVD算法的伪代码包含在算法2中。

3 新算法STHOSVD-SPRSVD

随着实际问题中张量问题的越来越大，对分解算法的效率要求也越来越高。算法2中计算代价最大的是每个张量展开需要计算SVD，因此算法2中的SVD分解将采用单步随机奇异值分解实现，进而得到更高效的Tucker分解，并将此算法命名为STHOSVD-SPRSVD，具体细节见算法3。

4 数值实验

本节通过几个数值实验验证新算法STHOSVD-SPRSVD，并与propack包中LANSVD方法以及Matlab自带的svds命令进行比较。对应的算法分别命名为STHOSVD-LANSVD、STHOSVD-SVDS和STHOSVD-SPRSVD。本实验通过下列方式构造一个稀疏的张量：

其中：是具有非负元素的稀疏向量，符号“”表示向量外积。并通过使用STHOSVD-LANSVD、STHOSVD-SVDS和STHOSVD-SPRSVD这三种算法分别得到一个具有秩（k，k，k）的Tucker分解[G;U1，U2，U3]。相对近似误差使用，其中，││.││F表示矩阵的Frobenius范数。

实验结果显示了STHOSVD-LANSVD、STHOSVD-SVDS和STHOSVD-SPRSVD算法运行在$300 ＼times 300 ＼times 300$稀疏张量上的相对近似误差和运行时间，从结果中观察到，这三种算法的误差是可比的，但是在时间效率上STHOSVD-SPRSVD算法比另外两种算法具有明显的优势。

5 结论

本文基于随机算法提出了STHOSVD-SPRSVD算法得到Tucker分解，數值实验表明STHOSVD-SPRSVD算法在达到所要求的精度上具有更少的计算代价。由于单步的近似SVD存在效率与精度的权衡，本文将基于现有的基础，在接下来的工作中研究具有更高精度和更高效率的算法。

参考文献：

[1] 张晓飞.解张量分解问题的信赖域交替最小二乘法[D].南京：南京师范大学，2014.

[2] 杨立东，王晶，谢湘，匡镜明.基于张量分解模型的语音信号特征提取方法[J].北京理工大学学报，2013（33）：1171–1175.

[3] Feng Y，Xiao J，Gu M.Flip-Flop Spectrum-Revealing QR Factorization and Its Applications on Singular Value Decomposition[J].Elec.Trans.Numer. Anal.， 2018（51）：469-494.

[4] Carroll J D， Chang J J.Analysis of individual differences in multidimensional scaling via an N-way generalization of “Eckart-Young” decomposition[J].Psychometrika， 1970（35）：283–319.

[5] Tucker L R. Some mathematical notes on three-mode factor analysis[J]. Psychometrika， 1966（31）：279–311.

[6] 周志华.机器学习[M].北京：清华大学出版社，2016.

[7] Halko N， Martinsson P G， Tropp J A.Finding structure with randomness： Probabilistic algorithms for constructing approximate matrix decompositions[J].SIAM Rev.，2011（53）：217–288.

[8] Kolda TG，Bader B W. Tensor decompositions and applications[J].SIAM Rev.，2009（51）：455–500.

[9] De Lathauwer L，De Moor B， Vandewalle J.A multilinear singular value decomposition[J].SIAM J.Matrix Anal. Appl.， 2000（21）：1253–1278.

[10] Andersson C A， Bro. R. Improving the speed of multi-way algorithms： Part I.Tucker3[J].Chemom. Intell.Lab.Syst.， 1998（42）：93–103.