# Tensor Decomposition

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.

-
"How many tensors"? Are you thinking about finite fields, or do you have a specific measure on $V$ in mind? –  Zhen Lin Feb 13 '12 at 19:35
@Yrogirg: You need a finite measure to be able to do anything resembling probability. Unfortunately, the Lebesgue measure is not a finite measure. You can either restrict the coefficients to a suitable subset of $\mathbb{R}$ with finite measure, or change to a finite measure, e.g. the normal distribution. –  Zhen Lin Feb 13 '12 at 20:07
This is not a probability question but a question in algebraic geometry. With probability $1$ a random tensor has $r=$ the maximal possible value. –  Christian Blatter Feb 13 '12 at 20:38
@ChristianBlatter: This is true for matrices, but for tensors over $\mathbb{R}$ there is not necessarily a single generic rank. See for example "Exact probabilities for typical ranks of $2\times 2\times 2$ and $3\times 3\times 2$ tensors by Göran Bergqvist. Apparently a $2\times 2\times 2$ tensor has rank $2$ with probability $\frac{\pi}{4}$ and rank $3$ with probability $1-\frac{\pi}{4}$ if the entries are i.i.d. standard normal random variables. –  Noah Stein Feb 13 '12 at 21:57
@Noah Stein: Thank you. It seems, I have blundered. –  Christian Blatter Feb 14 '12 at 9:20

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 $$\lceil \frac{m^n}{mn - m + 1}\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.

-

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.

-