Beyond Kruskal: Polynomial-Time Tensor Decomposition under the Lovitz-Petrov Condition

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 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.

Eigensolvers for polynomial roots and tensor decomposition
Enrica Barrilli, Bernard Mourrain
arXiv14 Sep 2026PreprintarXiv licenceFull textAlgebra & number theoryarXiv
A Global Wavefront Set Condition for Defining Bony's Paraproduct Decomposition
Josh Mott, Tim Van Hoose
arXiv1 Oct 2026PreprintarXiv licenceFull textAnalysis & PDEsarXiv
Heteroskedastic Canonical Polyadic Tensor Decomposition
Kyle Ritscher, Carlos Llosa-Vite
arXiv9 Oct 2026PreprintarXiv licenceFull textStatisticsarXiv
A Direct Polynomial Approach to Spectral Decomposition
Simon Bossoney, Marc Troyanov
arXiv31 Oct 2026PreprintarXiv licenceFull textAnalysis & PDEsarXiv
PAR2COX: Survival-Informed Tensor Decomposition for Phenotyping and Risk Prediction from Irregular Longitudinal Data
Mariafrancesca Patalano, Elif Konyar, Kamran Paynabar
arXiv20 Sep 2026PreprintarXiv licenceFull textStatisticsarXiv

Cite

BibTeX RIS

BibTeX

@misc{sivan2026beyond,
  title = {{Beyond Kruskal: Polynomial-Time Tensor Decomposition under the Lovitz-Petrov Condition}},
  author = {Shiri Sivan},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.13693},
  eprint = {2609.13693},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.13693},
}

RIS

TY  - UNPB
TI  - Beyond Kruskal: Polynomial-Time Tensor Decomposition under the Lovitz-Petrov Condition
AU  - Shiri Sivan
PY  - 2026
DA  - 2026/09/22
PB  - arXiv
DO  - 10.48550/arxiv.2609.13693
UR  - https://arxiv.org/abs/2609.13693
AB  - 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 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.
ER  -

Abstract

Related

Cite