A TT-BASED HIERARCHICAL FRAMEWORK FOR DECOMPOSING HIGH-ORDER TENSORS

摘要。在大数据背景下，高阶张量分解在存储和计算成本方面面临新的挑战。张量列（TT）分解提供了一种非常有用的基于图的模型降阶方法，其存储成本随张量阶数D DD线性增长。得益于流行的 TT-SVD 算法，TT-核张量和 TT-秩的计算可以通过稳定的顺序（即非迭代）方式完成。

在本文中，我们在 TT 分解的背景下利用了为分层/树状 Tucker 分解所发展的思想。具体而言，提出了一种名为 TT-HSVD（张量列分层 SVD）的新型高效估计方案，作为计算高阶张量 TT 分解的解决方案。

该新算法以分层方式（in a hierarchical way）同时给出 TT-核张量 （TT-core tensors）及其 TT-秩（their TT-ranks）。它是一种稳定（即非迭代）且比 TT-SVD 计算效率更高的算法，这在处理大规模数据时非常重要。TT-HSVD 算法采用了一种新的重塑策略和定制的偏 SVD，这使得我们能够处理比 TT-SVD 中更小的矩阵。此外，TT-HSVD 非常适合并行处理架构。我们对这两种算法进行了代数分析，结果表明 TT-SVD 和 TT-HSVD 计算出的 TT-秩和 TT-核张量是相同的（仅相差特定的基）。针对不同张量阶数和维度的仿真结果证实了所提算法的有效性。

[47] 中提出了一种新的模型降阶范式，在其中被称为张量列 (TT) 分解，此前在粒子物理学界也有提及 [50]。TT 的主要思想，也被称为“张量网络” (tensor networks，TNs) [3, 12]，是将一个高阶( D > 3 ) (D > 3)(D>3)张量分裂成一组低阶张量的乘积集，表示为一个因子图。因子图允许可视化多元或多线性函数（节点）及其依赖关系（边）的分解 [42]。这种图形式在处理大数据背景下非常有用 [56]。

特别地，TT 分解 [47, 46, 27] 通过D DD个 3 阶张量的乘积集来表示一个D DD阶张量。每个 3 阶张量与图的一个节点相关联，并连接到其左侧和右侧的“邻居”，这种连接被编码在一条一对一的有向边中 [50]。对于 CPD 和 TT 分解，相对于阶数D DD的存储成本具有相同的线性行为 [47]。此外，TT 分解拥有一个稳定的（非迭代）基于 SVD 的算法 [47]，即使对于大型张量也是如此。因此，TT 分解有助于打破维度灾难 [48]，因为它可以被视为分层 Tucker (hierarchical Tucker，HT) 分解的一个特例 [26, 27, 65, 60, 48]。请注意，HT 和 TT 分解允许我们以O ( D I R + D R 3 ) O(DIR + DR^3)O(DIR+DR3)和O ( D I R 2 ) O(DIR^2)O(DIR2)的存储成本分别表示大小为I × ⋯ × I I \times \dots \times II×⋯×I的D DD阶张量 [25, 11]，其中R RR是所考虑分解的秩。使用 TT 分解的动机在于其在许多有趣问题中的适用性，例如超压缩 [34]、张量补全 [39]、盲源分离 [5]、大规模矩阵的快速 SVD [43]、线性扩散算子 [33] 和机器学习 [58] 等。

另一类方法包括将数据张量细分为较小的“块”，随后在较小的子张量上进行高效计算 [51, 15, 16, 44]。这些方法仅关注高阶张量的 CPD。

在本文中，我们的兴趣在于 TT 分解和相关的 TT-SVD 算法 [47]。值得注意的是，TT-SVD 是一种顺序算法；即，TT-核是一个接一个计算的，而不是同时计算的。此外，就复杂性而言，它是一种成本非常高的算法，因为它涉及对非常大尺寸的矩阵应用 SVD。为了解决与大规模张量分解相关的计算复杂性问题，人们提出了许多方法 [13]，这些方法或者在张量具有结构时用闭式方法取代非迭代方法 [1]，或者利用数据的稀疏性 [38, 49]，或者利用并行处理通过压缩来减小数据规模 [45, 59]。

作为 TT-SVD 算法的替代方案，我们提出了一种称为 TT-HSVD（Tensor-Train Hierarchical SVD，张量列分层 SVD）的新算法。该算法允许我们以分层方式同时恢复 TT-核张量及其 TT-秩，并且在计算上比 TT-SVD 更高效。所提出的 TT-HSVD 算法采用了一种新的展开和重塑策略，该策略

• 一方面能够跨多个处理器实现分解的并行化，

