REFINED METHODS FOR THE IDENTIFIABILITY OF TENSORS

CRISTIANO BOCCI, LUCA CHIANTINI, AND GIORGIO OTTAVIANI

Abstract. We prove that the general tensor of size 2^{n} and rank k has a unique decomposition as the sum of decomposable tensors if k ≤ 0.9997 \frac{2^{n}}{n+1} (the constant 1 being the optimal value). Similarly, the general tensor of size 3^{n} and rank k has a unique decomposition as the sum of decomposable tensors if k ≤ 0.998 \frac{3^{n}}{2n+1} (the constant 1 being the optimal value).

Some results of this flavor are obtained for tensors of any size, but the explicit bounds obtained are weaker.

1. Introduction

We are interested in the problem to decompose a tensor in ℂ^{a_{1}+1} ⊗…⊗ℂ^{a_{q}+1} as a sum of decomposable tensors. We study the decomposition of the general tensor of given rank k. Conditions which guarantee the uniqueness of this decomposition are quite important in the applications [KB09]. Indeed, many decomposition algorithms converge to one decomposition, so that a uniqueness result guarantees that the decomposition found is the one we looked for. Even from a purely theoretical point of view, the study of the decomposition shows some beautiful and not expected phenomena. After a look at the table in section 7, we see that there are some exceptional sporadic cases which are intriguing.

It is well known that when k is bigger that the critical value

k_{c} := \frac{∏_{i=1}^{q}(a_{i} + 1)}{1 + ∑_{i=1}^{q} a_{i}}

then the decomposition can never be unique (see the introduction of [BC12]). Only one case is known when k_{c} is an integer and there is a unique decomposition for tensors of rank equal to k_{c}, namely when q = 3 and a_{1} = 1, a_{2} = a_{3}.

So, let us consider the range k < k_{c}, where the problem can be understood better.

Indeed, we consider two different cases, where the behavior is quite different. Let us order the numbers a_{i}, so that a_{1} ≤ … ≤ a_{q}. The first case is when a_{q} ≥ ∏_{i=1}^{q−1}(a_{i}+1)−(∑_{i=1}^{q−1} a_{i}), that is when the last dimension is much bigger with respect to the others. In this case there are always values of k < k_{c} such that the general tensor of rank k has a not unique decomposition. This case is completely described, see Corollary 8.4.

The second remaining case is when a_{q} ≤ ∏_{i=1}^{q−1}(a_{i} + 1) − (1 + ∑_{i=1}^{q−1} a_{i}). We believe in this case that the decomposition is almost always unique (for k < k_{c}), with the exception of few cases which we list in section 7 and have been studied in previous papers [BC12, CO12, CMO13]. Further references can be found in [CO12]. In general, we believe that the aforementioned list of exceptional cases is complete.

We illustrate some situations, where our analysis cover almost all the possible ranks.

In the case of many copies of ℙ^{1}, we prove (Theorem 4.4) that the general tensor of rank ≤ \frac{4095}{4096}k_{c} has a unique decomposition. Notice that \frac{4095}{4096} = 0.9997 …, so we are very close to cover the range k ≤ k_{c}.

In the case of many copies of ℙ^{2}, we prove (Theorem 5.3) that the general tensor of rank ≤ \frac{728}{729}k_{c} has a unique decomposition. Notice that \frac{728}{729} = 0.998 . . .. A similar result for many copies of ℙ^{3} is listed in the same section.

To give some evidence to our guess, that only a small set of exceptional cases occur, in the range a_{q} ≤ ∏_{i=1}^{q−1}(a_{i} + 1) − (1 + ∑_{i=1}^{q−1} a_{i}), we have implemented an algorithm that uses the concept of weak defectivity [CC02]. With respect to the algorithm implemented in [CO12], it is much faster, because it reduces the problem to numerical linear algebra operation, while the algorithm in [CO12] needed Gröbner basis computations.

We can prove that the list of exceptional cases, appearing at the end of section 7 is complete for all (a_{1}, …, a_{q}) such that ∏_{i=1}^{q}(a_{i} + 1) ≤ 100 (see Theorem 7.5).

Our general technique goes back to the seminal paper of Strassen [Str83], and we owe a lot to his point of view. Strassen proved the case c even of our Theorem 6.1, which provides a starting point for general results on cubic and general tensors (Theorem 7.1 and Theorem 7.2).

In fact, we point out that our technique is inductive: once we know that a particular Segre product X of projective spaces satisfies the k-tangency condition in Lemma 3.1, and consequently is k-identifiable for k ≤ αk_{c}, where α is some positive real ≤ 1, then the same happens to be true for a larger product X × ℙ^{a}.

This principle, which is indeed our main tool in the paper, is enlightened in Corollary 3.3. We hope that it will produce even more interesting results, when applied to specific types of tensors that people working in Multilinear Algebra are considering.

A consequence of this technique is a result on the dimension of secant varieties (Corollary 7.3), which can be seen as a generalization, to any number of factors, of previously known results in the case of three factors.

