11
$\begingroup$

Consider a tensor product

$ V^{\otimes n} = \underbrace{V\otimes\cdots\otimes V}_{n} $

where $V$ is a vector space over $\mathbb R$, $\dim V = m$ , hence $\dim V^{\otimes n} = m^n$ .

So every $A \in V^{\otimes n}$ can be represented as

$A = \sum_{i=1}^r a^i_1 \otimes a^i_2 \ldots \otimes a^i_n, \;\;\; a_i \in V $

in a non-unique way. Taking $R$ to be minimum $r$ among all the possible decompositions of A.

$R = \min \left \{ r : A = \sum_{i=1}^r a^i_1 \otimes a^i_2 \ldots \otimes a^i_n, \;\;\; a_i \in V \right \}$

How many tensors have certain $R$ ? How many tensors have $R=1$? Or $R = m^n$ ? What is the typical $R$ (mean, median mean, the most probable), what is the distribution?

IMPORTANT How should I imagine (picture) tensors for which $R$ is (near) maximum? What hinders them from decomposition?

Maybe there are some experimental data. I'm mostly interested in high $m$'s and $n$'s, though every answer is welcome.

  • 1
    @Noah Stein: Thank you. It seems, I have blundered.2012-02-14

2 Answers 2

5

If $V$ would have been a vector space over $\mathbb C$ instead, there is only one value of $R$ where the set of tensors having rank $R$ has non-zero (Lebesgue) measure (this single value of $R$ is called the generic rank). As Yrogirg says, this $R$ is expected to be $\left\lceil \frac{m^n}{mn - m + 1}\right\rceil.$ However, this is not always the case. For example, over $\mathbb C^3 \otimes \mathbb C^3 \otimes \mathbb C^3$ the generic rank is 5.

Over $\mathbb R$ the situation is more complicated and we can have multiple values of $R$ where the set of tensors having rank $R$ has non-zero measure. These $R$ are called typical ranks. For example, in $\mathbb R^2 \otimes \mathbb R^2 \otimes \mathbb R^2$ both 2 and 3 are typical ranks (and 3 is the maximal rank). Of course, in the case of $\mathbb R^n \otimes \mathbb R^n$ the single typical rank is $n$.

Determining the typical ranks for tensors over $\mathbb R$ is an open question, and it's mostly third order tensors which have been studied. A way of determining the minimal typical rank over $\mathbb R$ numerically is described in P. Comon, J.M.F. ten Berge, L. De Lathauwer, J.Castaing (2009), Generic and typical ranks of multi-way arrays, Linear Algebra and its Applications, 430, 2997-3007.

2

Well, I've found some sort of conjecture/rule of thumb, that the "expected rank" for both (?) complex and real tensors is almost everywhere $\frac{m^n}{mn - m + 1}$ At least that's how I understood it. It seems that this estimation could be obtained rather trivially, just by counting the number of degrees of freedom, but I couldn't understand that $-m+1\;$ part.

Check "Tensor Decompositions, Alternating Least Squares and other Tales." by P. Comon, X. Luciani and A. L. F. de Almeida for the details. In addition, it is a good starting to point for people interested in tensor decomposition and Comon's webpage features software (MATLAB codes) for tensor decomposition.