Symmetric tensors and symmetric tensor rank

Introduction

We will be interested in the decomposition of a symmetric tensor into a minimal linear combination of symmetric outer products of vectors (i.e. of the form $\mathbf{v}\otimes\mathbf{v}\otimes\dots\otimes\mathbf{v}$). We will see that a decomposition of the form

always exists for any symmetric tensor $A$ (over any field). One may regard this as a generalization of the eigenvalue decomposition for symmetric matrices to higher order symmetric tensors. In particular, this will allow us to define a notion of symmetric tensor rank (as the minimal $r$ over all such decompositions) that reduces to the matrix rank for order-$2$ symmetric tensors.

We will call (1) the symmetric outer product decomposition of the symmetric tensor $A$ and we will establish its existence in Proposition 9. This is often abbreviated as CanD in signal processing. The decomposition of a tensor into an (asymmetric) outer product of vectors and the corresponding notion of tensor rank was first introduced and studied by Frank L. Hitchcock in 1927 . This same decomposition was rediscovered in the 1970s by psychometricians in their attempts to define data analytic models that generalize factor analysis to multiway data . The name candecomp, for ‘canonical decomposition’, was used by Carrol and Chang while the name parafac, for ‘parallel factor analysis’, was used by Harshman for their respective models.

The symmetric outer product decomposition is particularly important in the process of blind identification of under-determined mixtures (UDM), i.e. linear mixtures with more inputs than observable outputs. We refer the reader to and references therein for a list of other application areas, including speech, mobile communications, machine learning, factor analysis of $k$-way arrays, biomedical engineering, psychometrics, and chemometrics.

Despite a growing interest in the symmetric decomposition of symmetric tensors, this topic has not been adequately addressed in the general literature, and even less so in the engineering literature. For several years, the alternating least squares algorithm has been used to fit data arrays to a multilinear model . Yet, the minimization of this matching error is an ill-posed problem in general, since the set of symmetric tensors of symmetric rank not more than $r$ is not closed, unless $r=1$ (see Sections 6 and 8) — a fact that parallels the illposedness discussed in . The focus of this paper is mainly on symmetric tensors. The asymmetric case will be addressed in a companion paper, and will use similar tools borrowed from algebraic geometry.

Symmetric tensors form a singularly important class of tensors. Examples where these arise include higher order derivatives of smooth functions , and moments and cumulants of random vectors . The decomposition of such symmetric tensors into simpler ones, as in the symmetric outer product decomposition, plays an important role in independent component analysis and constitutes a problem of interest in its own right. On the other hand the asymmetric version of the outer product decomposition defined in (9) is central to multiway factor analysis .

In Sections 2 and 3, we discuss some classical results in multilinear algebra and algebraic geometry . While these background materials are well-known to many pure mathematicians, we found that practitioners and applied mathematicians (in signal processing, neuroimaging, numerical analysis, optimization, etc) — for whom this paper is intended — are often unaware of these classical results. For instance, some do not realize that the classical definition of a symmetric tensor given in Definition 2 is equivalent to the requirement that the coordinate array representing the tensor be invariant under all permutations of indices, as in Definition 1. Many authors have persistently mislabeled the latter a ‘supersymmetric tensor’ (cf. ). In fact, we have found that even the classical definition of a symmetric tensor is not as well-known as it should be. We see this as an indication of the need to inform our target readership. It is our hope that the background materials presented in Sections 2 and 3 will serve such a purpose.

In this paper, we restrict our attention mostly to decompositions over the complex field. A corresponding study over the real field will require techniques rather different from those introduced here, as we will elaborate in Section 8.2.

Arrays and tensors

Unless noted otherwise, arrays with at least two indices will be denoted in uppercase; vectors are one-way arrays, and will be denoted in bold lowercase. For our purpose, only a few notations related to arrays are necessary.

For example, the outer product of two vectors, $\mathbf{u}\otimes\mathbf{v}$, is a matrix. The outer product of three vectors, or of a matrix with a vector, is a $3$-way array.

How is an array related to a tensor? Recall that a tensor is simply an element in the tensor product of vector spaces . One may easily check that the so-called Segre map

is multilinear. By the universal property of the tensor product , there exists a linear map $\theta$

When $r_{i}=n_{i}$ and $L,M,N$ are nonsingular matrices, the above multilinear map may be thought of as a change-of-bases (refer to for further discussions). We will call this map a multilinear transform of $A$.

Note that some authors denoted this contraction product as $A\times_{p}B$ or $\langle A,B\rangle_{p}$. By convention, when the contraction is between a tensor and a matrix, it is convenient to assume that the summation is always done on the second matrix index. For instance, the multilinear transform in (2) may be expressed as $A^{\prime}=A{\mathbin{\bullet}}_{1}L{\mathbin{\bullet}}_{2}M{\mathbin{\bullet}}_{3}N$. An alternative notation for (2) from the theory of group actions is $A^{\prime}=(L,M,N)\cdot A$, which may be viewed as multiplying $A$ on ‘three sides’ by the matrices $L$, $M$, and $N$ .