Let we finish with a short account of the status of the art, for the identifiability of binary tensors, i.e. tensors in the span of ℙ^{1} × ⋯ × ℙ^{1}. After the paper of Strassen [Str83], and using methods of Algebraic Geometry, Elmore, Hall and Neeman proved in [EHN05] the following asymptotic result: when the number m of factors is “very large” with respect to k, a, then the Segre product ℙ^{a} × ⋯ × ℙ^{a} is k-identifiable. A much more precise bound for identifiability of binary products was obtained by Allman, Matias and Rhodes. In [AMR09] (Corollary 5) they proved that the product of m copies of ℙ^{1} is k-identifiable when m > 2⌈log_{2}(k + 1)⌉ + 1. Thus, they gave a lower bound for 2^{m} which is quadratic with respect to k +1. Successively, using Geometric methods as well as a result by Catalisano, Gimigliano and Geramita ([CGG11]), the first and second authors, in [BC12] improved the bound, showing that a product of m > 5 copies of ℙ^{1} is k-identifiable for all k such that k + 1 ≤ 2^{m−1}/m. The case of 5 copies of ℙ^{1} was shown to be exceptional. The bound, which happened to be the best known up to now, is substantially improved in the present paper.

2. Preliminaries

We follow [Land] for basic facts about the geometric point of view on tensors. For any irreducible projective varieties X, we denote by S_{k}(X) the k-th secant variety of X, which is the Zariski closure of the set ⋃_{x_{1},...,x_{k}∈X}⟨x_{1}, …, x_{k}⟩. In other words, S_{k}(X) is the Zariski closure of the set of elements having X-rank equal to k.

We recall, from [CO12] Definition 2.1, the following:

Definition 2.1. X is called k-identifiable if the general element of S_{k}(X) has a unique decomposition as the sum of k elements of X.

Those who wonder why we ask for the uniqueness just for a general element of S_{k}(X), should consider that for any k ≥ 2 there are always points of S_{k}(X) which have rank smaller than k.

Notice that k-identifiable implies (k − 1)-identifiable, and so on.

A fundamental Geometric tool for the analysis of the identifiability of tensors, is Proposition 2.4 in [CO12], which is essentially a consequence of Terracini Lemma.

Proposition 2.2. If there exists a set of k particular points x_{1}, … x_{k} ∈ X, such that the span ⟨𝕋_{x_{1}}X, …, 𝕋_{x_{k}}X⟩ contains 𝕋_{x}X only if x = x_{i} for some i = 1, … k, then X is k-identifiable.

3. The Main Lemma

The inductive step, that allows us to provide effective results on the identifiability of tensors, relies in the following:

Lemma 3.1. Let X be a smooth non-degenerate projective subvariety of ℙ^{N}, of dimension n. Let Y denote the canonical Segre embedding of X × ℙ^{m} into ℙ^{M}, M = mN + m + N. Fix k with (n + 1)k < N + 1 and r < N such that r + 1 ≥ (n + m + 1)k. Assume that a general linear subspace of ℙ^{N}, of dimension r, which is tangent to X at k general points, is not tangent to X elsewhere.

Then the general linear subspace of ℙ^{M}, of dimension mr + m + r, which is tangent to Y at (m + 1)k general points, is not tangent to Y elsewhere.

Proof. First of all, notice that dim(Y) = (m + n), and (m + 1)(r + 1) ≥ (m + n + 1)(m + 1)k. Thus, by an obvious parameter count, there are linear subspaces of dimension mr + m + r which are tangent to Y at (m + 1)k general points.

Fix m + 1 independent points p_{0}, …, p_{m} of ℙ^{m} and for j = 0, …, m take k general points q_{ij} of the fiber X × {p_{j}}. Call π_{j} the natural projection of X × {p_{j}} to X.

For h = 0, …, m, fix a general linear subspace R_{h}, of dimension r, which is tangent to X × {p_{h}} at the k points q_{1h}, …, q_{kh} and passes through the points π_{j}(q_{ij})×{p_{h}}, for j ≠ h. Since r+1 ≥ k(n+1)+km, such spaces R_{h} exist. Moreover R_{h} it is tangent to X × {p_{h}} only at the point q_{1h}, …, q_{kh}, by our assumption on X.

Let R be the span of all the R_{h}’s. We claim that R, which is a linear subspace of dimension mr + m + r, is tangent to Y at all the points q_{ij}, and it is not tangent to Y elsewhere. This will conclude the proof of the lemma, by semicontinuity.

First notice that for all i, j, R contains m + 1 general points of {π_{j}(q_{ij})} × ℙ^{m}, hence it contains these fibers. Since R also contains the tangent spaces to X ×{p_{h}} at the points q_{ih}’s for all h, then it is tangent to Y at all the points q_{ij}’s.

Assume now that there exists a point x ∈ Y, different from the q_{ih}’s, such that R is tangent to Y at x. Call x′ the projection of x to ℙ^{m}, so that in some coordinate system, we can write x′ = a_{0}p_{0} + ⋯ + a_{m}p_{m}. There is at least one of the a_{i}’s, say a_{0}, which is non-zero. Assume that also a_{1} ≠ 0. Then, the projection of R to ℙ^{N} × {p_{0}}, which by construction coincides with R_{0}, is also tangent to X × {p_{0}} at the projection of q_{k1}. By the generality of the choice of the q_{ij}’s, q_{k1} cannot coincide with any of the points q_{10}, …, q_{k0}. Thus we get a contradiction.

