arXiv:2609.13693 · v3

Polynomial-time Tensor Decomposition under the Kruskal Condition and the Lovitz--Petrov Generalization

首次提交 2026-09-12 12:03

版本更新 2026-11-03 16:16

雷达观测 2026-11-04 23:39

摘要

An identifiability criterion is a condition on a tensor decomposition that certifies uniqueness when the condition holds. Kruskal's classical condition is one of the best-known deterministic criteria for identifiability. However, no polynomial-time decomposition algorithm is known under the Kruskal condition; verifying the condition itself is NP-hard. Lovitz and Petrov introduced a strictly more general identifiability condition which, in contrast, is polynomial-time verifiable, but no polynomial-time decomposition algorithm was known under this condition either. In this paper we give a randomized polynomial-time algorithm, in the algebraic model over $\mathbb R$, for tensor decomposition under the Lovitz--Petrov condition, and therefore also under the stricter Kruskal condition. Moreover, combining our algorithm with polynomial-time verification of the Lovitz--Petrov condition yields an efficient end-to-end certification procedure: after computing a decomposition, one can deterministically certify in polynomial time that it is unique and therefore of minimum rank.