Symmetric arrays and symmetric tensors

We shall say that a $k$-way array is cubical if all its $k$ dimensions are identical, i.e. $n_{1}=\dots=n_{k}=n$. A cubical array will be called symmetric if its entries do not change under any permutation of its $k$ indices. Formally, if $\mathfrak{S}_{k}$ denotes the symmetric group of permutations on $\{1,\dots,k\}$, then we have

for all permutations $\sigma\in\mathfrak{S}_{k}$.

Note that given any $\sigma\in\mathfrak{S}_{k}$,

Here $\circ$ denotes the composition of the linear operators $\sigma$ and $S$.

for all $\sigma\in\mathfrak{S}_{k}$; and so $A$ is symmetric. ∎

Then since $S\sigma=S$, the term $\mathbf{e}_{i_{1}}\dotsb\mathbf{e}_{i_{k}}$ depends only on the number of times each $\mathbf{e}_{i}$ enters this product and we may write

where $p_{i}$ is the multiplicity (which may be ) of occurrence of $\mathbf{e}_{i}$ in $\mathbf{e}_{i_{1}}\dotsb\mathbf{e}_{i_{k}}$. Note that $p_{1},\dots,p_{n}$ are nonnegative integers satisfying $p_{1}+\dotsb+p_{n}=k$.

If we regard $\mathbf{e}_{j}$ in (5) as variables (i.e. indeterminates), then every symmetric tensor of order $k$ and dimension $n$ may be uniquely associated with a homogeneous polynomial of degree $k$ in $n$ variables. Recall that these are just polynomials in $n$ variables whose constituting monomials all have the same total degree $k$. Homogeneous polynomials are also called quantics and those of degrees $1$, $2$, and $3$ are often called linear forms, quadratic forms, and cubic forms (or just cubics) respectively. From now on, we will use more standard notation for the variables — $x_{j}$ instead of $\mathbf{e}_{j}$. So the monomial on the rhs of (5) now becomes $x_{1}^{p_{1}}\dotsb x_{n}^{p_{n}}$. To further simplify this notation, we will adopt the following standard multi-index notations:

where for every $\boldsymbol{j}=(j_{1},\dots,j_{k})$, one associates bijectively the nonnegative integer vector $\boldsymbol{p}(\boldsymbol{j})=(p_{1}(\boldsymbol{j}),\dots,p_{n}(\boldsymbol{j}))$ with $p_{j}(\boldsymbol{j})$ counting the number of times index $j$ appears in $\boldsymbol{j}$ . We have in particular $\lvert\boldsymbol{p}(\boldsymbol{j})\rvert=k$. The converse is true as well, and the correspondence between symmetric tensors and homogeneous polynomials is obviously bijective. Thus

This justifies the use of the Zariski topology, where the elementary closed subsets are the common zeros of a finite number of homogeneous polynomials . Note that for asymmetric tensors, the same association is not possible (although they can still be associated with polynomials via another bijection). As will be subsequently seen, this identification of symmetric tensors with homogeneous polynomials will allow us to prove some interesting facts about symmetric tensor rank.

Note that $\langle\cdot,\cdot\rangle$ cannot be an inner product in the usual sense since $\langle F,F\rangle$ is in general complex valued (recall that for an inner product, we will need $\langle F,F\rangle\geq 0$ for all $F$). However, we will show that it is a non-degenerate symmetric bilinear form.

where $\lvert\boldsymbol{p}\rvert=k$ and we see immediately that

In the special case where $G$ is the $k$th power of a linear form, we have the following lemma. The main interest in introducing this inner product lies precisely in establishing this lemma.

Let $b_{\boldsymbol{p}}=\beta_{1}^{p_{1}}\cdots\beta_{n}^{p_{n}}$ for all $\boldsymbol{p}=(p_{1},\dots,p_{n})$ such that $\lvert\boldsymbol{p}\rvert=k$. The multinomial expansion then yields

For any $F(\mathbf{x})=\sum\nolimits_{\lvert\boldsymbol{p}\rvert=k}\binom{k}{p_{1},\dots,p_{n}}a_{\boldsymbol{p}}\mathbf{x}^{\boldsymbol{p}}$,

2 Equivalence with usual definition

As mentioned earlier, we will show that a tensor is symmetric in the sense of Definition 2 if and only if its corresponding array is symmetric in the sense of Definition 1.

for all permutations $\sigma\in\mathfrak{S}_{k}$ if and only if

for all permutations $\sigma\in\mathfrak{S}_{k}$.

Hence $A$ is a symmetric tensor in the sense of Definition 2.

Since $\{\mathbf{e}_{i_{1}}\otimes\dots\otimes\mathbf{e}_{i_{k}}\mid 1\leq i_{1},\dots i_{k}\leq n\}$ is a linearly independent set, we must have

For any given $\tau\in\mathfrak{S}_{k}$, we have

