arXiv preprint ·
Beyond Kruskal: Polynomial-Time Tensor Decomposition under the Lovitz-Petrov Condition
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Kusner's conjecture is false for $p>4$
NOC NOC, who's there? Clustering systems of tree-child and normal networks
The Complexity of Weak Partition Connectivity in Hedgegraphs
Edge-addition monotonicity of positive p-energy fails for every p >= 1
The threshold for online balancing of i.i.d. binary vectors
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.