陈 熙 冯月华

（1.上海工程技术大学 机械与汽车工程学院，上海 201620；2.上海工程技术大学 数理与统计学院，上海 201620）

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

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

1 随机算法

任意给定一个向量x∈Rn，Diag(x)表示对角元为向量x的对角矩阵。对于任意的矩阵A∈Rm×n(m≥n)，其SVD为：

其中U=(u1,u2,…um)∈Rm×m和V=(v1,v2,…vn)∈Rn×n是正交矩阵，∑=Diag(…)且1≥≥…m≥0。对于1≤k≤n，令A的秩k 截断S VD为：

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