Since this holds for arbitrary $\tau\in\mathfrak{S}_{k}$, the array $\llbracket a_{i_{1}\cdots i_{k}}\rrbracket$ is symmetric in the sense of Definition 1. ∎

Notions of rank for symmetric tensors

We will discuss two notions of rank for symmetric tensors — the outer product rank (defined for all tensors) and the symmetric outer product rank (defined only for symmetric tensors). We will show that under certain conditions, they are one and the same. However it is not known if they are equal on all symmetric tensors in general.

Any tensor can always be decomposed (possibly non-uniquely) as:

The tensor rank, $\operatorname*{rank}(A)$, is defined as the smallest integer $r$ such that this decomposition holds exactly . Among other properties, note that this outer product decomposition remains valid in a ring, and that an outer product decomposition of a multilinear transform of $A$ equals the multilinear transform of an outer product decomposition of $A$. In other words, if (9) is an outer product decomposition of $A$, then

is an outer product decomposition of $A{\mathbin{\bullet}}_{1}L{\mathbin{\bullet}}_{2}M{\mathbin{\bullet}}_{3}\cdots{\mathbin{\bullet}}_{k}N$, which may also be written as $(L,M,\dots,N)\cdot A$. The outer product decomposition has often been regarded synonymously as the data analytic models candecomp and parafac where the decomposition is used to analyze multiway psychometric data.

If in (9), we have $\mathbf{u}_{i}=\mathbf{v}_{i}=\dots=\mathbf{w}_{i}$ for every $i$, then we may call it a symmetric outer product decomposition, yielding a symmetric rank, $\operatorname*{rank}\nolimits_{\mathsf{S}}(A)$. Constraints other than full symmetry may be relevant in some application areas, such as partial symmetry as in indscal , or positivity/non-negativity .

The definition of symmetric rank is not vacuous because of the following result.

Lemma 9 may be viewed as a particular case of a basic result in algebraic geometry, stating that the linear space generated by points of an algebraic variety that is not included in a hyperplane, i.e. a subspace of codimension $1$, is the whole space . For completeness, a proof of our special case is given above. Note that it follows from the proof that

We will show that equality holds generically when $\operatorname*{rank}_{\mathsf{S}}(A)\leq n$ and when $k$ is sufficiently large with respect to $n$, and always holds when $\operatorname*{rank}_{\mathsf{S}}(A)=1,2$. While we do not know if the equality holds in general, we suspect that this is the case as we are unaware of any counterexample.

2 Secant varieties of the Veronese variety

3 Why rank can exceed dimension

Let $k\geq r-1$. Suppose that for some $\lambda_{1},\dots,\lambda_{r}$, $\sum\nolimits_{i=1}^{r}\lambda_{i}L_{i}^{k}=0$. Hence, by the duality property of Lemma 6,

Consider a homogeneous polynomial $F$ of degree $k\geq r-1$ that is a multiple of the product of $r-1$ linear forms $H_{i}$ vanishing at $L_{i}$ but not at $L_{r}$. We have $F(L_{r})\neq 0$ but $F(L_{j})=0$, $1\leq j\leq r-1$. As a consequence, we must have $\lambda_{r}=0$. By a similar argument, we may show that $\lambda_{i}=0$ for all $i=1,\dots,r$. It follows that the polynomials $L_{1}^{k},\dots,L_{r}^{k}$ are linearly independent. ∎

Notice that the bound $r-1$ on the degree can be reduced by $d$ if a $d$-dimensional linear space containing any $d+1$ of these points does not contain one of the other points [27, pp. 6]red. In this case, we can replace the product of $d+1$ linear forms $H_{i}$ vanishing at $d+1$ points by just $1$ linear form vanishing at these $d+1$ points.

This corollary extends results of [19, Lemma 2.2, pp. 2] and [33, Appendix]. Note that vectors $\mathbf{v}_{1},\dots,\mathbf{v}_{r}$ need not be linearly independent.

Vectors $\mathbf{v}_{1}=(1,0)$, $\mathbf{v}_{2}=(0,1)$, and $\mathbf{v}_{3}=(1,1)$, are pairwise non-collinear but linearly dependent. According to Corollary 11, the symmetric tensors $\mathbf{v}_{1}^{\otimes k},\mathbf{v}_{2}^{\otimes k},\mathbf{v}_{3}^{\otimes k}$ are linearly independent for any $k\geq 2$. Evidently, we see that this holds true for $k=2$ since the matrix below has rank $3$:

4 Genericity

Through the bijection (6), the symmetric outer product decomposition (9) of symmetric tensors can be carried over to quantics, as pointed out in . The bijection allows one to talk indifferently about the symmetric outer product decomposition of order-$k$ symmetric tensors and the decomposition of degree-$k$ quantics into a sum of linear forms raised to the $k$th power.

