求解张量多线性低秩逼近的随机算法及其应用

As the generalization and development of matrix decompositions, tensor decompositions are essential tools to the analysis of high-dimensional data. The low multilinear rank approximations, as a special case of tensor decompositions, has widely used in these aspects, such as pattern classification, multilinear subspace analysis, item recommendation and compression of aerodynamic databases..In this project, we will study randomized algorithms for the low multilinear rank approximations. To be specific, by combining random projection and matrix decompositions, we first derive a class of two-stage randomized algorithms for the low multilinear rank approximations with unknown multilinear rank. Numerical examples illustrate that in terms of running time, the two-stage algorithms are competitive with other existed algorithms. Secondly, in order to improving the accuracy of the low multilinear rank approximation derived by two-stage algorithms, by combining power scheme, sparse embedding, random projection and matrix decompositions, we derive a class of three-stage randomized algorithms for the low multilinear rank approximation. Numerical examples illustrate that in terms of running time and relative error, the three-stage algorithms are competitive with other existed algorithms. Finally, for the given factor matrices, we consider how to compute the core tensor via randomized algorithms..By studying these problems, we not only obtain the randomized algorithms for the low multilinear rank approximation, but also provide some references for the computation of other tensor decompositions.

作为矩阵分解在高维情况下的推广和发展，张量分解是一种常见的分析高维数据的降维工具。张量多线性低秩逼近，作为一种特殊的张量分解，在模式分类、多线性子空间分析、系统推荐、飞机动力学数据的压缩等方面有着广泛的应用。.本项目拟研究张量多线性低秩逼近的随机算法。首先，在给定多线性秩的情况下，将随机投影和矩阵分解相结合，得到一类求解张量多线性低秩逼近的两阶段随机算法；数值例子表明与已有算法相比较，在时间方面两阶段算法有很强的可比性。然后，为了提高两阶段算法的精度，在实现两阶段算法之前，先将乘幂策略和稀疏子空间嵌套作用于原始张量，得到了一类三阶段随机算法；数值例子表明三阶段算法与已有的算法在时间和相对误差这两方面有很强的可比性。最后，给定因子矩阵时，研究了快速计算核张量的随机算法。.通过这些问题的研究，我们不仅得到了求解多线性低秩逼近问题的随机算法，而且为求解其他形式的张量分解提供了一定的参考。

随着科学技术的发展和各学科交叉融合的不断深入，许多领域涌现出越来越多的大规模数学问题。这些问题的解和所涉及的数据不仅规模大、维数高，还有某种内在的特殊结构。仅用矩阵表示这些数据会丢失一些数据本身的结构性质。使用张量表示这些复杂的数据是自然的，同时张量也能反映数据内在结构特点。我们取得如下方面的成果：.1. 基于Gaussian随机矩阵、次抽样随机傅里叶变换和稀疏子空间嵌套，提出了一些求解多线性低秩逼近的随机算法；为了降低近似误差，将这些随机算法和乘幂策略相结合。.2. 在t-乘积意义下，提出了求解t-SVD的张量神经网络模型；研究了t-URV分解的相关性质；提出了求解t-URV分解和张量奇异值阈值的随机算法。.3. 求解张量互补问题的随机Kaczmarz方法；求解张量方程组的加速神经网络模型和预处理张量分裂AOR迭代算法；随机张量互补问题的期望残差最小形式的可解性。.4. 求解非负张量的非负CP分解和非负Tucker分解的迭代算法；Tucker形式下张量CUR分解的扰动分析。