Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
"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
2  
@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
1  
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
5  
@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
1  
@Noah Stein: Thank you. It seems, I have blundered. –  Christian Blatter Feb 14 '12 at 9:20

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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