The special case of cubics ($k=3$) is much better known — a complete classification is known since 1964 though a constructive algorithm to compute the symmetric outer product decomposition has only been proposed recently . The simplest case of binary quantics ($n=2$) has also been known for more than two decades — a result that is used in real world engineering problems .

Rank and symmetric rank

It may seem odd that the inequalities in (12) and (11) are reversed, but there is no contradiction since the spaces are not the same.

It is then legitimate to ask oneself whether the symmetric rank and the rank are always equal. We show that this holds generically when $\operatorname*{rank}_{\mathsf{S}}(A)\leq n$ (Proposition 15) or when the order $k$ is sufficiently large relative to the dimension $n$ (Proposition 16). This always holds (not just generically) when $\operatorname*{rank}_{\mathsf{S}}(A)=1,2$ (Proposition 17). We will need some preliminary results in proving these assertions.

has $\operatorname*{rank}_{\mathsf{S}}(A)=s$.

where $\alpha_{j}=\varphi_{i}(\mathbf{z}_{j})^{k-1}$. In other words, $\mathbf{y}_{i}\in\operatorname*{span}\{\mathbf{z}_{1},\dots,\mathbf{z}_{r}\}$. Since this holds for each $i=1,\dots,s$, it implies that the $s$ linearly independent vectors $\mathbf{y}_{1},\dots,\mathbf{y}_{s}$ are contained in $\operatorname*{span}\{\mathbf{z}_{1},\dots,\mathbf{z}_{r}\}$. Hence we must have $r\geq s$. On the other hand, it is clear that $r\leq s$. Thus we must have equality. ∎

be a symmetric outer product decomposition of $A$. Then vectors of the set $\{\mathbf{y}_{1},\dots,\mathbf{y}_{s}\}$ are generically linearly independent.

Define the map from the space of $n\times s$ matrices to order-$k$ symmetric tensors,

in $\mathcal{Z}_{s}$ for which $\{\mathbf{y}_{1},\dots,\mathbf{y}_{s}\}$ is linearly dependent, i.e. $[\mathbf{y}_{1},\dots,\mathbf{y}_{s}]$ is rank deficient, is simply

Since $f$ is a polynomial map and $E_{0}$ is a non-trivial algebraic set, we conclude that $f(E_{1})$ is generic in $\mathcal{Z}_{s}$. ∎

Let $r=\operatorname*{rank}(A)$ and $s=\operatorname*{rank}_{\mathsf{S}}(A)$. So there exist decompositions

where $\alpha_{ij}=\varphi_{i}(\mathbf{x}_{j}^{(1)})\cdots\varphi_{i}(\mathbf{x}_{j}^{(k-1)})$, $j=1,\dots,r$. Since this holds for each $i=1,\dots,s$, it implies that the $s$ linearly independent vectors $\mathbf{y}_{1},\dots,\mathbf{y}_{s}$ are contained in $\operatorname*{span}\{\mathbf{x}_{1}^{(k)},\dots,\mathbf{x}_{r}^{(k)}\}$. Hence we must have $r\geq s$. On the other hand, it is clear that $r\leq s$. Thus we must have equality. ∎

We will see below that we could have $\operatorname*{rank}(A)=\operatorname*{rank}_{\mathsf{S}}(A)$ even when the constituting vectors $\mathbf{y}_{1},\dots,\mathbf{y}_{s}$ are not linearly independent. The authors would like to thank David Gross for his help in correcting an error in the original proof.

satisfies $\operatorname*{rank}(A)=\operatorname*{rank}_{\mathsf{S}}(A)$ generically.

Let $r=\operatorname*{rank}(A)$ and $s=\operatorname*{rank}_{\mathsf{S}}(A)$. So there exist decompositions

Contracting both sides of (15) in the first $k/2$ modes with $\Phi_{i}$, we get

where $\alpha_{ij}=\Phi_{i}(\mathbf{x}_{j}^{(1)}\otimes\dots\otimes\mathbf{x}_{j}^{(k/2)})$, $j=1,\dots,r$. Since this holds for each $i=1,\dots,s$, it implies that the $s$ linearly independent vectors $\mathbf{y}_{1}^{\otimes k/2},\dots,\mathbf{y}_{s}^{\otimes k/2}$ are contained in $\operatorname*{span}\{\mathbf{x}_{1}^{(k/2+1)}\otimes\dots\otimes\mathbf{x}_{1}^{(k)},\dots,\mathbf{x}_{r}^{(k/2+1)}\otimes\dots\otimes\mathbf{x}_{r}^{(k)}\}$. Hence we must have $r\geq s$. On the other hand, it is clear that $r\leq s$. Thus we must have equality. ∎

If $\operatorname*{rank}_{\mathsf{S}}(A)=1$, then $\operatorname*{rank}(A)=1$ clearly. If $\operatorname*{rank}_{\mathsf{S}}(A)=2$, then

for any $\beta=(1+\alpha^{k})^{1/k}$, contradicting $\operatorname*{rank}_{\mathsf{S}}(A)=2$. It follows from the argument in the proof of Proposition 15 with $s=2$ that $\operatorname*{rank}(A)=2$. ∎

