arXiv:2411.14344cs.DScs.LG2024-11被引 7

提出新算法,高效分解高阶张量并验证唯一性。

Overcomplete Tensor Decomposition via Koszul-Young Flattenings

  • 基于Koszul-Young展开构造新分解算法
  • 在张量秩≤(1−ε)(n₂+n₃)时保证成功,条件优于已有方法
  • 适用于通用成分的高维张量,对理论研究者有启发

受代数复杂度下界与张量分解关联的启发,本文研究了Koszul-Young展开,这是近期矩阵乘法下界的核心工具。基于此,我们提出一种新算法,用于将一个n₁×n₂×n₃张量分解为最少数量的秩一项之和,并验证其分解唯一性。当n₁≤n₂≤n₃且n₁→∞、n₃/n₂=O(1)时,若张量秩r≤(1−ε)(n₂+n₃)(ε>0任意),且分量一般选取,则算法可保证成功;对任意固定ε,运行时间在n₃上多项式。当n₂=n₃=n时,该条件比经典同时对角化算法(要求r≤n)提高两倍,也优于Koiran(2024)的r≤4n/3及Persu(2018)的r≤3n/2。我们进一步证明:所考虑的展开形式无法突破秩n₂+n₃的限制;对于n×n×n张量,更一般的d次多项式展开也无法超越常数倍C(d)n的秩上限。这表明,对于具有通用成分的张量分解,其难度可能远高于随机成分下的情形,后者即使在高度过完备条件下仍可高效求解。

原文摘要 · Abstract (English)

Motivated by connections between algebraic complexity lower bounds and tensor decompositions, we investigate Koszul-Young flattenings, which are the main ingredient in recent lower bounds for matrix multiplication. Based on this tool we give a new algorithm for decomposing an $n_1 \times n_2 \times n_3$ tensor as the sum of a minimal number of rank-1 terms, and certifying uniqueness of this decomposition. For $n_1 \le n_2 \le n_3$ with $n_1 \to \infty$ and $n_3/n_2 = O(1)$, our algorithm is guaranteed to succeed when the tensor rank is bounded by $r \le (1-ε)(n_2 + n_3)$ for an arbitrary $ε> 0$, provided the tensor components are generically chosen. For any fixed $ε$, the runtime is polynomial in $n_3$. When $n_2 = n_3 = n$, our condition on the rank gives a factor-of-2 improvement over the classical simultaneous diagonalization algorithm, which requires $r \le n$, and also improves on the recent algorithm of Koiran (2024) which requires $r \le 4n/3$. It also improves on the PhD thesis of Persu (2018) which solves rank detection for $r \leq 3n/2$. We complement our upper bounds by showing limitations, in particular that no flattening of the style we consider can surpass rank $n_2 + n_3$. Furthermore, for $n \times n \times n$ tensors, we show that an even more general class of degree-$d$ polynomial flattenings cannot surpass rank $Cn$ for a constant $C = C(d)$. This suggests that for tensor decompositions, the case of generic components may be fundamentally harder than that of random components, where efficient decomposition is possible even in highly overcomplete settings.

张量分解代数复杂度算法设计数学优化

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。