<p>The book <a href="http://rads.stackoverflow.com/amzn/click/3319054457" rel="nofollow">Perspectives in Computational Complexity: The Somenath Biswas Anniversary Volume</a> published this summer (July 2014) largely agrees with the consensus that we reached here.  On <a href="http://books.google.com/books?id=U7ApBAAAQBAJ&amp;pg=PA119&amp;lpg=PA119&amp;dq=computing%20tensor%20rank%20decidable&amp;source=bl&amp;ots=d61_18XUwr&amp;sig=cuISfiGRUv4PNVTfryKTouhiTiA&amp;hl=en&amp;sa=X&amp;ei=L5hGVNm3Buny8AGeq4D4Dg&amp;ved=0CCEQ6AEwAA#v=onepage&amp;q=computing%20tensor%20rank%20decidable&amp;f=false" rel="nofollow">page 199</a>, it says:</p>

<blockquote>
  <p>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.</p>
</blockquote>

CC BY-SA 3.0
2016-12-14T15:23:39.017Z
A recent preprint also confirms this: https://arxiv.org/pdf/1612.04338v1.pdf. (See the table on page 3.)
Huck Bennett
CC BY-SA 3.0
2014-10-23T02:26:41.230Z
2014-10-23T02:26:41.230Z
Tyson Williams
<p>There is a recent preprint about this: <a href="http://galton.uchicago.edu/~lekheng/work/np.pdf">http://galton.uchicago.edu/~lekheng/work/np.pdf</a> . 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.)</p>

CC BY-SA 3.0
2011-09-14T14:01:36.527Z
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
CC BY-SA 3.0
2011-08-26T11:28:44.453Z
Bart, that preprint (by Hillar and Lim) is terrific ... thank you very much.
John Sidles
CC BY-SA 3.0
2011-08-26T12:33:57.510Z
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
CC BY-SA 3.0
2011-08-26T12:36:02.200Z
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
CC BY-SA 3.0
2011-08-27T10:30:00.630Z
@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
CC BY-SA 3.0
2011-08-27T19:50:10.573Z
It seems like the authors are referring to the concept of numerical rank? From my understanding of tensor rank, the concept of a tensor rank should be well-defined over any ring.
Cong Han
CC BY-SA 3.0
2011-08-26T09:06:27.277Z
2011-08-26T09:06:27.277Z
Bart
<p><b>Note:</b> The text below was intended as a comment&nbsp;&hellip; it definitely is <i>not</i> an answer, but rather a pragmatic observation that arose out of a <a href="http://faculty.washington.edu/sidles/FRIAS_2011/index.html#Slichter" rel="nofollow">restating of Charlie Slichter's <i>Principles of Magnetic Resonance</i></a> 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 <a href="http://faculty.washington.edu/sidles/FRIAS_2011/index.html#burningArrow" rel="nofollow">partial geometric understanding</a> 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.  </p>

<p>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. 
<hr>
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.</p>

CC BY-SA 3.0
2011-08-25T02:08:16.417Z
Is this theorem easy to state? If not, can you provide a link to a good statement and explanation?
Tyson Williams
CC BY-SA 3.0
2011-08-25T04:35:43.040Z
@Tyson: I think John is talking about his experience solving instances of the problem, and not about a theorem.
Joe Fitzsimons
CC BY-SA 3.0
2011-08-25T14:13:07.530Z
@Joe I agree. Do you have a point?
Tyson Williams
CC BY-SA 3.0
2011-08-25T15:17:14.783Z
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
CC BY-SA 3.0
2011-08-25T15:23:41.207Z
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
CC BY-SA 3.0
2011-08-25T17:03:56.727Z
@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
CC BY-SA 3.0
2011-08-25T17:19:29.587Z
@Tyson, well perhaps then I have misunderstood what you were asking.
Joe Fitzsimons
CC BY-SA 3.0
2011-08-25T00:49:23.983Z
2011-08-25T15:18:43.583Z
2011-08-25T15:18:43.583Z
John Sidles
<p>A <a href="http://en.wikipedia.org/wiki/Tensor_%28intrinsic_definition%29">tensor</a> is a generalization of vectors and matrices to higher dimensions and the <a href="http://en.wikipedia.org/wiki/Tensor_%28intrinsic_definition%29#Tensor_rank">rank</a> 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.</p>

<p>The elements in $T$ come from a field $\mathbb{F}$. If $\mathbb{F}$ is finite, then Håstad <a href="http://www.nada.kth.se/~johanh/tensorrank.pdf">proved</a> 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.</p>

<blockquote>
  <p><strong>Question:</strong> 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$?</p>
</blockquote>