The following result will be useful later.

It is not hard to check that the symmetric tensor in (16) is associated with the quantic $p(z_{1},z_{2})=z_{1}z_{2}^{k-1}$, up to a constant multiplicative factor (where $z_{1},z_{2}$ are the first two coordinate variables in $(z_{1},\dots,z_{n})$).

To prove that this quantic is of symmetric rank $k$, we are going to show that $p(z_{1},z_{2})$ can be decomposed into a sum of powers of linear forms as

There are infinitely many possibilities of choosing coefficients $(\alpha_{i},\beta_{i})$ but we just need to provide one solution. Take $\alpha_{1}=\dots=\alpha_{r}=1$ and $\beta_{1},\dots,\beta_{k}$ distinct such that

First we express all quantics in terms of the canonical basis scaled by the binomial coefficients:

In this basis, the monomial $kz_{1}z_{2}^{k-1}$ can be represented by a $(k+1)$-dimensional vector containing only one non-zero entry. The quantic $(z_{i}+\beta_{i}z_{2})^{k}$ is then represented by the vector

The existence of coefficients $\lambda_{1},\dots,\lambda_{k}$ such that we have the decomposition (17) is equivalent to the vanishing of the $(k+1)\times(k+1)$ determinant

An explicit computation shows that this determinant is $\pm(\sum\nolimits_{i=1}^{k}\beta_{i})V_{k}(\beta_{1},\dots,\beta_{k})$ where $V_{k}(\beta_{1},\dots,\beta_{k})$ is the Vandermonde determinant of degree $k-1$ of $\beta_{1},\dots,\beta_{k}$. Thus by (18), the determinant in (19) vanishes.

This proves that the symmetric rank of $z_{1}z_{2}^{k}$ is $\leq k$. Note that the symmetric rank cannot be smaller than $k$ because removing any row of the matrix of (19) still yields a matrix of rank $k$, if the $\beta_{i}$ are distinct (see also Proposition 10). ∎

This proof is constructive, and gives an algorithm to compute a symmetric outer product decomposition of any binary symmetric tensor of the form (16). For example, the reader can check out that the decompositions below may be obtained this way.

The quantics $48z_{1}^{3}z_{2}$ and $60z_{1}^{4}z_{2}$ are associated with the symmetric tensors of maximal rank $A_{31}$ and $A_{41}$ respectively. Their symmetric outer product decompositions are given by

The maximal symmetric rank achievable by symmetric tensors of order $k$ and dimension $n=2$ is $k$, i.e. $R_{\mathsf{S}}(k,2)=k$. One can say that such symmetric tensors lie on a tangent line to the Veronese variety of symmetric rank-$1$ tensors. In , an algorithm has been proposed to decompose binary forms when their rank is not larger than $k/2$; however, this algorithm would not have found the decompositions above since the symmetric ranks of $A_{31}$ and $A_{41}$ exceed $4/2$ and $5/2$ respectively.

Generic symmetric rank and typical symmetric ranks

The quantities $\overline{R}_{\mathsf{S}}(k,n)$ and $R_{\mathsf{S}}(k,n)$ may now be formally defined by

An integer $r$ is not a typical rank if $\mathcal{Z}_{r}$ has zero volume, which means that $\mathcal{Z}_{r}$ is contained in a non-trivial closed set. This definition is somewhat unsatisfactory since any mention of ‘volume’ necessarily involves a choice of measure, which is really irrelevant here. A better definition is as follows.

The varieties $\overline{\mathcal{Z}}_{r}$ can be ordered by inclusion as follows. If

Before proving this proposition, we first state two preliminary results. Recall that an algebraic variety is irreducible if it cannot be decomposed as the union of proper subvarieties (cf. [27, pp. 51] and [48, pp. 34]). In algebraic geometry, it is known that the secant varieties of any irreducible variety are irreducible. Nevertheless, we will give a short proof of the following lemma for the sake of completeness.

The sets $\overline{\mathcal{Y}}_{r}$, $r\geq 1$, are irreducible algebraic varieties.

For $r\geq 1$, the variety $\overline{\mathcal{Y}}_{r}$ is the closure of the image $\mathcal{Y}_{r}$ of the map

Consider now two polynomials $f,g$ such that $fg\equiv 0$ on $\overline{\mathcal{Y}}_{r}$. As $\overline{\mathcal{Y}}_{r}$ is the Zariski closure of $\mathcal{Y}_{r}$, this is equivalent to $fg\equiv 0$ on $\mathcal{Y}_{r}$ or

Thus either $f\equiv 0$ or $g\equiv 0$ on $\mathcal{Y}_{r}$ or equivalently on $\overline{\mathcal{Y}}_{r}$, which proves that $\overline{\mathcal{Y}}_{r}$ is an irreducible variety. For more details on properties of parameterized varieties, see . See also the proof of for third order tensors. ∎