So, we conclude that a_{1} = 0. Similarly we get that a_{2} = ⋯ = a_{m} = 0. It follows that x = x′ belongs to X × {p_{0}} and since R_{0} is tangent to X × {p_{0}} at x, then x must coincide with some point q_{i0}. □

Remark 3.2. It is worthy of spending one Remark to point out that, by semicontinuity, if a general linear subspace of ℙ^{N}, of dimension r, which is tangent to X at k general points, is not tangent to X elsewhere, then the same phenomenon occurs for general linear subspaces of dimension r − 1, r − 2, and so on.

The Lemma, together with Theorem 2.2, produces the following general principle:

Corollary 3.3. With the same assumptions on X of Lemma 3.1, then Y = X ×ℙ^{m} is (m + 1)k-identifiable.

Thus we will prove the identifiability of Segre products, starting with a X who is a Segre product for which we know that the assumptions of Lemma 3.1 hold (by computer-aided specific computations or by Theorem 6.1 below) and then extending the number of factors of X, and using Lemma 3.1 inductively.

4. Many copies of ℙ^{1}

The main case in which the previous result applies is the Segre product of many projective lines.

Proposition 4.1. Let X be the product of n copies of ℙ^{1}, 6 ≤ n ≤ 12, naturally embedded in ℙ^{2^{n}−1}. Then for k < k_{c} = \frac{2^{n}}{n+1} the linear span of k general tangent spaces at X, is not tangent to X elsewhere. In particular X is k-identifiable for all k < k_{c}.

Proof. Just a computer-aided computation, following the the algorithm presented in section 9. In the case of 12 copies, the algorithm goes out of memory if implemented in a straightforward way. We used a “divide and conquer” technique to save memory, running in 2 hours on a PC with two processors at 2GHz. □

Theorem 4.2. For n ≥ 12, let X be the product of n copies of ℙ^{1}, naturally embedded in ℙ^{N}, with N = 2^{n} − 1. Then for r < 2^{n} − 2^{n−12} and for k ≤ \frac{r+1}{n+1}, a general linear subspace of dimension r which is tangent to X at k points, is not tangent to X elsewhere.

Proof. The proof goes by induction on n ≥ 12. If n = 12, the claim follows from the previous Proposition and Remark 3.2.

Assume the claim holds for n − 1. Again by Remark 3.2, it suffices to prove the claim for r + 1 = 2^{n} − 2^{n−12}. Fix k as above. Notice that k′ := ⌈k/2⌉ is at most (2^{n−1} − 2^{n−13})/(n + 1) + 1, which is smaller than (2^{n−1} − 2^{n−13})/n for n ≥ 12. Thus we may apply induction: the general linear subspace of P^{N′}, N′ := 2^{n−1} − 1, of dimension (2^{n−1} − 2^{n−13}) − 1, which is tangent to X′ := (ℙ^{1})^{n−1} at k′ points, is not tangent to X′ elsewhere. The claim now follows directly from the Main Lemma 3.1. □

Remark 4.3. The assumption n ≥ 6 is motivated by the fact that for 5 copies of ℙ^{1}, X is k-identifiable if and only if k ≤ 4, while the general tensor of rank 5 has exactly two decompositions [BC12].

We recall that for 4 copies of ℙ^{1}, X is k-identifiable if and only if k ≤ 2, while it is a result of Strassen that the general tensor of rank 3 has infinitely many decompositions.

For 3 copies of ℙ^{1}, X is k-identifiable if and only if k ≤ 2, 2 being the general rank.

As a corollary, we get

Theorem 4.4. For n ≥ 12, let X be the product of n copies of ℙ^{1}, naturally embedded in ℙ^{N}, with N = 2^{n} − 1. Then for k ≤ (2^{n} − 2^{n−12})/(n + 1), X is k-identifiable.

Let us compare the result with the (best known) bound on the identifiability of ℙ^{1} × ⋯ × ℙ^{1} given in [BC12], which makes a fundamental use of the main result in [CGG11].

The main result of [BC12] proves that X is k-identifiable for k < 2^{n−1}/n, which is a little better than half way from the critical (maximal) value k_{c}.

The previous result shows that X is k-identifiable for

k ≤ \frac{2^{n}}{n + 1}(1 − \frac{1}{2^{12}} ) = \frac{4095}{4096} \frac{2^{n}}{n + 1} = 0, 9997 . . . · k_{c}

a sensible improvement, as n grows.

5. Many copies of ℙ^{2} and ℙ^{3}

Let us see what happens with the Segre product of many projective planes.

Proposition 5.1. Let X be the product of n copies of ℙ^{2}, 4 ≤ n ≤ 6, naturally embedded in ℙ^{3^{n}−1}. Then for k < k_{c} = \frac{2^{n}}{n+1} the linear span of k general tangent spaces at X, is not tangent to X elsewhere. In particular X is k-identifiable for all k < k_{c}.

