7
$\begingroup$

This question is related to a previous unanswered question of mine. Please see that question for background.

When Håstad proved that computing tensor rank is NP-complete, the rank in question was allowed to be part of the input. Specifically, given a Boolean formula with $n$ variables and $m$ clauses, Håstad constructed a tensor that has rank exactly $4n+2m$ if the formula is satisfiable and has some larger rank otherwise.

What if we fix the bound on the rank to some constant? For example...

What is the complexity of deciding if a tensor has rank at most 3?

The tensor should be defined over an infinite field, otherwise the problem is trivial (...only a finite number of things to check). Answers for the natural infinite fields $\mathbb{Q}$, $\mathbb{R}$, and $\mathbb{C}$ would be best. I am personally interested in this question using the complex numbers.

$\endgroup$
7
$\begingroup$

Testing for constant border-rank can be done in polynomial-time, I'm pretty sure, if you're talking about tensors of fixed arity. More precisely, testing for border-rank $\leq r$ in $\mathbb{C}^{d_1} \otimes \dotsb \otimes \mathbb{C}^{d_k}$ can be done in something like $k(d_1 d_2 \dotsb d_k)^{2(r+1)}$ evaluations of $(r+1) \times (r+1)$ determinants plus some additional constant work (constant depending on $r$).

Theorem 3.7.1.1 of Landsberg's tensor book ("Inheritance") says that the equations for the variety of tensors of border-rank $\leq r$ in $\mathbb{C}^{d_1} \otimes \mathbb{C}^{d_2} \otimes \dotsb \otimes \mathbb{C}^{d_k}$ are given by the equations for border-rank $r$ in $\mathbb{C}^r \otimes \mathbb{C}^r \otimes \dotsb \otimes \mathbb{C}^r$ together with all $(r+1) \times (r+1)$ minors of flattenings. Since $r = O(1)$, there are only finitely many equations of the former type.

Border-rank 1 = rank 1, and more generally rank $\leq r$ implies border-rank $\leq r$. But border-rank 2 can have rank anywhere from $2$ to the arity $k$, and border-rank $3$ in arity 3 can have ranks 3, 4, or 5. Beyond that I don't know about testing for rank.

$\endgroup$
  • $\begingroup$ Yes, fixed arity. This book looks great. The naive system of polynomial equations to check for rank at most $r$ (for arity $k$ and $d = d_1 = \dotsb d_k$) has $d r$ variables in $d^k$ equations, each of degree $k$ with $r$ monomials. Are the equations for the variety of tensors of border-rank $\le r$ significantly simpler than this? $\endgroup$ – Tyson Williams Oct 25 '13 at 21:53
  • $\begingroup$ If you're talking about the naive equations you get by expressing a variable rank-r tensor and then setting it = to your tensor $T$, then there's a key difference. In that setting, you setup a system of equations that depend on $T$, and then check if the system has a solution. In the equations for border-rank I was talking about, you simply plug the coordinates of your tensor into the equations and make sure they all evaluate to zero. For fixed $r$ and $k$, the only equations that aren't of O(1) size are determinants, so are easy to evaluate. $\endgroup$ – Joshua Grochow Oct 26 '13 at 15:07
  • $\begingroup$ Note: checking if a system of equations over $\mathbb{Z}$ has a solution in $\mathbb{C}$ is in PSPACE unconditionally and in PH assuming the generalized Riemann hypothesis. In the Blum-Shub-Smale model (or even the usual Boolean model, if working over finite fields), solving systems of equations is NP-complete. So this seems much harder than merely evaluating equations, as in the case of border-rank. $\endgroup$ – Joshua Grochow Oct 26 '13 at 15:09
  • $\begingroup$ For others reading this question, the first two chapters of Landsberg's book are available online. $\endgroup$ – Tyson Williams Oct 30 '13 at 20:09
  • $\begingroup$ Oh, the "naive system of polynomials" I spoke about in my first comment is for checking symmetric (aka Waring) rank. $\endgroup$ – Tyson Williams Nov 1 '13 at 1:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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