We have $\overline{R}_{\mathsf{S}}=\min\{r\mid\overline{\mathcal{Y}}_{r}=\overline{\mathcal{Y}}_{r+1}\}$.

Suppose that there exists $r<\overline{R}_{\mathsf{S}}$ such that $\overline{\mathcal{Y}}_{r}=\overline{\mathcal{Y}}_{r+1}$. Then since $\overline{\mathcal{Y}}_{r}\subseteq\overline{\mathcal{Y}}_{r}+\mathcal{Y}_{1}\subseteq\overline{\mathcal{Y}}_{r+1}=\overline{\mathcal{Y}}_{r}$, we have

We are now in a position to prove Proposition 21.

Proof of Proposition 21. By Lemma 23, we deduce that for $r<\overline{R}_{\mathsf{S}}$,

As $\overline{\mathcal{Y}}_{r}$ is an irreducible variety, we have $\dim(\overline{\mathcal{Y}}_{r})<\dim(\overline{\mathcal{Y}}_{r+1})$. As $\mathcal{Y}_{r}\cup\mathcal{Z}_{r+1}=\mathcal{Y}_{r+1}$, we deduce that

which implies by the irreducibility of $\overline{\mathcal{Y}}_{r+1}$, that $\overline{\mathcal{Z}}_{r+1}=\overline{\mathcal{Y}}_{r+1}$. Consequently, for $r_{1}<r_{2}<\overline{R}_{\mathsf{S}}$, we have

If $1\leq r\leq R_{\mathsf{S}}$, then $\mathcal{Z}_{r}\neq\overline{\mathcal{Z}}_{r}$.

Let $r>1$ and $A\in\mathcal{Z}_{r}$. Then by definition of $\mathcal{Y}_{r}$, there exists $A_{0}\in\mathcal{Y}_{r-1}$ and $A_{1}\in\mathcal{Y}_{1}$ such that $A=A_{0}+A_{1}$. As $A_{0}\not\in\mathcal{Y}_{r-2}$ (otherwise $A\in\mathcal{Y}_{r-1}$) we have $A_{0}\in\mathcal{Z}_{r-1}$. For $\varepsilon\neq 0$, define $A_{\varepsilon}=A_{0}+\varepsilon A_{1}$. We have that $A_{\varepsilon}\in\mathcal{Z}_{r}$, for all $\varepsilon\neq 0$, and $\lim_{\varepsilon\rightarrow 0}A_{\varepsilon}=A_{0}$. This shows that $A_{0}\in\overline{\mathcal{Z}}_{r}-\mathcal{Z}_{r}$, and consequently that $\mathcal{Z}_{r}\neq\overline{\mathcal{Z}}_{r}$. ∎

The above proposition is about the set of symmetric tensors of symmetric rank exactly $r$. But what about those of symmetric rank at most $r$? While $\mathcal{Y}_{1}$ is closed as a determinantal variety, we will see from Examples 25 and 26 as well as Proposition 27 that $\mathcal{Y}_{r}$ is generally not closed for $r>1$. This is another major difference from matrices, for which all $\mathcal{Y}_{r}$ are closed sets.

In dimension $n\geq 2$, and for any order $k>2$, $\mathcal{Y}_{2}$ is not closed. In fact, take two independent vectors $\mathbf{x}_{i}$ and $\mathbf{x}_{j}$ and define the sequence of symmetric tensors

For any $\varepsilon\neq 0$, $A_{\varepsilon}(i,j)$ is of symmetric rank $2$, but converges in the limit as $\varepsilon\to 0$ to a symmetric tensor of symmetric rank $k$. In fact, the limiting symmetric tensor is easily seen to be a sum of $k$ rank-$1$ tensors,

which has symmetric rank $k$ by Proposition 18.

Let $n=3$ and $k=3$. Then $\mathcal{Y}_{5}\subset\overline{\mathcal{Y}}_{3}$, whereas $3<\overline{R}_{\mathsf{S}}$. In fact, take the symmetric tensor associated with the ternary cubic $p(x,y,z)=x^{2}y-xz^{2}$. According to , this tensor has rank $5$. On the other hand, it is the limit of the sequence $p_{\varepsilon}(x,y,z)=x^{2}y-xz^{2}+\varepsilon z^{3}$ as $\varepsilon$ tends to zero. According to a result in , the latter polynomial is associated with a rank-$3$ tensor since the determinant of its Hessian is equal to $8x^{2}(x-3\varepsilon z)$ and hence contains two distinct linear forms as long as $\varepsilon\neq 0$.

It is easy to show that this lack of closeness extends in general to $r>\overline{R}_{\mathsf{S}}$ or for $r\leq n$, as stated in the two propositions below.

If $\overline{R}_{\mathsf{S}}<r$, then for all $k>2$, $\mathcal{Y}_{r}\neq\overline{\mathcal{Y}}_{r}$.

If $1<r\leq n$, then for any $k>2$, $\mathcal{Y}_{r}\neq\overline{\mathcal{Y}}_{r}$.