Proof. Just a computer-aided computation, following the the algorithm presented in section 9. □

Remark 5.2. The assumption n ≥ 4 is motivated by the fact that for 3 copies of ℙ^{2}, X is k-identifiable if and only if k ≤ 3, while it is a result of Strassen ([Str83] §4) that the general tensor of rank 4 has infinitely many decompositions.

Theorem 5.3. For n ≥ 6, let X be the product of n copies of ℙ^{2}, naturally embedded in ℙ^{N}, with N = 3^{n} − 1. Then for r < 3^{n} − 3^{n−6} and for k ≤ (r + 1)/(2n + 1), a general linear subspace of dimension r which is tangent to X at k points, is not tangent to X elsewhere.

Proof. The proof goes by induction on n ≥ 6. If n = 6, the claim follows from the previous proposition and Remark 3.2.

Assume n ≥ 7 and the claim holds for n − 1. Again by Remark 3.2, it suffices to prove the claim for r + 1 = 3^{n} − 3^{n−6}. Fix k as above. Notice that k′ := ⌈k/3⌉ is at most (3^{n−1} − 3^{n−7})/(2n + 1) + 1, which is smaller than (3^{n−1} − 3^{n−7})/(2n − 1) for n ≥ 5. Thus we may apply induction: the general linear subspace of P^{N′}, N′ := 3^{n−1} − 1, of dimension (3^{n−1} − 3^{n−7}) − 1, which is tangent to X′ := (ℙ^{2})^{n−1} at k′ points, is not tangent to X′ elsewhere. The claim now follows directly from the Main Lemma 3.1. □

As a corollary, we get

Theorem 5.4. For n ≥ 6, let X be the product of n copies of ℙ^{2}, naturally embedded in ℙ^{N}, with N = 3^{n} − 1. Then for k ≤ (3^{n} − 3^{n−6})/(2n + 1), X is k-identifiable.

The previous result shows that X is k-identifiable for

k ≤ \frac{3^{n}}{2n + 1}(1 − \frac{1}{3^{6}} ) = \frac{728}{729} \frac{3^{n}}{2n + 1},

i.e. up to 728/729 = 0.998 … of the critical (maximal) value k_{c}.

And now the reader can see how the trick goes, at least for cubic tensors. Once one determines a starting point, for few copies of given projective spaces (e.g. by using a computer-aided computation), then the Main Lemma 3.1 provides an extension to the product of an arbitrary number of copies of projective spaces, in which the bound is expressed as a constant fraction of the critical value k_{c}.

We end the list of particular cases with the product of many copies of ℙ^{3}, which is relevant because of its connection with the Algebraic Statistics of DNA chains.

Theorem 5.5. Let X be the product of n ≥ 5 copies of ℙ^{3}, naturally embedded in ℙ^{N}, with N = 4^{n} − 1.

(i) for n = 5, a general linear subspace of dimension r = 1007 which is tangent to X at k ≤ 63 points, is not tangent to X elsewhere.

(ii) For n > 5 and k ≤ (4^{n} − 4^{n−3})/(3n + 1), a general linear subspace of dimension r = 4^{n} − 4^{n−3} − 1 which is tangent to X at k points, is not tangent to X elsewhere.

(iii) For k ≤ (4^{n} − 4^{n−3})/(3n + 1), then X is k-identifiable. In other words, X is k-identifiable up to 63/64 = 0.98 … of the critical (maximal) value k_{c}.

Proof. (i) follows from a computer-aided computation, following the the algorithm presented in section 9. (ii) is a consequence of (i) and the inductive Lemma 3.1. (iii) follows from (ii) and Theorem 2.2. □

6. Products of three projective spaces

For the general case, in which we have projective spaces of arbitrary dimension, in order to produce examples similar to the ones of the previous section, we need a starting point for the induction.

We obtain a starting point, for the case of the product of three projective spaces X = ℙ^{a} × ℙ^{b} × ℙ^{c}, 2 < a ≤ b ≤ c, from the following Theorem, which is due to Strassen in the case c odd (see [Str83], Corollary 3.7), and we generalize to any c.

Our proof is apparently independent from the argument given by Strassen. Indeed, following correctly the details of the steps, one realizes that the two arguments are essentially equivalent.

Theorem 6.1. Let X be the product of three projective spaces X = ℙ^{a} × ℙ^{b} × ℙ^{c}, 2 < a ≤ b ≤ c, naturally embedded in ℙ^{N}, with N = (a + 1)(b + 1)(c + 1) − 1. Then a general linear subspace L of codimension a + b + 2 in ℙ^{N}, that contains the span of the tangent spaces to X at k general points, with:

k≤\frac{(a + 1)(b + 1)(c + 1)}{a + b + c + 1} − c − 1,

is not tangent to X elsewhere.

Proof. Let ℙ^{c} = ℙ(C), where C is a vector space of dimension c + 1. Fix one vector v_{0} ∈ C and split C in a direct sum C = ⟨v_{0}⟩ ⊕ C′, where C′ is a supplementary subspace of dimension c. From the geometric point of view, this is equivalent to split the product X in two products

