Complexity of Tensor Rank over an Infinite Field

A tensor is a generalization of vectors and matrices to higher dimensions and the rank of a tensor also generalizes the rank of a matrix. Namely, the rank of a tensor $T$ is the minimum number of rank one tensors that sum to $T$. A vector and matrix are tensors of degree 1 and 2 respectively.

The elements in $T$ come from a field $\mathbb{F}$. If $\mathbb{F}$ is finite, then Håstad proved that deciding if the rank of a degree 3 tensor is at most $r$ is NP-complete, but when $\mathbb{F}$ is an infinite field like the rationals $\mathbb{Q}$, he gives (or cites) no upper bound.

Question: What is the best known upper bound for the complexity of deciding if the rank of a degree 3 tensor $T$ over $\mathbb{Q}$ is at most $r$?

• Is the rank of a degree three tensor over ℚ the same as the rank of the same tensor over ℝ? If so, the problem can be formulated as a special case of the Existential Theory of the Reals and therefore lies in PSPACE. – Tsuyoshi Ito Aug 21 '11 at 21:05
• The idea in my previous comment will not work because the rank of a degree three tensor over ℚ is sometimes different from the rank of the same tensor over ℝ. Let {x,y} be a basis of a two-dimensional vector space, and consider the tensor 2x⊗x⊗x + x⊗y⊗y + y⊗x⊗y + y⊗y⊗x. It is not hard to see that its rank over ℝ is two but its rank over ℚ is greater than two. (This example was obtained by modifying the example showing that the rank over ℝ can be different from the rank over ℂ in Kruskal 1989.) – Tsuyoshi Ito Aug 21 '11 at 23:39
• @Tsuyoshi Ito I completely agree. I also can't find any upper bound. – Tyson Williams Aug 22 '11 at 13:47
• I think that it is better to ask computability before complexity. – Tsuyoshi Ito Aug 23 '11 at 14:26
• The trivial upperbound is that it is c.e. Håstad also proves in the same paper that the problem is $\mathsf{NP\text{-}hard}$ over $\mathbb{Q}$. The following more general problem is c.e.-complete: given a partially filled tensor, is there a completion of it that has rank $\leq r$? – Kaveh Aug 25 '11 at 17:41

There is a recent preprint about this: http://galton.uchicago.edu/~lekheng/work/np.pdf . It shows that most rank-related issues with tensors are NP hard over $\mathbb{R}$ and $\mathbb{C}$. (It also mentions that deciding the rank over $\mathbb{Q}$ is NP hard.)

• Bart, that preprint (by Hillar and Lim) is terrific ... thank you very much. – John Sidles Aug 26 '11 at 11:28
• Nice. However, I don't understand this sentence: "While Håstad’s result applies to $\mathbb{Q}$ and $\mathbb{F}_q$, these choices of fields do not make sense for all but one of the above problems (the exception being the bilinear system of equations) as these are analytic problems only well-defined over a complete field of characteristic 0 with an absolute value. Among such fields, $\mathbb{R}$ and $\mathbb{C}$ are by far the most common in applications and so we shall restrict our discussions to these fields." – Tyson Williams Aug 26 '11 at 12:33
• One of the problem being referred to in the quote above is the rank. Are these authors saying that the rank of a tensor is not well-defined over $\mathbb{Q}$? – Tyson Williams Aug 26 '11 at 12:36
• @Tyson: I think the authors just want to say that for many numerical applications (partial differential equations, signal processing), you want to do computations in $\mathbb{R}$ or $\mathbb{C}$. Being a numerical analyst myself, I don't see many applications defined on $\mathbb{Q}$. They don't imply that rank is not well-defined on $\mathbb{Q}$. – Bart Aug 27 '11 at 10:30
• Although this was really the only answer (since John meant his to be a comment), I still believe this answer deserves the bounty since it provided a reference that showed hardness over the other important infinite fields (reals and complexes). As the title of my question suggests, I am curious about infinite fields in general but decided to ask about the rationals in order to have a question with a specific answer. I will still pick another question as the accepted answer if someone can provide an upper bound (or show that it is uncomputable). – Tyson Williams Sep 14 '11 at 14:01

The book Perspectives in Computational Complexity: The Somenath Biswas Anniversary Volume published this summer (July 2014) largely agrees with the consensus that we reached here. On page 199, it says:

To the best of my knowledge, it is even not known whether [the problem of computing tensor rank] over $\mathbb{Q}$ is decidable. Over $\mathbb{R}$, the situation is somewhat better...The problem is decidable and even in PSPACE, since it can be reduced to the existential theory of the reals.

Note: The text below was intended as a comment … it definitely is not an answer, but rather a pragmatic observation that arose out of a restating of Charlie Slichter's Principles of Magnetic Resonance in the language of symplectic geometry and quantum information theory (which pulls back naturally onto polynomial-rank tensor-product state-spaces). At present we have a partial geometric understanding of these tensor-rank methods, a marginal quantum informatic understanding, essentially no complexity-theoretic or combinatoric understanding, and a working (but largely empirical) computational understanding.

We are very interested to broaden, deepen, and unify this understanding, and so we hope other folks will post further answers/comments on this subject.

Our practical computational experience has been that estimating rank over $\mathbb{C}$ is generically tractable by steepest-descent methods ... as we understand it, this robustness arises for a geometric reason, namely, the holomorphic bisectional curvature theorem of Goldberg and Kobayashi. This is far from a rigorous proof, needless to say.

• Is this theorem easy to state? If not, can you provide a link to a good statement and explanation? – Tyson Williams Aug 25 '11 at 2:08
• @Tyson: I think John is talking about his experience solving instances of the problem, and not about a theorem. – Joe Fitzsimons Aug 25 '11 at 4:35
• You asked him about a theorem, and he doesn't seem to be talking about one. I just thought you had misunderstood him. – Joe Fitzsimons Aug 25 '11 at 15:17
• Actually, I thought I had posted a comment & was surprised to see it appear as an answer. Doh! I have just now edited it to add a reference, but still it is very far from a satisfactory answer. A fine question by Tyson Williams! :) – John Sidles Aug 25 '11 at 15:23
• @Joe He mentioned the holomorphic bisectional curvature theorem of Goldberg and Kobayashi, so I asked him about it. I am not sure if that means I misunderstood him or not though. – Tyson Williams Aug 25 '11 at 17:03