Take $n$ linearly independent vectors $\mathbf{x}_{1},\dots,\mathbf{x}_{n}$. Then the symmetric tensors $\mathbf{x}_{1}^{\otimes k},\dots,\mathbf{x}_{n}^{\otimes k}$ are linearly independent as well, and $\sum\nolimits_{i=1}^{r}\mathbf{x}_{i}^{\otimes k}$ is of symmetric rank $r$ for every $r\leq n$ by Lemma 13. Now for $r>2$ and any $\varepsilon\neq 0$, define the symmetric tensor

$A_{\varepsilon}$ is again of symmetric rank $r$ for every $\varepsilon\neq 0$, but tends to a symmetric rank $r+1$ tensor (see also Section 8.1). For $r=2$, the same reasoning applies with

This shows that $\mathcal{Y}_{r}$ is not closed. ∎

Based on these two propositions, we conjecture the stronger statement that for order $k>2$, the set of symmetric tensors of symmetric rank at most $r$ is never closed, even for $r=n+1,\dots,R_{\mathsf{S}}-1$.

Assume $k>2$ and $n\geq 2$. Then $\mathcal{Y}_{r}\neq\overline{\mathcal{Y}}_{r}$ for any $r$ such that $1<r<R_{\mathsf{S}}$.

Up to this point, our study has been based on the Zariski topology . However it is useful from a practical point of view to be able to apply these results to other topologies, for example, the Euclidean topology. Since the $\mathcal{Y}_{r}$’s are parameterized and are thus algebraic constructible sets , and since the closure of an algebraic constructible set for the Euclidean topology and the Zariski topology are the same, the results in this paper holds true for many other topologies. We have in particular the following result.

Values of the generic symmetric rank

In practice, it would be useful to be able to compute the symmetric rank of any given symmetric tensor, or at least to know the maximal values of the symmetric rank, given its order and dimensions. Unfortunately, these questions are far from resolved.

The corresponding problem for the generic values of the symmetric rank, however, has seen enormous progress due to the work of Alexander and Hirschowitz described in Section 7.1. In fact, even before their breakthrough, bounds on the generic symmetric rank have been known for decades :

It is known that the lower bound is often accurate but the upper bound is not tight . Furthermore, exact results are known in the case of binary quantics ($n=2$) and ternary cubics ($k=3$) .

It was not until the work of Alexander and Hirschowitz in 1995 that the generic symmetric rank problem was completely settled. Nevertheless, the relevance of their result has remained largely unknown in the applied and computational mathematics communities. One reason is that the connection between our problem and the interpolating polynomials discussed in is not at all well-known in the aforementioned circles. So for the convenience of our readers, we will state the result of Alexander and Hirschowitz in the context of the symmetric outer product decomposition below.

except for the following cases: $(k,n)\in\{(3,5),(4,3),(4,4),(4,5)\}$, where it should be increased by $1$.

This theorem is extremely complicated to prove, and the interested reader should refer to the two papers of Alexander and Hirschowitz . Simplifications to this proof have also been recently proposed in . It is worth noting that these results have been proved in terms of multivariate polynomials and interpolation theory, and not in terms of symmetric tensors. The exception $(k,n)=(4,3)$ has been known since 1860; in fact, Sylvester referred to it as Clebsh Theorem in his work . It is not hard to guess the formula in (21) by a degrees-of-freedom argument. The difficulty of proving Theorem 31 lies in establishing the fact that the four given exceptions to the expected formula (21) are the only ones. Table 1 below lists a few values of the generic symmetric rank.

2 Uniqueness

Besides the exceptions pointed out in Theorem 31, the number of solutions for the symmetric outer product decomposition has to be finite if the rank $r$ is smaller than or equal to $\frac{1}{n}\binom{n+k-1}{k}$. This occurs for instance for all cases of degree $k=5$ in Table 1, except for $n=5$ and $n=10$. Hence we may deduce the following:

Then (22) has a finite number of solutions if and only if

Actually, one may easily check the generic dimension of the fiber of solutions by computing the number of remaining free parameters :

This is summarized in Table 2. When the dimension of the fiber is non-zero, there are infinitely many symmetric outer product decompositions.

Our technique is different from the reduction to simplicity proposed by ten Berge et al. , but also relies on the calculation of dimensionality.

Examples

We will present a few examples to illustrate our discussions in the previous sections.

It has been shown that symmetric tensors of order $3$ and dimension $3$ have a generic rank $\overline{R}_{\mathsf{S}}(3,3)=4$ and a maximal rank $R_{\mathsf{S}}(3,3)=5$. From the results of Section 6, this means that only $\mathcal{Z}_{4}$ is dense in $\overline{\mathcal{Y}}_{4}=\overline{\mathcal{Y}}_{5}$, and that $\mathcal{Z}_{3}$ and $\mathcal{Z}_{5}$ are not closed by Proposition 24. On the other hand, $\mathcal{Z}_{1}$ is closed.