X′ = ℙ^{a} × ℙ^{b} × ℙ^{c−1} and X′′ = ℙ^{a} × ℙ^{b} × {P_{0}} = ℙ^{a} × ℙ^{b}.

Fix general points P_{1}, …, P_{k} ∈ X′, with P_{i} = v_{i} ⊗ w_{i} ⊗ u_{i} and let Q_{1}, …, Q_{k}, Q_{i} = v_{i} ⊗ w_{i}, be the corresponding points of X′′. The linear span of the Q_{i}’s is a space of dimension k − 1 in ℙ^{N′′}, where N′′ = ab + a + b.

By assumption k − 1≤N′′ − dim(X′′) = N′′ − a − b. Indeed if c + 1 ≥ a + b then

k − 1 ≤ \frac{(a + 1)(b + 1)(c + 1)}{a + b + c + 1} − a − b − 1 ≤ (a + 1)(b + 1) − a − b − 1.

If c + 1 < a + b then k < (a + 1)(b + 1)/2 and (a + 1)(b + 1)/2 > a + b.

Fix a linear space L′′ of codimension a + b + 1 in ℙ^{N′′}, which contains the span of the Q_{i}’s. Since the points Q_{i}’s are general in X′′, it follows from the Theorem 2.6 in [CC06] (it is a generalization of the “trisecant lemma”) that the linear space L′′ does not meet X′′ in other points. Moreover L′′ is not tangent to X′′ at any of the points Q_{i}’s.

Let L′ be a hyperplane in ℙ^{N′}, N′ = (a + 1)(b + 1)c − 1, which is tangent to X′ at the points P_{i}’s. The hyperplane L′ exists, since by assumption

k(dim(X′) + 1) < (a + 1)(b + 1)(c + 1) − c(a + b + c) < N − 1.

Let L be the linear span of L′ and L′′. L has codimension a + b + 2 and it is tangent to X at the k points P_{1}, …, P_{k}, since it contains the tangent spaces to X′ at the P_{i}’s, moreover it contains the points Q_{i}’s, so it contains the fiber ℙ^{c} passing through each P_{i}.

We want to exclude that L is tangent to X at any other point P ≠ P_{i}. Call Q the projection of P to X′′. If L is tangent to X at P, then it must contain the fiber ℙ^{c} passing through P, thus it contains Q. This proves that Q is one of the Q_{i}’s (say Q = Q_{1}), since L does not meet X′′ elsewhere. But then L contains the fibers ℙ^{a} and ℙ^{b} at two points P, P_{1} with the same projection to X′′. Thus it contains these fibers at any point of the line ℓ joining P, P_{1}. As ℓ contains Q_{1}, we get a contradiction, since L′′ = L ∩ ℙ^{N′′} is not tangent to X′′ at Q_{1}. □

Corollary 6.2. Let X be the product of three projective spaces X = ℙ^{a} × ℙ^{b} × ℙ^{c}, 2 < a ≤ b ≤ c, naturally embedded in ℙ^{N}, with N = (a + 1)(b + 1)(c + 1) − 1. Then for

k≤\frac{(a + 1)(b + 1)(c + 1)}{a + b + c + 1} − c − 1,

X is k-identifiable.

Proof. Follows immediately from the previous Theorem and [CO12]. □

The identifiability of products of three projective spaces has been studied by a long list of authors, who refined the celebrated Kruskal’s bound for arbitrary tensors. We mention De Lauthawer’s results for unbalanced tensor ([Lat06]), and the general bounds found by the second and third authors in [CO12].

We believe that the bound of Corollary 6.2, at least for some balanced case, is the best known result for tensors of type a, b, c.

7. Inductive bounds for the identifiability of general tensors

The same procedure we used for products of many projective lines and planes, based on the bound found in Corollary 6.2, can produce results for cubic tensors, which, in some cases, are far beyond any known result on the identifiability problem.

Then, with the above notation, we have:

Theorem 7.1. For n ≥ 3, let X be the product of n copies of ℙ^{a}, naturally embedded in ℙ^{N}, with N = (a + 1)^{n} − 1. Then for r < (a + 1)^{n} − (3a + 1)(a + 1)^{n−2} and for k ≤ (r + 1)/(an + 1), a general linear subspace of dimension r which is tangent to X at k points, is not tangent to X elsewhere.

As a consequence, we get that X is k-identifiable, for

k ≤ \frac{(a + 1)^{n} − (3a + 1)(a + 1)^{n−2}}{an + 1} .

Proof. The proof is absolutely similar to the ones of the cases a = 1, 2, 3 given above. We may assume a ≥ 4. It goes by induction on n ≥ 3, and uses Theorem 6.1 as a starting point.

We leave the straightforward details to the reader. □

We recall that we defined, in the introduction, the critical value

k_{c} = \frac{∏_{i=1}^{q}(a_{i} + 1)}{1 + ∑_{i=1}^{q} a_{i}}

which is essentially the maximum for which k-identifiability can hold. Then the previous bound proves that X is k-identifiable, for

k≤\frac{a(a − 1)}{(a + 1)^{2}} k_{c}.

Even for the case of rectangular tensors, we are able to prove some results, using the same procedure.

