4
$\begingroup$

Write $R(T)$ for the rank of an order-$3$ tensor $T \in \mathbb C^{m \times n \times p}$ over the complex numbers. If $T' \in \mathbb {C}^{m' \times n' \times p'}$ is another such tensor then let $T \otimes T' \in \mathbb{C}^{mm' \times nn' \times pp'}$ denote their tensor product (aka Kronecker product). It is straightforward to verify that $R(T \otimes T') \le R(T) R(T')$, and from this it follows that the sequence $R(T^k)^{1/k}$ converges to its infimum. The asymptotic rank of $T$ is $$\tilde R(T) = \lim_{k \to \infty} R(T^k)^{1/k} = \inf_{k \ge 1} R(T^k)^{1/k}.$$

For example, if $T = m_2$ is the structure tensor for $2 \times 2$ matrix multiplication then $\tilde R(T) = 2^\omega$ where $\omega$ is the exponent of matrix multiplication. It would therefore be putting it mildly to say that $\tilde R(T)$ is not easy to calculate.

My question is actually about the border rank of tensors. The literature agrees universally that this is denoted $\underline R(T)$, but seems to vary wildly on what it's actual definition is. Here are some possibilities:

  1. According to some sources, including Wikipedia, border rank is the minimal $r$ such that $T$ is a limit of tensors of rank at most $r$. Let's call this $\underline R^\text{naive}$. Wikipedia has a basic example of a tensor with $R(T) = 3$ but $\underline R^\text{naive}(T) = 2$.

  2. That cannot possibly be the "right" definition for an arbitrary field since there is no natural topology in general. I have seen at least one source therefore define border rank to be the least $r$ such that $T$ is in the Zariski closure of the set of tensors of rank at most $r$. Call this $\underline{R}^\text{Zariski}$.

  3. Most of the literature that actually carefully defines and proves things (such as the book Algebraic Complexity Theory, Chapter 15) defines border rank in terms of algebraic expressions over $\mathbb C[\epsilon]$ of the type $\epsilon^d T + O(\epsilon^{d+1}) = (\text{rank-$r$ tensor})$ for some integer $d$. Let's call this definition $\underline R^\text{original}(T)$.

Note that $\underline R^\text{Zariski} \le \underline R^\text{naive} \le \underline R^\text{original}$.

Question 1: Are these things really different? What are good examples?

Anyway, the crucial inequality relating border rank (at least in its original definition) to asymptotic rank is $\tilde R(T) \le \underline R^\text{original}(T)$. However, it seems to be implicit in some of the more recent literature that this holds for $R^\text{naive}$ (see for example the intro to https://arxiv.org/abs/1112.6007). Is this true?

Question 2: Is it true that $\tilde R \le \underline R^\text{naive}$?

Of course, we could ask the same question for $\underline R^\text{Zariski}$, which would be even better.

$\endgroup$
2
  • $\begingroup$ ... $R$ is a limit of tensors of rank at most $r$ - you mean, $T$ is a limit? $\endgroup$ Feb 22 at 20:48
  • $\begingroup$ @FedorPetrov Yes, thanks $\endgroup$ Feb 23 at 9:03

1 Answer 1

7
$\begingroup$

It is true that over $\mathbb{C}$ (and over every algebraically closed field) we have $\underline{R}^{\mathrm{Zariski}}(T) = \underline{R}^{\mathrm{original}}(T)$.

The standard reference is the doctoral thesis of Alder "Grenzrang und Grenzkomplexität aus algebraischer und topologischer Sicht", but it is not accessible. A proof is also available in §20.6 of the book "Algebraic complexity theory" by Bürgisser, Clausen, Shokrollahi, and a stronger statement can be found in the following paper: T. Lehmkuhl, T. Lickteig. "On the order of approximation in approximative triadic decompositions of tensors". Theor. Comp. Sci. 66(1):1–14.

The idea is that the set $X_r$ of tensors of rank at most $r$ is constructible and therefore contains a subset $Y_r$ open in the Zariski closure $\overline{X}_r$. If $x \in \overline{X}_r \setminus X_r$, then, taking an intersection of $\overline{X}_r$ with a general affine subspace of appropriate dimension containing $x$, we can get an algebraic curve $C \subset \overline{X}_r$ such that $x \in C$ and $C \cap Y_r$ is open in $C$. Then we take a normalization of this curve to get rid of possible singularity at $x$, which gives a local parametrization of $C$ at $x$ equivalent to the required expression with $\varepsilon$.

$\endgroup$
1
  • $\begingroup$ Wonderful, thank you! $\endgroup$ Feb 23 at 9:35

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.