In order to make this statement even more explicit, let us now define a sequence of symmetric tensors, each of symmetric rank $2$, that converges to a symmetric tensor of symmetric rank $3$. This will be a simple demonstration of the lack of closure of $\mathcal{Y}_{r}$ for $r>1$ and $k>2$, already stated in Proposition 27. For this purpose, let $\mathbf{x},\mathbf{y}$ be two non-collinear vectors. Then the following order-$3$ symmetric tensor is of symmetric rank $2$ for any scalar $\varepsilon\neq 0$:

and it converges, as $\varepsilon\to 0$, to the following symmetric tensor:

This limiting symmetric tensor is of symmetric rank $3$. In fact, one may show that it admits the following symmetric outer product decomposition:

Now let $\mathbf{x}_{i},\mathbf{y}_{i}$ be linearly independent vectors.

By adding two terms of the form (23), a similar example can be given in dimension $n=4$, where we get a sequence of symmetric tensors of symmetric rank $4$ converging to a limit of symmetric rank $6$.

We will give two more illustrations of Conjecture 29.

If the dimension is $n=3$, we can take three linearly independent vectors, say $\mathbf{x}$, $\mathbf{y}$, and $\mathbf{z}$. Then the sequence of symmetric tensors $A_{\varepsilon}+\mathbf{z}^{\otimes 3}$ is of symmetric rank $3$ and converges towards a symmetric rank-$4$ tensor.

In dimension $3$, it is somewhat more tricky to build a sequence converging towards a symmetric tensor of symmetric rank $5$. Note that $5$ is the maximal rank for $k=3$ and $n=3$.

Consider the sequence below as $\varepsilon$ tends to zero:

It converges to the following symmetric tensor, which we expressed as a sum of six (asymmetric) rank-$1$ terms,

This has symmetric rank $5$ since it can be associated with quantic $x^{2}y+xz^{2}$, which is the sum of (at least) five cubes.

In terms of algebraic geometry, this example admits a simple geometric interpretation. The limiting tensor is the sum of a point in the tangent space to $\mathcal{Y}_{1}$ at $\mathbf{x}^{\mathbin{\otimes}3}$ and a point in the tangent space to $\mathcal{Y}_{1}$ at $\mathbf{z}^{\mathbin{\otimes}3}$.

Note that the same kind of example can be constructed in the asymmetric case:

Further discussions of the lack of closeness of $\mathcal{Y}_{r}$ and the ill-posedness of the best rank-$r$ approximation problem in the asymmetric case can be found in .

2 Symmetric outer product decomposition over the real field

This inequality also holds true for the outer product rank of asymmetric tensors. For $k=2$, i.e. matrices, we always have equality in (26) but we will see in the examples below that strict inequality can occur when $k>2$.

For asymmetric tensors, the same kind of computer simulation would yield (by generating $8$ independent real Gaussian entries) typical ranks of $2$ and $3$, $78$% and $22$% of the time, respectively, leading to the same qualitative conclusions. This procedure is not new [53, pp. 13] and has already been proposed in the past to illustrate the existence of several typical ranks for asymmetric tensors . An interesting result obtained by ten Berge is that $p\times p\times 2$ real asymmetric tensors have typical ranks $\{p,p+1\}$.

The problems pertaining to rank and decompositions of real symmetric tensors have not received as much attention as their complex counterparts. However, a moderate amount of work has been done and we refer the reader to these for further information.

3 Open questions

Most of the results that we have presented so far are limited to symmetric tensors over the complex field. The case of general asymmetric tensors is currently being addressed with the same kind of approach. As pointed out earlier, decompositions over the real field are more complicated to handle with algebraic geometric tools. In addition, while the problem of determining the generic symmetric rank has been resolved thanks to the Alexander-Hirschowitz Theorem, the maximal symmetric rank is known only for particular values of order and dimensions (e.g. dimension $2$); only very rough upper bounds are known for general values. Lastly, the computation of an explicit symmetric outer product decomposition for a symmetric tensor is computationally expensive, and the conditions (dimension, order) under which this can be executed within a polynomial time are not yet clearly known. These are problems that we hope will be addressed in future work, either by ourselves or interested readers.

Acknowledgements

The authors would like to thank the anonymous reviewers for their helpful comments. This work is a result of collaboration initiated in the 2004 Workshop on Tensor Decomposition held at the American Institute of Mathematics, Palo Alto, CA, and continued in the 2005 Workshop on Tensor Decomposition and its Applications held at the Centre International de Rencontres Mathématiques (CIRM), Luminy, France. The work of B. Mourrain and P. Comon has been partially supported by the contract ANR-06-BLAN-0074 “Decotes”. The work of G.H. Golub has been partially supported by the grant CCF 0430617 from the National Science Foundation. The work of L.-H. Lim has been partially supported by the grant DMS 0101364 from the National Science Foundation, and by the Gerald J. Lieberman Fellowship from Stanford University.

References