Theorem 7.2. Let X be the product of q ≥ 3 projective spaces X = ℙ^{a_{1}} ×⋯×ℙ^{a_{q}}, naturally embedded in ℙ^{N}, with N = −1 + Π_{i=1}^{q}(a_{i} + 1). Then for

r < Π_{i=1}^{q}(a_{i}+1)−(a_{1}+a_{2}+a_{3}+1)Π_{i=3}^{q}(a_{i}+1) and for k ≤ (r+1)/(1+∑_{i=1}^{q} a_{i}), a general linear subspace of dimension r which is tangent to X at k points, is not tangent to X elsewhere.

As a consequence, we get that X is k-identifiable, for

k ≤ \frac{Π_{i=1}^{q}(a_{i} + 1) − (a_{1} + a_{2} + a_{3} + 1)Π_{i=3}^{q}(a_{i} + 1)}{1 + ∑_{i=1}^{q} a_{i}}.

Again, notice that we get k-identifiability for

k≤\frac{a_{1}a_{2} − a_{3}}{(a_{1} + 1)(a_{2} + 1)} k_{c}.

Of course, the previous bound changes if one reorders the a_{i} suitably. Notice that the previous thereom requires a_{1}a_{2} > a_{3} in order to give a an effective range of values for k. Moreover, one of the conditions among a_{1} ≫ a_{3}, a_{2} ≫ a_{3} and a_{1}a_{2} ≫ a_{3} is strongly preferable to have a larger range of values for k.

We strongly believe that some ad hoc procedure, as well as the improvements of our computational facilities, for the starting point of the induction, are suitable to produce advancement in the inequalities of our results.

Let us stress that the previous bounds provide also some answers to the problem of finding the dimension of secant varieties to Segre varieties (i.e. to the dimension of paces of tensors of given rank).

Corollary 7.3. Let X be the product of q ≥ 3 projective spaces X = ℙ^{a_{1}} ×⋯×ℙ^{a_{q}}. If

k ≤ \frac{Π_{i=1}^{q}(a_{i} + 1) − (a_{1} + a_{2} + a_{3} + 1)Π_{i=3}^{q}(a_{i} + 1)}{1 + ∑_{i=1}^{q} a_{i}}

then the dimension of the k-secant variety S_{k}(X) is the expected one, namely it is equal to k(1 + ∑_{i=1}^{q} a_{i}) − 1.

Remark 7.4. One should compare the previous result with the result of Gesmundo, [Ges12], Theor. 1.1, who proved that the dimension of k-secant variety to ℙ^{a_{1}} × … × ℙ^{a_{q}} is the expected one for k ≤ Θ_{q}k_{c}, where Θ_{q} is a constant depending only on q. Moreover, in the case where a_{i} +1 are powers of 2, then Θ_{q} → 1 when q → ∞.

Next, we show a list of Segre products for which k-identifiability does not hold. We refer to section 5 of [CO12] for further details.

Table of known cases when a_{q} ≤ ∏_{i=1}^{q−1}(a_{i} + 1) − (1 + ∑_{i=1}^{q−1} a_{i}) and the decomposition of the general tensor of rank k < k_{c} is not unique.

(a_{1}, …, a_{q})  k  number of decompositions
(2, 3, 3)  5  ∞^{1}
(2, b, b) b even \frac{3b+2}{2} ∞^{\frac{b}{2} +1}
(1, 1, n, n)  2n + 1 ∞^{1}
(3, 3, 3)  6  2
(2, 5, 5)  8  finite, ≥ 6
(1, 1, 1, 1, 1)  5  2

A straightforward application of the algorithm presented in the last section shows the following

Theorem 7.5. The previous list is complete for all (a_{1}, …, a_{q}) such that ∏_{i=1}^{q}(a_{i}+ 1) ≤ 100.

8. The unbalanced case

Consider again X = ℙ^{a_{1}} × ⋯ × ℙ^{a_{q}} be a Segre product, canonically embedded in ℙ^{N}, where N + 1 = ∏_{i=1}^{q}(a_{i} + 1). We may assume a_{1} ≤ … ≤ a_{q} and q ≥ 3.

When the dimension of a_{q} is much bigger than the dimension of the other factors, then the tensor decomposition has a not expected behavior, that can be understood by considering the Segre variety consisting of only two factors, ℙ^{a_{q}} and the product of all the others.

In [AOP09] it was settled completely the dimension of secant variety in the unbalanced case a_{q} ≥ ∏_{i=1}^{q−1}(a_{i} + 1) − (∑_{i=1}^{q−1} a_{i}) + 1. In these cases the last secant variety, which does not fill the ambient space, always has dimension smaller than expected.

We consider now the k-identifiability. It turns out (see Corollary 8.4) that the analogous condition to be unbalanced is a bit weaker, namely a_{q} ≥ ∏_{i=1}^{q−1}(a_{i} + 1) − (∑_{i=1}^{q−1} a_{i}). This explains why in the table shown in §7 we considered just the remaining cases.

The following Proposition is certainly well known, we prove it for the convenience of the reader.

Proposition 8.1. The general tensor of rank k ≤ ∏_{i=1}^{q−1}(a_{i} + 1) − (1 + ∑_{i=1}^{q−1} a_{i})