CC BY-SA 3.0
2011-08-21T21:05:05.463Z
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](http://en.wikipedia.org/wiki/Existential_theory_of_the_reals) and therefore lies in PSPACE.
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-21T23:39:49.027Z
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](http://dl.acm.org/citation.cfm?id=120567).)
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-22T13:15:24.863Z
Now I wonder if this problem is even decidable or not….
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-22T13:47:57.357Z
@Tsuyoshi Ito I completely agree. I also can't find any upper bound.
Tyson Williams
CC BY-SA 3.0
2011-08-23T14:26:13.827Z
I think that it is better to ask computability before complexity.
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-25T17:41:46.463Z
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
CC BY-SA 3.0
2011-08-25T18:20:16.570Z
@Kaveh Interesting result. Is this more general result also proved in Håstad's paper or do you have a different reference?
Tyson Williams
CC BY-SA 3.0
2011-08-26T06:56:02.960Z
@Tyson, no, I don't have a reference, and it seems that the simple reasoning that I had in mind for completeness of the generalization does not work.
Kaveh
CC BY-SA 3.0
2018-01-23T00:55:57.643Z
@Tsuyoshi Ito Is it easy to see how to express tensor rank as an ETR formula?
Nikhil
<ds.algorithms><reference-request><computability><tensor-rank>
Complexity of Tensor Rank over an Infinite Field
Tyson Williams
# Complexity of Tensor Rank over an Infinite Field

(Asked by: username_0 on 2011-08-21)

A [tensor](http://en.wikipedia.org/wiki/Tensor_%28intrinsic_definition%29) is a generalization of vectors and matrices to higher dimensions and the [rank](http://en.wikipedia.org/wiki/Tensor_%28intrinsic_definition%29#Tensor_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](http://www.nada.kth.se/~johanh/tensorrank.pdf) 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$?

**Tags:** ds.algorithms, reference-request, computability, tensor-rank

> **Comments:**
> **username_1**: 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](http://en.wikipedia.org/wiki/Existential_theory_of_the_reals) and therefore lies in PSPACE.  
> **username_1**: 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](http://dl.acm.org/citation.cfm?id=120567).)  
> **username_1**: Now I wonder if this problem is even decidable or not….  
> **username_0**: @username_1 I completely agree. I also can't find any upper bound.  
> **username_1**: I think that it is better to ask computability before complexity.  
> **username_2**: 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$?  
> **username_0**: @username_2 Interesting result. Is this more general result also proved in Håstad's paper or do you have a different reference?  
> **username_2**: @Tyson, no, I don't have a reference, and it seems that the simple reasoning that I had in mind for completeness of the generalization does not work.  
> **username_3**: @username_1 Is it easy to see how to express tensor rank as an ETR formula?  

---

## 3 answers

### Answer by username_0 on 2014-10-23. Score: 4 | Accepted answer

The book [Perspectives in Computational Complexity: The Somenath Biswas Anniversary Volume](http://rads.stackoverflow.com/amzn/click/3319054457) published this summer (July 2014) largely agrees with the consensus that we reached here. On [page 199](http://books.google.com/books?id=U7ApBAAAQBAJ&pg=PA119&lpg=PA119&dq=computing%20tensor%20rank%20decidable&source=bl&ots=d61_18XUwr&sig=cuISfiGRUv4PNVTfryKTouhiTiA&hl=en&sa=X&ei=L5hGVNm3Buny8AGeq4D4Dg&ved=0CCEQ6AEwAA#v=onepage&q=computing%20tensor%20rank%20decidable&f=false), 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.

> **Comments:**
> **username_4**: A recent preprint also confirms this: https://arxiv.org/pdf/1612.04338v1.pdf. (See the table on page 3.)  

---

### Answer by username_5 on 2011-08-26. Score: 8

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

> **Comments:**
> **username_6**: username_5, that preprint (by Hillar and Lim) is terrific ... thank you very much.  
> **username_0**: 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."  
> **username_0**: 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}$?  
> **username_5**: @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}$.  
> **username_7**: It seems like the authors are referring to the concept of numerical rank? From my understanding of tensor rank, the concept of a tensor rank should be well-defined over any ring.  
> **username_0**: 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).  

---

### Answer by username_6 on 2011-08-25. Score: 2

**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*](http://faculty.washington.edu/sidles/FRIAS_2011/index.html#Slichter) 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](http://faculty.washington.edu/sidles/FRIAS_2011/index.html#burningArrow) 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.

> **Comments:**
> **username_0**: Is this theorem easy to state? If not, can you provide a link to a good statement and explanation?  
> **username_8**: @Tyson: I think John is talking about his experience solving instances of the problem, and not about a theorem.  
> **username_0**: @Joe I agree. Do you have a point?  
> **username_8**: You asked him about a theorem, and he doesn't seem to be talking about one. I just thought you had misunderstood him.  
> **username_6**: 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 username_0! :)  
> **username_0**: @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.  
> **username_8**: @Tyson, well perhaps then I have misunderstood what you were asking.  

---

