How hard is the tensor rank?

Abstract

We investigate the computational complexity of tensor rank, a concept that plays fundamental role in different topics of modern applied mathematics. For tensors over any integral domain, we prove that the rank problem is polynomial time equivalent to solving a system of polynomial equations over this integral domain. Our result gives a complete description of the algorithmic complexity of tensor rank and allows one to solve several known open problems. In particular, the tensor rank over $\mathbb{Z}$ turns out to be undecidable, which answers the question posed by Gonzalez and Ja'Ja' in 1980. We generalize our result and prove that the symmetric rank admits a similar description of computational complexity as the one we give for usual rank. In particular, computing the symmetric rank of a rational tensor is shown to be NP-hard, which proves a recent conjecture of Hillar and Lim. As a byproduct of our approach, we get a similar characterization of the algorithmic complexity of the minimal rank matrix completion problem, which gives a complete answer to the question discussed in 1999 by Buss, Frandsen, and Shallit.

14 pages

References in corpus (6)

• Computing symmetric rank for symmetric tensors
• Eigenvectors of tensors and algorithms for Waring decomposition
• Suns-V${}_{\text{OC}}$ characteristics of high performance kesterite solar cells
• Multiarray Signal Processing: Tensor decomposition meets compressed sensing
• The complexity of computing the minimum rank of a sign pattern matrix
• Symmetric tensor decomposition

Cited by in corpus (8)

• A universality theorem for nonnegative matrix factorizations
• A note on the gap between rank and border rank
• Quantum algorithm for multivariate polynomial interpolation
• Variety Membership Testing, Algebraic Natural Proofs, and Geometric Complexity Theory
• The border support rank of two-by-two matrix multiplication is seven
• Hankel tensor decompositions and ranks
• Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits
• On tensor rank and commuting matrices