• 另一方面，与基于 TT-SVD 的竞争方案相比，其计算成本更低。

我们的代数分析还表明，TT-SVD 和 TT-HSVD 计算出相同的 TT-秩和 TT-核张量（仅相差特定的基）。

3. Standard tensor decompositions

截断奇异值分解 (Truncated SVD)，也被称为低秩近似 (low-rank approximation)，也将被大量使用。著名的 Eckart-Young 定理 提供了对给定矩阵的最佳近似（在 Frobenius 范数意义下）存在的证明，该最佳近似是通过另一个秩较小的矩阵实现的。此外，该定理确保了最佳低秩近似可以通过截断奇异值分解以一种稳定（即非迭代）的方式计算出来。

3.2.3. Why to use the TT decomposition.

• 对于已知阶数的张量，TT 分解具有唯一的基于图的表示；即，任何D DD阶张量都可以分解为 TT 格式，即D DD个阶数至多为 3 的 TT-核的乘积集，这是相对于底层张量网络的所有节点都对齐的那一种配置而言的。如图 2© 所示，HT 分解的情况并非如此。可能的配置数量随阶数D DD迅速增长。例如，一个 10 阶张量容许 11 种不同的 HT 分解 [40]。

• “with respect to the one configuration where all nodes of the underlying tensor network are aligned” 可以通俗地解释为
• “基于那种将底层张量网络中所有节点都排成一条直线（对齐）的特定结构配置。”

• 如果 TT-秩的上界为R RR[26]，则 HT 的秩的上界为R 2 R^2R2。如果假设秩相等且I II不太大，由于 HT 格式中存在不同于单位矩阵的叶子节点，TT 格式中的自由参数数量要少于 HT 格式中的数量。
• TT 分解的存储量随D DD线性增长，而 HOSVD 的存储量随D DD指数增长，且伴随着巨大的计算成本。

如果 TT 分解能够用一个最大秩R RR来精确或很好地近似一个D DD阶张量，那么 HT 分解要达到同样的表示能力，其内部的子空间秩（HT 秩）可能需要达到R 2 R^2R2级别。

• TT 分解具有紧凑的形式，不像树状分解（如树状 Tucker [48]），后者需要基于 Gram 矩阵计算的递归算法，实现起来很复杂 [47]。

4. Hierarchical methodology to compute the TT decomposition.

在本节中，在介绍我们的主要贡献之前，我们首先回顾一下 TT-SVD 算法 [48]。

4.1. Description of the TT-SVD algorithm.

在实践中，TT 分解是借助于 TT-SVD 算法 [48] 完成的。完整的算法在图 4 中针对一个 4 阶张量进行了描述。请注意，当我们对矩阵X ( d ) \mathbf{X}_{(d)}X(d)​应用截断 SVD 时，由奇异值构成的对角矩阵被吸收进了V d \mathbf{V}_dVd​中。

从这个简单的例子中，我们可以得出结论，TT-SVD 算法包括顺序地截断矩阵V d \mathbf{V}_dVd​的重塑版本的 SVD，其中d = 1 , … , D − 1 d=1,\dots,D-1d=1,…,D−1。重要的是要注意，算法的每一步都产生一个 TT-核，导致这是一个无法并行的顺序算法。

4.2. Description of the TT-HSVD algorithm

在本节中，介绍了 TT-HSVD 算法，目的是以并行的分层方式推导 TT-核。TT-SVD 和 TT-HSVD 之间的主要区别在于待 SVD 处理的初始矩阵展开，以及重塑策略，即在每一步重塑 SVD 因子( U d , V d ) (\mathbf{U}_d, \mathbf{V}_d)(Ud​,Vd​)的方式。图 5 通过 4 阶张量 TT 分解的基于图的表示说明了所提出的策略。

