Symmetric tensor decomposition

Question

Let $T$ be an order-$k$, rank-$m$ symmetric tensor, that is, $T=\sum_{j=1}^m v_j\otimes v_j \otimes \cdots \otimes v_j$, where the Segre outer product is taken $k$ times, with $v_j\in\mathbb{R}^d$ for all $j$. That is to say, for every $i_1,\dots,i_k\in\{1,2,\dots,d\}$, it holds that, $T_{i_1,\dots,i_k}=\sum_{j=1}^m v_{ji_1}v_{ji_2}\cdots v_{ji_k}$.

My question is as follows.

1) Given a $T$, that is known to be symmetric and order $k$, can such a decomposition be found, with the same rank?

2) Assume, the same rank condition is removed. Can such a decomposition be found? That is, are there $v_1',\dots,v_M'\in\mathbb{R}^d$, such that, $\sum_{j=1}^M v_i'\otimes v_i' \otimes \cdots \otimes v_i'$ where the outer product is $k$ times can be found?

3) How about uniqueness? Under what conditions on $m$ and $d$, we can say the recovery is unique?

Answer 1

A recent introduction is Carlini, et al, Four lectures on secant varieties. Adam mentioned Landsberg, Tensors: Geometry and Applications.

In brief:

1(a). If $T$ is a symmetric tensor of tensor rank $m$, does $T$ have a symmetric decomposition with $m$ terms?

Probably not. If $T$ is symmetric and has rank $m$, it may not be the case that there exists a symmetric decomposition with $m$ terms. In the lingo, the symmetric rank of a symmetric tensor may not be equal to the rank; this is known to happen over $\mathbb{C}$, and expected (at least by me) to also happen over $\mathbb{R}$. See Waring rank vs tensor rank of symmetric tensors?, https://mathoverflow.net/a/322467/88133.

1(b). Suppose that $T$ is a symmetric tensor with both tensor rank and symmetric tensor rank equal to $m$. In this case, is it possible to find, in some sense, a symmetric decomposition with $m$ terms? That is, is there some algorithm or numerical method to find an $m$ term symmetric decomposition?

Yes and no. There are algorithms and methods. First of all, there is simple brute force: just write $T = v_1^{\otimes k} + \dotsb + v_m^{\otimes k}$, and solve for the entries of the $v_i$, using methods such as Gröbner bases. Certainly this is quite inefficient, but it counts as a method. There are better methods. See for example Brachat, et al, Symmetric tensor decomposition. There are quite a few more recent papers that refer to that one. You can use MathSciNet to find them. Some of them are iterative and numerical, others are exact (if the tensor $T$ was given exactly).

2. Can some symmetric decomposition be found?

Yes, a symmetric decomposition can be found, by polarization identities. I will describe a wildly non-minimal symmetric decomposition. Finding a minimal symmetric decomposition is a huge problem---see the algorithms discussed above; and even in the "theoretical" approach, it's still difficult.

The polarization identities, or at least one version, are the identities $$ v_1 \cdot \dotsm \cdot v_k = \frac{1}{2^{k-1}} \sum \pm (v_1 \pm \dotsb \pm v_k)^{\otimes k}, $$ where $\cdot$ is the symmetric tensor product (sum over all permutations), the sum is taken over all $2^{k-1}$ choices of $\pm$ coefficients inside the parentheses, and the coefficient in front of the parentheses is the product of the ones inside. For example, $$ v_1 \cdot v_2 = v_1 \otimes v_2 + v_2 \otimes v_1 = \frac{1}{2}((v_1+v_2)^{\otimes 2} - (v_1 - v_2)^{\otimes 2}), $$ and $$ \begin{split} v_1 \cdot v_2 \cdot v_3 &= v_1 \otimes v_2 \otimes v_3 + v_1 \otimes v_3 \otimes v_2 + \dotsb + v_3 \otimes v_2 \otimes v_1 \\ &= \frac{1}{4}((v_1+v_2+v_3)^{\otimes 3}-(v_1+v_2-v_3)^{\otimes 3}-(v_1-v_2+v_3)^{\otimes 3} \\ &\qquad \qquad +(v_1-v_2-v_3)^{\otimes 3}). \\ \end{split} $$ These hold for all $v_i$, even if they are linearly dependent, or even equal (although if $v_1=v_2$, say, then terms like $(v_1-v_2+\dotsb)$ will certainly simplify). So every symmetric tensor can be decomposed "term by term". This is explicit.

Even for a single term (symmetric product) the above decomposition is usually not minimal. A minimal decomposition over $\mathbb{C}$ is described in Buczynska, et al, Waring decompositions of monomials. But that's just for monomials; beyond that, practically everything is open. Even for binomials, nobody knows the answer. Over $\mathbb{R}$, even the monomial case is open, see Carlini, et al, On the real rank of monomials. As Adam said in the comments, these are very complicated questions and not much is known!

On MathOverflow, see Efficient way to express a symmetric tensor in terms of rank one elements; Generalization of the Polarisation Formula for Symmetric Bilinear Forms to Symmetric multilinear Forms; polarization formula for homogeneous polynomials; and more, if you search (in fact, if you browse through my answers, I think a lot of them are on this topic).

3. How about uniqueness?

A (symmetric) tensor is called identifiable if it has a unique shortest decomposition (uniqueness up to permuting terms and rescaling factors in terms). Mella and Galuppi-Mella have recently solved the problem of identifiability of general symmetric tensors. There are other results, e.g., identifiability of "most" tensors of less than generic rank, or identifiability over the reals versus identifiability over the complex numbers. There is a well-known Kruskal's criterion for identifiability (which you can find by searching).