Polynomial time algorithm finds unique tensor decompositions efficiently
Beyond Kruskal: Polynomial-Time Tensor Decomposition under the Lovitz-Petrov Condition
Data Structures and Algorithms
Summary
Tensor decomposition breaks down complicated data arranged in grids into simpler parts, but figuring out if there's only one best way to do this has been very hard and slow. Kruskal's known method can check uniqueness but is too slow and hard to use practically. The authors build on a newer idea by Lovitz and Petrov that generalizes this condition and can be checked quickly, and they create the first fast algorithm that actually finds the unique tensor decomposition under this condition. This means that now we can not only break down tensors quickly but also be sure the breakdown is the simplest and unique one, which was not possible before.
What this means in practice
- •For machine learning engineers: Decompose complex data tensors efficiently and verify uniqueness of the decomposition to improve model interpretability and reliability.
- •For data analysts: Use polynomial-time algorithms to certify minimum-rank tensor decompositions, enhancing analysis of multiway datasets in practical time frames.
Authors
Shiri Sivan
Abstract
Identifiability criteria certify that a given tensor decomposition is a unique rank decomposition. 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, and 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 previously known under this condition. We give a polynomial-time algorithm for 3-way tensor decomposition under the Lovitz--Petrov 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. This contrasts with an arbitrary tensor decomposition, which certifies only an upper bound on the tensor rank, while determining tensor rank is NP-hard in general.