Tensor decomposition beyond uniqueness, with an application to the minrank problem
Pascal Koiran and Rafael Oliveira
我们证明了詹尼希在不完全设置中张量分解的独一性定理。 我们的独特性定理基于标准张量分解的替代定义,我们称之为矩阵向量分解。 此外,在我们的唯一性定理适用的相同设置中,我们还设计和分析一种高效的随机算法来计算唯一的最小矩阵-矢量分解(从而计算最小等级的张量排名分解)。 作为我们的唯一性定理和高效算法的应用,我们展示了如何计算矩阵的某些通用向量空间中最小等级(高达标量倍数)的所有矩阵。
We prove a generalization to Jennrich's uniqueness theorem for tensor decompositions in the undercomplete setting. Our uniqueness theorem is based on an alternative definition of the standard tensor decomposition, which we call matrix-vector decomposition. Moreover, in the same settings in which our uniqueness theorem applies, we also design and analyze an efficient randomized algorithm to compute the unique minimum matrix-vector decomposition (and thus a tensor rank decomposition of minimum ran...