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

陈熙 冯月华

摘 要 随着大数据时代的到来，实际应用中出现的张量规模也越来越大，因此求解张量的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]。但是这些经典算法需要高内存消耗且计算复杂度高，已经无法满足时代发展的需求。……