该图应与图 4 进行比较。在 TT-HSVD 算法中，对于一个先验选择的索引D ˉ ∈ { 1 , … , D } \bar{D} \in \{1,\dots,D\}Dˉ∈{1,…,D}，第一个矩阵展开X ( D ˉ ) \mathbf{X}_{(\bar{D})}X(Dˉ)​的大小为( I 1 ⋯ I D ˉ ) × ( I D ˉ + 1 ⋯ I D ) (I_1 \cdots I_{\bar{D}}) \times (I_{\bar{D}+1} \cdots I_D)(I1​⋯IDˉ​)×(IDˉ+1​⋯ID​)，而不是像 TT-SVD 算法那样是I 1 × ( I 2 ⋯ I D ) I_1 \times (I_2 \cdots I_D)I1​×(I2​⋯ID​)，这导致了一个更加矩形的矩阵。其R D ˉ R_{\bar{D}}RDˉ​-截断 SVD 分别提供了两个大小为( I 1 ⋯ I D ˉ ) × R D ˉ (I_1 \cdots I_{\bar{D}}) \times R_{\bar{D}}(I1​⋯IDˉ​)×RDˉ​和R D ˉ × ( I D ˉ + 1 ⋯ I D ) R_{\bar{D}} \times (I_{\bar{D}+1} \cdots I_D)RDˉ​×(IDˉ+1​⋯ID​)的因子U D ˉ \mathbf{U}_{\bar{D}}UDˉ​和V D ˉ \mathbf{V}_{\bar{D}}VDˉ​。这两个因子现在被并行地重塑，构成了与 TT-SVD 算法的主要区别，后者仅对V 1 \mathbf{V}_1V1​应用单一的重塑操作。这种处理在每次 SVD 计算后重复进行，如图 5 针对 4 阶张量所示。

一般而言（Generally speaking），最佳重塑策略的选择，即索引D ˉ \bar{D}Dˉ的选择，依赖于与每个应用相关的先验物理知识 [37, 6]，例如，在生物医学信号分析或无线通信中 [14, 66, 21]。在第 7 节中，将从算法复杂度的角度讨论这种最佳选择。为了说明这种选择，图 6（左）和图 6（右）考虑了两种重塑策略，用于使用 TT-HSVD 算法计算 8 阶张量的 TT 分解。更准确地说，

• 图 6（左）对应于I D ˉ = I 4 I_{\bar{D}} = I_4IDˉ​=I4​的平衡展开，
• 而图 6（右）对应于I D ˉ = I 3 I_{\bar{D}} = I_3IDˉ​=I3​的非平衡展开。

从这个简单的例子可以得出结论，这种基于图的表示不具说明性，这激发了下一节中引入的使用模式的新型基于图的表示。

4.3. Graph-based representation with patterns.

在表 3 中，我们展示了针对 TT-SVD 和 TT-HSVD 的估计张量的归一化重建误差，其中考虑了一个受加性高斯噪声影响的张量。原始张量是一个 8 阶超立方张量，其服从典型秩R = 2 R = 2R=2且维度I = 4 I = 4I=4的 CPD。对于联合降维与因子检索 (JIRAFE) 框架 [69, 68] 而言，这是一个有趣且现实的案例，在该框架中，原始张量是一个高阶 CPD，在估计其参数之前，它被分解为 TT 格式以打破其维度。接下来的实验考虑了两种情况，即

• 当原始含噪张量的 TT-秩已知且等于R RR时，
• 以及当 TT-秩未知且在算法的每一步进行估计时。

给出的误差是通过对 1000 次蒙特卡洛运行的结果取平均值获得的。可以注意到，对于大范围的信噪比 (SNR)，无论是估计 TT-秩还是假设 TT-秩已知，两种算法都具有相同的鲁棒性。这意味着在用于高阶张量参数估计的 JIRAFE 框架中，TT-HSVD 可以作为 TT-SVD 算法的一个更好的替代方案。

7. Conclusion and future work.

在这项工作中，我们提出了 TT-HSVD 算法，这是一种用于张量列 (TT) 分解的分层算法。这个新算法允许我们同时/分层地恢复 TT-核张量及其 TT-秩。还提出了一种使用模式的新型基于图的表示法，以简化并使 TT-SVD 和 TT-HSVD 算法的算法表示更具说明性。我们的分析表明，TT-SVD 和 TT-HSVD 算法估计出相同的 TT-秩和相同的 TT-核张量（仅相差特定的基），且 TT-HSVD 算法具有显著的时间和内存节省。前景包括研究以随机方式组合张量模态，以及这种修改对估算和算法复杂度的影响。

未来的研究包括在所提出的分层算法中使用交叉插值代替 SVD。一些工作已经解决了交叉插值方案，或者是针对离散张量（如在 [57, 2] 中），或者是将其推广到连续情况（如在 [23] 中）。例如，在 [57] 中，证明了最大体积交叉插值的准最优精度，并提出了一种使用与 TT-SVD 相同逻辑但用插值代替 SVD 近似的算法。除了准最优性之外，结果还表明该解决方案可以提供比 SVD 更快的低秩近似。因此我们可以设想，将 TT-HSVD 与使用插值代替 SVD 的模式结合使用，将是这项工作合乎逻辑且有趣的延续。未来的工作还涉及将 TT-HSVD 算法应用于诸如张量补全 [39]、盲源分离 [5] 和大规模矩阵的快速 SVD [43] 等问题。