Search Results

A famous theorem of Kruskal gives the simplest and arguably most fundamental criterion under which a tensor is guaranteed a unique minimum-rank decomposition. Kruskal’s condition requires that the sum of the Kruskal ranks {k_i}_{i=1}^m of the components satisfies ∑_{i∈[m]} k_i ≥ 2r + m - 1, where r denotes the rank and m the order of the tensor. However, Kruskal’s original proof and subsequent simplifications/generalizations have remained non-constructive. With the sole exception of the case (k₁ = r, k₂ = r, k₃ = 2), attributed to Jennrich - no algorithm has been established for decomposing tensors under the Kruskal condition without additional assumptions. In fact, whether there exists an efficient algorithm for decomposing a tensor under the Kruskal condition was explicitly posed as an open problem in the work of Bhaskara et al. (COLT 2014). Even slight variations of the Jennrich special case, such as the (r, r-1, 3) case, have remained algorithmically open; specifically, no sub-exponential time bound was known. In this work, we make progress on this problem by giving an elementary, constructive proof of Kruskal’s Theorem for general m-way tensors. Concretely, we give a randomized algorithm that decomposes any tensor satisfying the Kruskal condition by utilizing random projections to map the problem into a geometry of intersecting hyperplanes via a MinRank instance. Specifically for 3-way tensors satisfying k₁+k₂+k₃ = 2r+2, the algorithm achieves a runtime of n^O(k) where k = min(k₁,k₂,k₃). Thus, we extend smoothly beyond the Jennrich special case, achieving polynomial-time complexity for any family of tensors that satisfies the Kruskal condition, provided the least Kruskal rank is bounded.