23
$\begingroup$

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$?

Improve this question
$\endgroup$
9
  • 4
    $\begingroup$ 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. $\endgroup$
    – Tsuyoshi Ito
    Commented Aug 21, 2011 at 21:05
  • 8
    $\begingroup$ 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.) $\endgroup$
    – Tsuyoshi Ito
    Commented Aug 21, 2011 at 23:39
  • 1
    $\begingroup$ @Tsuyoshi Ito I completely agree. I also can't find any upper bound. $\endgroup$
    – Tyson Williams
    Commented Aug 22, 2011 at 13:47
  • 2
    $\begingroup$ I think that it is better to ask computability before complexity. $\endgroup$
    – Tsuyoshi Ito
    Commented Aug 23, 2011 at 14:26
  • 1
    $\begingroup$ 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$? $\endgroup$
    – Kaveh
    Commented Aug 25, 2011 at 17:41

3 Answers 3

Reset to default
8
+50
$\begingroup$

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

Improve this answer
$\endgroup$
6
  • $\begingroup$ Bart, that preprint (by Hillar and Lim) is terrific ... thank you very much. $\endgroup$
    – John Sidles
    Commented Aug 26, 2011 at 11:28
  • 2
    $\begingroup$ 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." $\endgroup$
    – Tyson Williams
    Commented Aug 26, 2011 at 12:33
  • 2
    $\begingroup$ 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}$? $\endgroup$
    – Tyson Williams
    Commented Aug 26, 2011 at 12:36
  • $\begingroup$ @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}$. $\endgroup$
    – Bart
    Commented Aug 27, 2011 at 10:30
  • 1
    $\begingroup$ 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). $\endgroup$
    – Tyson Williams
    Commented Sep 14, 2011 at 14:01
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
2
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ Is this theorem easy to state? If not, can you provide a link to a good statement and explanation? $\endgroup$
    – Tyson Williams
    Commented Aug 25, 2011 at 2:08
  • 1
    $\begingroup$ @Tyson: I think John is talking about his experience solving instances of the problem, and not about a theorem. $\endgroup$
    – Joe Fitzsimons
    Commented Aug 25, 2011 at 4:35
  • 1
    $\begingroup$ You asked him about a theorem, and he doesn't seem to be talking about one. I just thought you had misunderstood him. $\endgroup$
    – Joe Fitzsimons
    Commented Aug 25, 2011 at 15:17
  • 2
    $\begingroup$ 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! :) $\endgroup$
    – John Sidles
    Commented Aug 25, 2011 at 15:23
  • 1
    $\begingroup$ @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. $\endgroup$
    – Tyson Williams
    Commented Aug 25, 2011 at 17:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.