in ℙ(ℂ^{a_{1}+1} ⊗ … ⊗ ℂ^{a_{q}+1}) has a unique decomposition as sum of k decomposable summands for a_{q} ≥ ∏_{i=1}^{q−1}(a_{i} + 1) − (2 + ∑_{i=1}^{q−1} a_{i}).

Proof. Let ϕ ∈ ℂ^{a_{1}+1} ⊗ … ⊗ ℂ^{a_{q}+1} be general of rank k ≤ ∏_{i=1}^{q−1}(a_{i} + 1) − (1 + ∑_{i=1}^{q−1} a_{i}). It induces the flattening contraction operator

A_{ϕ}: (ℂ^{a_{q}+1})^{∨} → ℂ^{a_{1}+1} ⊗ … ⊗ ℂ^{a_{q−1}+1}

which has still rank k, by the assumption a_{q} ≥ ∏_{i=1}^{q−1}(a_{i} + 1) − (2 + ∑_{i=1}^{q−1} a_{i}).

Indeed, if ϕ = ∑_{i=1}^{k} v_{i,1} ⊗ v_{i,2} ⊗ ⋯ ⊗ v_{i,q} with v_{i,j} ∈ ℂ^{a_{j}+1}, where v_{i,q} can be chosen as part of a basis of ℂ^{a_{q}+1}, then Im A_{ϕ} is the span of the representatives of v_{i,1} ⊗ … ⊗ v_{i,q−1} for i = 1, …, k. It is well known that the projectification of this span, whose dimension is smaller than the codimension of the Segre variety Y = ℙ^{a_{1}} × … × ℙ^{a_{q−1}} ⊂ ℙ(ℂ^{a_{1}+1} ⊗ … ⊗ ℂ^{a_{q−1}+1}), meets Y only in these k points (see again, for example, the Theorem 2.6 in [CC06]). The claim follows. □

The case q = 3 of next Propositions 8.2 and 8.3 is contained in Prop. 5.4 of [CO12].

Proposition 8.2. If a_{q} ≥ ∏_{i=1}^{q−1}(a_{i} +1)−(∑_{i=1}^{q−1} a_{i})+1 then the rank of a general

tensor in ℙ(ℂ^{a_{1}+1} ⊗ … ⊗ ℂ^{a_{q}+1}) is min{a_{q} + 1, ∏_{i=1}^{q−1}(a_{i} + 1)}.

Moreover ℙ^{a_{1}} × … × ℙ^{a_{q}} is not k-identifiable for k > ∏_{i=1}^{q−1}(a_{i} + 1) − (∑_{i=1}^{q−1} a_{i}).

If a_{q} = ∏_{i=1}^{q−1}(a_{i} + 1) − (∑_{i=1}^{q−1} a_{i}), then the rank of a general tensor in

ℙ(ℂ^{a_{1}+1} ⊗ … ⊗ ℂ^{a_{q}+1}) is a_{q} + 1.

Proof. When a_{q} ≥ ∏_{i=1}^{q−1}(a_{i} + 1) − (∑_{i=1}^{q−1} a_{i}) + 1, we are in the unbalanced case, according to Definition 4.2 of [AOP09] (in the defective setting, the range of the unbalanced case is slightly bigger than in the weakly defective setting). In this case the statement follows from Theorem 4.4 of [AOP09].

When a_{q} = ∏_{i=1}^{q−1}(a_{i} + 1) − (∑_{i=1}^{q−1} a_{i}), using the same technique, we show that the secant variety S_{k}(ℙ^{a_{1}} × … × ℙ^{a_{q}}) has the expected dimension, for k ≤ a_{q}, and fills the ambient space, for k = a_{q} + 1.

Indeed, with the notations of [AOP09], condition T (a_{1}, …, a_{q}; a_{q}; 0^{q}) reduces to T (a_{1}, …, a_{q−1}, 0; 1; 0^{q−1}, a_{q} − 1) and T (a_{1}, …, a_{q−1}, 0; 0; 0^{q−1}, a_{q}) which are true and subabundant, while condition T (a_{1}, …, a_{q}; a_{q} + 1; 0, 0, 0) reduces to condition T (a_{1}, …, a_{q−1}, 0; 1; 0^{q−1}, a_{q}) which is superabundant and true. □

Proposition 8.3. Assume a_{q} ≥ ∏_{i=1}^{q−1}(a_{i} + 1) − (∑_{i=1}^{q−1} a_{i}). Then the number of

different decompositions of a general tensor of rank k = ∏_{i=1}^{q−1}(a_{i} + 1) − (∑_{i=1}^{q−1} a_{i})

is \binom{D}{k} where D = deg ℙ^{a_{1}} × … × ℙ^{a_{q−1}} = \frac{(∑_{i=1}^{q−1} a_{i})!}{a_{1}!...a_{q−1}!}. This number is always bigger than 1, so we have never identifiability.

Proof. We apply the same argument of the proof of Proposition 8.1. We pick a general ϕ of rank k. The only difference is that, now, the dimension of the projectification of Im A_{ϕ}, which is k−1, equals the codimension of ℙ^{a_{1}} ×…×ℙ^{a_{q−1}}. Thus we get D points of intersection. Any choice of k among these D points yields a decomposition. □

Corollary 8.4. Assume a_{q} ≥ ∏_{i=1}^{q−1}(a_{i} + 1) − (∑_{i=1}^{q−1} a_{i}). Then ℙ^{a_{1}} × … × ℙ^{a_{q}} is k-identifiable if and only if

k ≤ ∏_{i=1}^{q−1}(a_{i} + 1) − (1 + ∑_{i=1}^{q−1} a_{i})

Remark 8.5. We notice a misprint in the table in section 5 of [CO12]. The condition for “defective unbalanced” should read as c ≥ (a − 1)(b − 1) + 3 instead of c ≥ (a − 1)(b − 1) + 1. The proof of Prop. 5.3 of [CO12] needs slight modifications accordingly, but the statement remains correct.

9. The algorithm

The algorithm we have used has been implemented in Macaulay2 [GS] and it can be found as ancillary file in the arXiv submission of this paper.

The steps are the following.

(1) We choose s random points p_{1}, …, p_{s} on the Segre variety X, working on an affine chart. The point p_{1} can be chosen as (1, 0, …) on each factor.

(2) We compute the equations of the span of tangent spaces < T_{p_{1}}, …, T_{p_{s}} >.

(3) For any of the cartesian equations we compute its partial derivatives, the common locus is the locus C of points p such that T_{p}X ⊂ ⟨T_{p_{1}}, …, T_{p_{s}}⟩.

(4) We compute the rank of the jacobian matrix of C at p_{1}. If it is equal to the dimension of X then X is k-identifiable. If it is smaller than the dimension of X then a further analysis is required.

References

[AOP09] H. Abo, G. Ottaviani, C. Peterson, Induction for secant varieties of Segre varieties. Trans. Amer. Math. Soc., 361 (2009), 767–792

[AMR09] E.S. Allman, C. Matias, J.A. Rhodes. Identifiability of parameters in latent structure models with many observed variables. Ann. Statist., 37 (2009), 3099-3132.

[BC12] C. Bocci, L. Chiantini On the identifiability of binary Segre products. J. Alg. Geom.22 (2013) 1–11.

[CGG11] M.V. Catalisano, A.V. Geramita, A. Gimigliano Secant varieties of ℙ^{1} × … × ℙ^{1} (ntimes) are not defective for n ≥ 5. J. Algebraic Geom. 20 (2011), no. 2, 295-327.

[CC02] L. Chiantini and C. Ciliberto, Weakly defective varieties. Trans. Amer. Math. Soc., 354(1) (2002) 151–178.

[CC06] L. Chiantini and C. Ciliberto. On the concept of k-secant order of a variety. J. London Math. Soc. 73 (2006), 436–454.

[CO12] L. Chiantini, G. Ottaviani, On generic identifiability of 3-tensors of small rank. SIAM J. Matrix Anal. Appl., 33 (3), (2012), 1018–1037.

[CMO13] L. Chiantini, M. Mella, G. Ottaviani, One example of general unidentifiable tensors, arXiv:1303.6914

[EHN05] R. Elmore, P. Hall, A. Neeman., An application of classical invariant theory to identifiability in non-parametric mixtures. Ann. Inst. Fourier, 55 (2005), 1–28.

[Ges12] F. Gesmundo, An asymptotic bound for secant varieties of Segre varieties. to appear in Annali dell’Università di Ferrara, arXiv:1209.1732

[GS] D. Grayson and M. Stillman, Macaulay 2, a software system for research in algebraic

         geometry. Available at www.math.uiuc.edu/Macaulay2/ .

[KB09] T. Kolda and B. Bader. Tensor Decompositions and Applications. SIAM Review, 51(3) (2009) 455–500.

[Land] J. M. Landsberg. The geometry of tensors with applications. Graduate Studies in Mathematics 128, AMS, Providence 2012.

[Lat06] L. De Lauthawer. A link between the canonical decomposition in multilinear algebra and simultaneous matrix diagonalization. SIAM J. Matrix Anal. Appl., 28 (2006) 642–666.

[Str83] V. Strassen Rank and optimal computation of generic tensors. Linear Algebra Appl., 52 (1983) 645–685.

(C. Bocci) Dipartimento di Ingegneria dell’Informazione e Scienze Matematiche, Università di Siena, Pian dei Mantellini 44, 53100 Siena, Italia

   E-mail address: cristiano.boccii@unisi.it
   URL: http://www.mat.unisi.it/newsito/docente.php?id=16

(L. Chiantini) Dipartimento di Ingegneria dell’Informazione e Scienze Matematiche, Università di Siena, Pian dei Mantellini 44, 53100 Siena, Italia

   E-mail address: luca.chiantini@unisi.it
   URL: http://www.mat.unisi.it/newsito/docente.php?id=4

(G. Ottaviani) Dipartmento di Matematica e Informatica ’Ulisse Dini’, Università di Firenze, Viale Morgagni 67/A,, 50134 Firenze , Italia

   E-mail address: ottavian@math.unifi.it

URL: