The tensor rank decomposition, or canonical polyadic decomposition, is the decomposition of a tensor into a sum of rank-1 tensors. The condition number of the tensor rank decomposition measures the sensitivity of the rank-1 summands with respect to structured perturbations. Those are perturbations preserving the rank of the tensor that is decomposed. On the other hand, the angular condition number measures the perturbations of the rank-1 summands up to scaling. We show for random rank-2 tensors that the expected value of the condition number is infinite for a wide range of choices of the density. Under a mild additional assumption, we show that the same is true for most higher ranks \(r\ge 3\) as well. In fact, as the dimensions of the tensor tend to infinity, asymptotically all ranks are covered by our analysis. On the contrary, we show that rank-2 tensors have finite expected angular condition number. Based on numerical experiments, we conjecture that this could also be true for higher ranks. Our results underline the high computational complexity of computing tensor rank decompositions. We discuss consequences of our results for algorithm design and for testing algorithms computing tensor rank decompositions.
Notes
Communicated by Joseph M. Landsberg.
CB: Supported by Spanish “Ministerio de Economía y Competitividad” Under Project PID2020-113887GB-I00, as well as by the Banco Santander and Universidad de Cantabria Under Project 21.SI01.64658. PB: Funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation)—Projektnummer 445466444. NV: Supported by the Postdoctoral Fellowship of the Research Foundation—Flanders (FWO) with Project Numbers 12E8116N and 12E8119N and partially supported by KU Leuven project STG/19/002.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
1 Introduction
1.1 The Condition Number of Tensor Rank Decomposition
In this article, a tensor is a multidimensional array filled with numbers:
The integer d is called the order of . The tensor product of d vectors \(\mathbf {u}^{1} \in \mathbb {R}^{n_1},\ldots , \mathbf {u}^{d} \in \mathbb {R}^{n_d}\) is defined to be the tensor \(\mathbf {u}^{1} \otimes \cdots \otimes \mathbf {u}^{d} \in \mathbb {R}^{n_1 \times \cdots \times n_d}\) with entries
Any nonzero multidimensional array obeying this relation is called a rank-1 tensor. Not every multidimensional array represents a rank-1 tensor, but every tensor
is a finite linear combination of rank-1 tensors:
(1)
Hitchcock [50] coined the name polyadic decomposition for the decomposition Eq. (1). The smallest number r for which
admits an expression as in Eq. (1) is called the (real) rank of
. A corresponding minimal decomposition is called a canonical polyadic decomposition (CPD).
For instance, in algebraic statistics [1, 59], chemical sciences [67], machine learning [4], psychometrics [54], signal processing [35, 36, 65], or theoretical computer science [29], the input data have the structure of a tensor and the CPD of this tensor reveals the information of interest. Usually, this data is subject to measurement errors, which will cause the CPD computed from the measured data to differ from the CPD of the true data. In numerical analysis, the sensitivity of the model parameters, such as the rank-1 summands in the CPD, to perturbations of the data is often quantified by the condition number [61].
Advertisement
When there are multiple CPDs of a tensor , the condition number must be defined at a decomposition . However, in this article, we will restrict our analysis to tensors having a unique decomposition. Such tensors are called identifiable. In this case, the condition number of the tensor rank decomposition of a tensor is well-defined, and we denote it by . We will explain in Section 1.3 in greater detail the notion of identifiability of tensors. At this point, the reader should mainly bear in mind that the assumption of being identifiable is comparably weak as most tensors of low rank satisfy it. However, note that matrices (\(d=2\)) are never identifiable, so we assume that the order of the tensor is \(d\ge 3\).
The condition number of tensor rank decomposition was characterized in [20], and it is the condition number of the following computational problem: On input of rank r, compute the set of rank-1 terms in the decomposition Eq. (1). This condition number measures the sensitivity of the rank-1 terms with respect to perturbations of the tensor . In other words, when the condition number of the rank-r identifiable tensor in Eq. (1) is finite, it is the smallest value such that
(2)
holds for all rank-r tensors (with of rank 1) sufficiently close to . Herein, the norm on \(\mathbb {R}^{n_1\times \cdots \times n_d}\) is the usual Euclidean norm, and \(\mathfrak {S}_r\) is the permutation group on \(\{1,\ldots ,r\}\). It was shown in [24, Corollary 5.5] that the same expression holds if is any tensor close to and is the best rank-r approximation of in the Euclidean norm.
As a general principle in numerical analysis, the condition number is an intrinsic property of the computational problem that governs the forward error and attainable precision of any method for solving the problem. Its study is also useful for other purposes. For example, in [21, 22] the local rate of convergence of Riemannian Gauss–Newton optimization methods for computing the CPD was related to the condition number .
A conventional wisdom in numerical analysis is that it is harder to compute the condition number of a given problem instance than solving the problem itself [38, 39]. This viewpoint led Smale to initiate the study of the probability distribution of condition numbers: If the condition number is small with high probability, then for many practical purposes one can assume that any given input is well-conditioned; at least the probability of failure necessarily will be small. Smale started studying the probability that a polynomial is ill-conditioned [66]. This strategy was extended to linear algebra condition numbers [26, 31, 41], to systems of polynomial equations in diverse settings [42, 62], to linear systems of inequalities [49], to linear and convex programming [2, 68], eigenvalue and eigenvectors in the classic and other settings [7], to polynomial eigenvalue problems [6, 8], and to other computational models [30], among others. As there is a substantive bibliography on this setting, we refer the reader to [28] for further details.
Advertisement
Tensor rank decomposition seems to be no exception to this wisdom: The characterization of for a given in [20] requires the CPD of itself. This forces us to rely on probabilistic studies to establish reasonable a priori values of the condition number. Settling this is the main purpose of this paper.
1.2 Informal Version of Our Main Results and Discussion
The first probabilistic analyses of the condition number of CPD were given in [11, 23]. In those references, the expected value was computed for random rank-1 tensors; that is, for random output of the computational problem of computing CPDs. This amounts to choosing random \(\mathbf {u}_{i}^{k}\) in the notation above, constructing the corresponding tensor and studying . The probabilistic study is feasible, in principle, because one can obtain a closed expression for which is polynomial in terms of the \(\mathbf {u}_{i}^{k}\), so that the question boils down to an explicit but nontrivial integration problem.
This article is the first to investigate the condition number for random input. That is, we assume that is chosen at random within the set of rank-r tensors (see the definition of random tensors in Definition 1 and the extension in Theorem 4) and we wonder about the expected value of . The difficulty now is that even if we assume that a decomposition (1) exists, we do not have it and hence we lack a closed expression for .
One may wonder if these two different random procedures should give similar distributions in this or other numerical problems. The answer is no. For example, say that our problem is to compute the kernel of a given matrix \(A\in \mathbb {R}^{n\times (n+1)}\) and we want to study the expected value of the associated condition number \(\Vert A\Vert \,\Vert A^\dagger \Vert \). Choosing A at random produces \(\mathbb {E}(\Vert A\Vert \,\Vert A^\dagger \Vert )<\infty \) but choosing the kernel at random and then A at random within the matrices with that kernel is the same as computing the expected value of the usual Turing’s condition number of a square real Gaussian matrix, which is infinity; see [31] for precise estimations of these quantities. The situation is similar in the study of systems of homogeneous polynomial equations: random inputs have better condition number than inputs produced from random outputs; see for example [9]. In both these examples, the condition number of input constructed from random output is, on average, larger than the condition number of random input. This is a stroke of luck since in general one expects instances from practical, real-life problems, to be somehow random within the input space, not to have a random output!
In this paper, we show that computing the CPD is a rara avis: we prove in Theorems 1 and 2 that (under suitable hypotheses) the condition number of random input tensors turns out to be infinity. On the contrary, by Beltrán et al. [11] and Breiding and Vannieuwenhoven [23] it is presumed that the average condition number is finite when choosing random output. This result reinforces the evidence that computing CPDs is a very challenging computational problem.
The literature often cites the result of Håstad [53] to underline the high computational complexity of computing CPDs. Håstad showed that the NP-complete 3-satisfiability problem (also called 3-SAT) can be reduced to computing the rank of a tensor; hence, solving the tensor rank decomposition problem is NP-complete in the Turing machine computational model. Our main result is different in two aspects: First, Håstad showed the difficulty of only one particular instance of a CPD, whereas we show that computing the CPD is difficult on average. Second, our evidence supporting the hardness of the problem is not based on Turing machine complexity, but given by analyzing the condition number, which is more appropriate for numerical computations [16]. Linking complexity analyses to condition numbers is common in the literature; for instance, in the case of solving polynomial systems [9, 27, 56, 63]. In general, the book [28] provides a good overview. In this interpretation, we show that computing CPDs numerically is hard on average.
On the other hand, in the literature, the main result of de Silva and Lim [37] is often cited as a key reason why approximating a tensor by a low-rank CPD is such a challenging problem: for some input tensors, a best low-rank approximation may not exist! This is because the set of tensors of bounded rank is not closed: There are tensors of rank strictly greater than r that can be approximated arbitrarily well by rank-r tensors. It is shown in [37] that this ill-posedness of the approximation problem is not rare in the sense that for every tensor space \(\mathbb {R}^{n_1 \times n_2 \times n_3}\) there exists an open set of input tensors which do not admit a best rank-2 approximation. This result is stronger than Håstad’s in the sense that it proves that instances with no solution to the tensor rank approximation problem may occur on an open set, rather than in one particular set of measure zero. Notwithstanding this key result, it does not tell us about the complexity of solving the tensor rank decomposition problem, in which we are given a rank-r tensor whose CPD we seek. In this setting, there are no ill-posed inputs in the sense of de Silva and Lim [37]. It was already shown in [20] that the condition number diverges as one moves toward the open part of the boundary of tensors of bounded rank, entailing that there exist regions with arbitrarily high condition number. One of the main result of this paper, Theorem 2, shows that such regions cannot be ignored: They are sufficiently large to cause the integral of the condition number over the set of rank-r tensors to diverge. In other words, one cannot neglect the regions where the condition number is so high that a CPD computed from a floating-point representation of a rank-r tensor in \(\mathbb {R}^{n_1 \times \cdots \times n_d}\), subject only to roundoff errors, is meaningless—a result similar in spirit to de Silva and Lim [37].
One may conclude from the above that, at least from the point of view of average stability of the problem, tensor rank decomposition is doomed to fail. However, if one only cares about the directions of the rank-1 terms in the decomposition, then the situation changes dramatically. The condition number associated with the computational problem “Given a rank-r identifiable tensor as in Eq. (1), output the set of normalized rank-1 tensors ” will be called the angular condition number. Analogously to the bound Eq. (2), one can show that when \(\kappa _{\mathrm {ang}}\) is finite, it is the smallest number such that
for all rank-r tensors (with rank-1 tensors) in a sufficiently small open neighborhood of . By Breiding and Vannieuwenhoven [24, Corollary 5.5], the same expression holds for all tensors in a small open neighborhood of if is the best rank-r approximation of .
We will prove in Theorem 3 that at least in the case of rank-2 tensors, the angular condition number \(\kappa _{\mathrm {ang}}\) for random inputs is finite, contrary to the classic condition number \(\kappa \); in fact, the numerical experiments in Sect. 7 suggest that this finite average condition seems to extend to much higher ranks as well. In other words, on average we may expect to be able to recover the angular part of the CPD:
where is as in Eq. (1). One could conclude from this that a tensor decomposition algorithm should aim to produce the normalized rank-1 terms from the tensor rank decomposition
accurately. Once these terms are obtained, one can recover the \(\lambda _i\)’s by solving a linear system of equations. Since, as a general principle, the condition number of a composite smooth map \(g \circ f\) between manifolds satisfies [16, 28]
it follows that the condition number of tensor decomposition is bounded by the product of the condition numbers of the problem of finding the angular part of the CPD and the condition number of solving a linear least-squares problem. Our main results suggest that precisely the last problem will on average be ill-conditioned.
The foregoing observation can have major implications for algorithm design. Indeed, solving the tensor rank decomposition problem by first solving for the angular part and then the linear least-squares problem decomposes the problem into a nonlinear and a linear part. Crucially, the latter least-squares problem can be solved by direct methods, such as a QR-factorization combined with a linear system solver. Such methods have a uniform computational cost regardless of the condition number of the problem. By contrast, since no (provably) numerically stable direct algorithms for tensor rank decomposition are currently known Beltrán et al. [11], iterative methods are indispensable for this problem. We may expect their computational performance to depend on the condition number of the problem instance. Indeed, our main results combined with the main result of Breiding and Vannieuwenhoven [21] imply, for example, that Riemannian Gauss–Newton optimization methods for solving the angular part of the CPD should, on average, require less iterations to reach convergence than Riemannian Gauss–Newton methods for solving the tensor decomposition problem directly (such as the methods in [21, 22]), because the angular condition number \(\kappa _{\mathrm {ang}}\) appears to be finite on average, while the regular condition number \(\kappa \) is proved to be \(\infty \) on average in most cases, as we show in this article.
Our main results also have consequences for researchers testing numerical algorithms for computing the CPD. In the literature, a common way of generating input data for testing algorithms is to sample the rank-1 terms randomly, and then apply the algorithm to the associated tensor . However, our analysis in this paper and the analyses in [11, 23] show that this procedure generates tensors that are heavily biased toward being numerically well-conditioned. Hence, this way of testing algorithms probably does not correspond to a realistic distribution on the inputs. We acknowledge that it is currently not easy to sample rank-r tensors uniformly even though some methods exist [18]. In part, this is because equations for the algebraic variety containing the tensors of rank bounded by r are hard to obtain [57]. Nevertheless, in Sect. 7, using the observation from Remark 2, we present an acceptance–rejection method that can be applied to a few cases and yields uniformly distributed rank-r tensors, relative to the Gaussian density in Definition 1. In any case we strongly advocate that the (range of) condition numbers are reported when testing the performance of iterative methods for solving the tensor rank decomposition problem, so that one can assess the difficulty of the problem instances. We believe it is always recommended to include models that are known to lead to instances with high condition numbers, such as those used in [20, 22].
The formal presentation of our main results requires some extra notation that we introduce in subsequent sections.
1.3 Identifiable Tensors and a Formula for the Condition Number
A particular feature of higher-order tensors that distinguishes them from matrices is identifiability. This means that in many cases the CPD of tensors of order \(d\ge 3\) of small rank is unique. A tensor is called r-identifiable if there is a unique set of cardinality r such that and all ’s are rank-1 tensors. A celebrated criterion by Kruskal [55] gives a tool to decide if a given tensor of order 3 satisfies this property.
Lemma 1
(Kruskal’s criterion [55, 64]) Let \(\mathbb {F}\) be \(\mathbb {R}\) or \(\mathbb {C}\), a tensor of order 3 and assume that where Define the factor matrices \(U_\ell = [\mathbf {u}_{i}^{\ell }]_{1\le i \le r} \in \mathbb {F}^{n_\ell \times r}\) for \(\ell =1,2,3\), and let \(k_\ell \) be the largest integer k such that every subset of k columns of \(U_\ell \) has rank equal to k. If \( r \le \frac{1}{2}( k_1 + k_2 + k_3 - 2) \) and \(k_1, k_2, k_3 > 1\), then the tensor is r-identifiable over \(\mathbb {F}\).
Since matrix rank does not change with a field extension from \(\mathbb {R}\) to \(\mathbb {C}\), a real rank-r tensor that satisfies the assumptions of Lemma 1 is r-identifiable over \(\mathbb {R}\) and also automatically r-identifiable over \(\mathbb {C}\). In other words, Kruskal’s criterion is certifying complexr-identifiability of tensors, which is a strictly stronger notion than r-identifiability over \(\mathbb {R}\) [5].
Most order 3 tensors of low-rank satisfy Kruskal’s criterion [34]: There is an open dense subset of the set of rank-r tensors in \(\mathbb {R}^{n_1 \times n_2 \times n_3}\), \(n_1 \ge n_2 \ge n_3 \ge 2\), where complex r-identifiability holds, provided \(r \le n_1 + \min \{ \tfrac{1}{2} \delta , \delta \}\) with \(\delta := n_2 + n_3 - n_1 - 2\). In fact, this phenomenon occurs much more generally than third-order tensors of very small rank. Let us denote the set of complex tensors of complex rank bounded by r by
This constructible1 set turns out to be an open dense subset (in the Euclidean topology) of its Zariski closure \(\overline{\sigma _{r;n_1,\ldots ,n_d}^\mathbb {C}}\); see [57]. One says that \(\sigma _{r;n_1,\ldots ,n_d}^\mathbb {C}\) is generically complexr-identifiable if the subset of points of \(\sigma _{r;n_1,\ldots ,n_d}^\mathbb {C}\) that are not complex r-identifiable is contained in a proper closed subset in the Zariski topology on the algebraic variety \(\overline{\sigma _{r;n_1,\ldots ,n_d}^\mathbb {C}}\); see [32]. It is known from dimensionality arguments [32] that there is a maximum value of r for which generic r-identifiability of \(\sigma _{r;n_1,\ldots ,n_d}\) can hold, namely
In fact, it is conjectured that the inequality is strict in general; see [47] for details. For all other values of r, generic r-identifiability does not hold. In [17, 32, 33, 40], it is proved that in the majority of choices for \(n_1, \ldots , n_d\), generic complex r-identifiability holds for most ranks with \(r < r_\text {crit}\); see [17, Theorem 7.2] for a result that is asymptotically optimal. For a summary of the conjecturally complete picture of complex r-identifiability results, see [34, Section 3].
Assumption 1
In the rest of this article, we will assume that \(\sigma _{r;n_1,\ldots ,n_r}^\mathbb {C}\) is generically complex r-identifiable.
The reason why we make this assumption is because it greatly simplifies some of the arguments. At the same time, Assumption 1 is (conjectured to be) extremely weak and only limits the generality in the exceptional cases listed in [33, Theorem 1.1], and even then generic r-identifiability only fails very close to the upper bound \(r_\text {crit}\) of the permitted ranks.
An immediate benefit of Assumption 1 is that it allows for a nice expression of the condition number of the tensor rank decomposition problem. Let us denote the set of rank-1 tensors in \(\mathbb {R}^{n_1\times \cdots \times n_d}\) by
It is a smooth manifold, called the Segre manifold [46, 57]. The set of tensors of rank bounded by r is the image of the addition map: \(\sigma _{r;n_1,\ldots ,n_d} = \varPhi (\mathcal {S}_{n_1,\ldots ,n_d}^{\times r})\), where
(4)
Then, under Assumption 1, there exists an open dense subset \(\mathcal {N}_{r;n_1,\ldots ,n_d}\) of \(\sigma _{r;n_1,\ldots ,n_d}\) such that for all we have by Beltrán et al. [11, Proposition 4.5–4.7].2 In particular, the points in the fiber are isolated, so there is a local inverse map of \(\varPhi \) for each . Recall from [20] that the condition number of the CPD at is then the condition number (in the classic sense of Rice [61]; see also [28, 69]) of any of these local inverses:
(5)
where is arbitrary; it is a corollary of Breiding and Vannieuwenhoven [20, Theorem 1.1] that the above definition does not depend on the choice of . Herein, \(\Vert \cdot \Vert \) in the denominator is the Euclidean norm induced by the ambient \(\mathbb {R}^{n_1\times \cdots \times n_d}\), and the norm in the numerator is the product norm of the Euclidean norms inherited from the ambient \(\mathbb {R}^{n_1\times \cdots \times n_d}\)’s. The right-hand side is the spectral norm of the derivative of \(\varPhi _a^{-1}\) at . See Sect. 2 for more details. By Breiding and Vannieuwenhoven [20, Proposition 4.4], the condition number does not depend on the norm of : for \(t\in \mathbb {R}{\setminus }\{0\}\).
Remark 1
We did not specify the value of the condition number for . The main reason is that our analysis is independent of the values that the condition number takes on this set of measure zero, so that for simplicity we decided against including the more complicated general case where there can be several distinct elements in the preimage.
1.4 Main Results
The goal of this paper is to study the average condition number relative to “reasonable” density functions. By this, we mean probability distributions \(\hat{\rho }\) that are comparable to the standard Gaussian density \(\rho \): There exist positive constants \(c_1,c_2\) such that \(c_1 \le \frac{{\hat{\rho }}}{\rho } \le c_2\). The main result, Theorem 4, applies, among others, for all distributions \({\hat{\rho }}\) comparable to the following Gaussian density defined on the set of bounded rank tensors \(\sigma _{r;n_1,\ldots ,n_d}\).
Definition 1
(Gaussian identifiable tensors) We define a random variable on \(\sigma _{r;n_1,\ldots ,n_d}\) by specifying its density as
is the normalization constant. Under Assumption 1, if and , we say that is a Gaussian Identifiable Tensor (GIT) of rank r.
Remark 2
Suppose that r is a typical rank of tensors in \({\mathbb {R}}^{n_1\times \cdots \times n_d}\). This means that \(\sigma _{r;n_1,\ldots ,n_d}\) contains a Euclidean open subset of \({\mathbb {R}}^{n_1\times \cdots \times n_d}\) and is of maximum dimension \(n_1\cdots n_d\). Then, the distribution defined in Definition 1 is a conditional probability distribution: A GIT of rank r has the distribution , where is a tensor with independent and identically distributed (i.i.d.) standard Gaussian entries. We exploit this fact in our numerical experiments to sample GITs using an acceptance–rejection method.
We first state our results for the foregoing Gaussian density. At the end of this subsection, in Theorem 4, we generalize these results to other densities, including all densities comparable to the Gaussian density. Our first contribution is the following result. We prove it in Sect. 3.
Theorem 1
Let be a GIT of rank \(r= 2\). Then,
It should be mentioned that in our analysis we consider a small subset of \(\sigma _{2;n_1,\ldots ,n_d}\) and show that on this subset the condition number integrates to infinity. In particular, a weak average-case analysis as proposed in [3] would be of interest in this problem.
Under one additional assumption, we can extend the result from Theorem 1 to higher ranks. We prove the following theorem in Sect. 4.
Theorem 2
Let \(n_1,\ldots ,n_d\ge 3\). On top of Assumption 1, we assume that \(\sigma _{r-2,n_1-2,\ldots ,n_r-2}\) is generically complex identifiable. Then, for a GIT , \(r \ge 3\), we have
By Bocci et al. [17, Theorem 7.2], the assumptions of Theorem 2 are satisfied in a large number of cases. In fact, as the size of the tensor increases, the assumptions become weaker: When \(n_1 \ge n_2 \ge \cdots \ge n_d \ge 2\), the conditions in Theorem 2 are satisfied for \(r\le \min (s_1,s_2)\) with
Note that for large \(n_i\), the second piece \(s_2\) is the most restrictive. From Eq. (3), it is implied that \(r_{n_1-2,\ldots ,n_d-2}^\text {crit} = (1 - \delta _{n_1,\ldots ,n_d}){r_{n_1,\ldots ,n_d}^\text {crit}}\) with \(\delta _{n_1,\ldots ,n_d} = \mathcal {O}( \sum _{k=1}^d \frac{1}{n_k} )\). Therefore, we obtain the following asymptotically optimal result.
Corollary 1
Let \(d \ge 3\) be fixed, and \(n_1 \ge n_2 \ge \cdots \ge n_d \ge 2\). If \(n_1,\ldots ,n_d \rightarrow \infty \), then for a GIT we have for all
It follows from dimensionality arguments that if \(r>r_\text {crit}\), then the addition map \(\varPhi \) does not have a local inverse. In fact, in this case all of the connected components in the fiber of \(\varPhi \) at have positive dimension [46]. It follows from Breiding and Vannieuwenhoven [20] that the condition number of the tensor rank decomposition problem at each expression Eq. (1) of length r of such a tensor is \(\infty \). In this case, , regardless of how the tensor decomposition problem is defined3 when has multiple distinct decompositions; see also the discussion in [28, Remark 14.14]. In this case the average condition number is infinite, as well.
Our results lead us to the conjecture that the expected condition number is infinite, also without making the assumption from Theorem 2 and without any upper bound on the rank.
Conjecture 1
Let be a GIT of rank \(r\ge 2\). Then,
Corollary 1 proves this conjecture asymptotically, in practice leaving only a small range of ranks for which it might fail.
As mentioned above, it turns out that for GITs the expected angular condition number is not always infinite. Formally, the angular condition number is defined as follows: Let the canonical projection onto the sphere be \(p: \mathbb {R}^{n_1\times \cdots \times n_d} \rightarrow \mathbb {S}(\mathbb {R}^{n_1\times \cdots \times n_d})\). Then, the angular condition number of is
(6)
where is an arbitrary local inverse of \(\varPhi \) with . As before we do not specify what happens on the measure-zero set \(\sigma _{r;n_1,\ldots ,n_d}{\setminus }\mathcal {N}_{r;n_1,\ldots ,n_d}\), because it is not relevant for this paper. The angular condition number only accounts for the angular part of the CPD, i.e., the directions of the tensors, not for their magnitude, hence the name.
To distinguish the condition numbers Eqs. (5) and (6), we will refer to the condition number from Eq. 5 as the regular condition number. Oftentimes we even drop the clarification “regular.”
Here is the result for for tensors of rank two that we prove in Sect. 5.
Theorem 3
Let be a GIT of rank 2. Then, .
Unfortunately, we do not know if this theorem can be extended to higher rank tensors. However, based on our experiments in Sect. 7, we pose the following:
Conjecture 2
Let be a GIT of rank r. Then, .
We finally observe that the foregoing main results are not limited to GITs. They are valid for a wide range of distributions of random tensors.
Theorem 4
Theorems 1, 2, Corollary 1 and Theorem 3 are still true if instead of GITs we take random tensors defined by a wide range of other probability distributions, including some of interest such as:
1.
All probability distributions that are comparable to the standard Gaussian density \(\rho \). This means that the random tensor has a density \(\hat{\rho }\) for which there exists positive constants \(c_1,c_2\) such that \(c_1 \le \frac{{\hat{\rho }}}{\rho } \le c_2\).
2.
Uniformly randomly chosen in the unit sphere \({\mathbb {S}}(\sigma _r)\).
3.
Uniformly randomly chosen in the unit ball .
1.5 Organization of the Article
The rest of the article is organized as follows. In the next section, we give some preliminary material. Thereafter, in Sects. 3–6, we successively prove Theorems 1–4. In Sect. 7, we present numerical experiments supporting our main results. Finally, in Appendices A–C we give proofs for several lemmata that we need in the other sections.
2 Notation and Preliminaries
2.1 Notation
We will use the following typographic conventions for convenience: Vectors are typeset in a bold face (\(\mathbf {a}, \mathbf {b}\)), matrices in upper case (A, B), tensors in a calligraphic font (, ), and manifolds and linear spaces in a different calligraphic font (\(\mathcal {A}, \mathcal {B}\)).
The positive integer \(d \ge 2\) is reserved for the order of a tensor, \(n_1,\ldots ,n_d \ge 2\) are its dimensions, and \(r \ge 1\) is its rank. The following integers are used throughout the paper:
they correspond to the dimension of the Segre manifold \(\mathcal {S}_{n_1,\ldots ,n_d}\) and the dimension of the ambient space \(\mathbb {R}^{n_1 \times \cdots \times n_d}\), respectively. The symmetric group on r elements is denoted by \(\mathfrak {S}_r\).
We work exclusively with real vector spaces, for which \(\langle \cdot ,\cdot \rangle \) denotes the Euclidean inner product and \(\Vert \cdot \Vert \) always denotes the associated norm. We will switch freely between the finite-dimensional vector spaces \(\mathbb {R}^{n_1 \cdots n_d}\) and \(\mathbb {R}^{n_1 \times \cdots \times n_d}\) for representing tensors in the abstract vector space \(\mathbb {R}^{n_1} \otimes \cdots \otimes \mathbb {R}^{n_d}\). By the above choice of norms, all of these finite-dimensional Hilbert spaces are isometric; specifically, if and \(\mathbf {a} \in \mathbb {R}^{n_1 \cdots n_d}\) is its coordinate array with respect to an orthogonal basis, then . Similarly, if the coordinates \(\mathbf {a}\) are reshaped into a multidimensional array \(A \in \mathbb {R}^{n_1 \times \cdots \times n_d}\), then . It is important to note that this notation can conflict with the usual meaning of \(\Vert A\Vert \) when \(d=2\); to distinguish the spectral norm from the standard norm in this paper, we write \(\Vert A\Vert _2\) for the former; see Eq. (7).
For matrices \(U_1 \in \mathbb {R}^{m_1\times n_1}, \ldots , U_d \in \mathbb {R}^{m_d\times n_d}\), the tensor product \(U_1\otimes \cdots \otimes U_d\) acts on rank-1 tensors as follows:
By the universal property [44], this extends to a linear map \(\mathbb {R}^{n_1} \otimes \cdots \otimes \mathbb {R}^{n_d}\rightarrow \mathbb {R}^{m_1} \otimes \cdots \otimes \mathbb {R}^{m_d}\). Note that we can view \(U_1\otimes \cdots \otimes U_d \) as a matrix in \(\mathbb {R}^{(m_1\cdots m_d)\times (n_1\cdots n_d)}\).
For any subset \(U \subset V\) of a normed vector space V, we define the sphere over U as
In particular, the unit sphere in \(\mathbb {R}^n\) is denoted by \(\mathbb {S}(\mathbb {R}^n)\).
Given an \(m \times n\) matrix R or a linear operator \(R:\mathbb {R}^n\rightarrow \mathbb {R}^m\), we denote the pseudo-inverse by \(R^\dagger \). The spectral norm and smallest singular value of R are denoted respectively by
A special role will be played in this paper by the product of all but the smallest singular values of R, which we denote by q(R). In other words, if R is injective, then
where \(R^T\) is the transposed matrix (operator) and \(\varsigma _i(R)\) is the ith largest singular value of R.
2.2 Differential Geometry
In this article, we only consider submanifolds of Euclidean spaces; see, e.g., [58] for the general definitions. A smooth (\(C^\infty \)) manifold is a topological manifold with a smooth structure, in the sense of Lee [58]. The tangent space\(\mathrm {T}_{x} {\, \mathcal {M}}\) at x to an embedded n-dimensional smooth submanifold \(\mathcal {M} \subset \mathbb {R}^N\) is the set
At every point \(x \in \mathcal {M}\), there exist open neighborhoods \(\mathcal {V} \subset \mathcal {M}\) and \(\mathcal {U} \subset \mathrm {T}_{x} {\, \mathcal {M}}\) of x, and a bijective smooth map \(\phi : \mathcal {V} \rightarrow \mathcal {U}\) with smooth inverse. The tuple \((\mathcal {V},\phi )\) is a coordinate chart of \(\mathcal {M}\). A smooth map between manifolds \(F : \mathcal {M} \rightarrow \mathcal {N}\) is a map such that for every \(x \in \mathcal {M}\) and coordinate chart \((\mathcal {V},\phi )\) containing x, and every coordinate chart \((\mathcal {W}, \psi )\) containing F(x), we have that \(\psi \circ F \circ \phi ^{-1} : \phi (\mathcal {U}) \rightarrow \psi (F(\mathcal {U}))\) is a smooth map. The derivative of F can be defined as the linear map \(\mathrm {d}{}_{x} F : \mathrm {T}_{x} {\, \mathcal {M}} \rightarrow \mathrm {T}_{F(x)} {\, \mathcal {N}}\) taking the tangent vector \(\mathbf {v} \in \mathrm {T}_{x} {\, \mathcal {M}}\) to \(\frac{\mathrm {d}{}}{\mathrm {d}{}t}|_{t=0} F(\gamma (t)) \in \mathrm {T}_{F(x)} {\, \mathcal {N}}\) where \(\gamma (t) \subset \mathcal {M}\) is a curve with \(\gamma (0) = x\) and \(\gamma '(0) = \mathbf {v}\). If \(\dim \mathcal {M} = \dim \mathcal {N}\) and if \(\mathrm {d}{}_{x} F\) has full rank, there is a neighborhood \(\mathcal {W} \subset \mathcal {M}\) on which F is invertible and its inverse is also smooth; that is, F is a diffeomorphism between \(\mathcal {W}\) and \(F(\mathcal {W})\). If this property holds for all \(x \in \mathcal {M}\), then F is called a local diffeomorphism.
A differentiable submanifold \(\mathcal {M}\subset \mathbb {R}^N\) can be equipped with a Riemannian metricg, turning it into a Riemannian manifold, allowing for the computation of integrals. The manifolds in this paper are all embedded submanifolds of Euclidean space, so the Riemannian metric for us will always be the metric inherited from the ambient space.
The set of tensors of rank at most r is denoted by
it is a semialgebraic set of dimension at most \(\min \{r\varSigma , \varPi \}\); see, e.g., [60]. Under Assumption 1, the dimension of \(\sigma _{r;n_1,\ldots ,n_d}\) is exactly \(r\varSigma \).
In [11, Section 4], we introduced an open dense subset of \(\sigma _{r;n_1,\ldots ,n_d}\) with favorable differential-geometric properties. We called it the manifold of r-nice tensors in [11, Definition 4.2]. Below, we present a slightly modified definition that is suitable for our present purpose; it eliminates conditions (4) and (5) from Beltrán et al. [11, Definition 4.2].
In what follows, we denote the real closure in the Zariski topology of a subset \(A \subset \mathbb {R}^\varPi \) by \(\overline{A}\). This is the real algebraic variety \(\overline{A}:=\overline{A}^{{\mathbb {C}}} \cap \mathbb {R}^\varPi \), where \(\overline{A}^{{\mathbb {C}}}\) is the closure of A in the Zariski topology in \(\mathbb {C}^\varPi \). By Whitney [70, Lemma 8], the real dimension of \(\overline{A}\) equals the complex dimension of \(\overline{A}^{{\mathbb {C}}}\).
Definition 2
Recall the addition map \(\varPhi \) defined in Eq. (4). Let \(\mathcal {M}_{r;n_1,\ldots ,n_d} \subset (\mathcal {S}_{n_1,\ldots ,n_d})^{\times r}\) be the subset of r-tuples of rank-1 tensors satisfying all of the following properties:
1.
is a smooth point of the algebraic variety \(\overline{\sigma _{r;n_1,\ldots ,n_d}}\);
2.
is complex r-identifiable; and
3.
.
The set of r-nice tensors is \(\mathcal {N}_{r;n_1,\ldots ,n_d}:=\varPhi (\mathcal {M}_{r;n_1,\ldots ,n_d})\).
Remark that the third item in the definition is well defined because of the second item.
Proposition 1
If Assumption 1 holds, then the following statements are true:
1.
\(\mathcal {M}_{r;n_1,\ldots ,n_d}\) and \(\mathcal {N}_{r;n_1,\ldots ,n_d}\) are smooth manifolds of dimension \(r\varSigma \);
2.
\(\mathcal {M}_{r;n_1,\ldots ,n_d}\) is Zariski-open in \((\mathcal {S}_{n_1,\ldots ,n_d})^{\times r}\);
3.
\(\mathcal {N}_{r;n_1,\ldots ,n_d}\) is Zariski-open in \(\sigma _{r;n_1,\ldots ,n_d}\);
4.
the addition map \(\varPhi {\mid _{\mathcal {M}_{r;n_1,\ldots ,n_d}}}\) is a global diffeomorphism onto its image;
5.
\(\mathcal {N}_{r;n_1,\ldots ,n_d}\) is closed under multiplication by nonzero scalars; and
Items 1, 2, 3, and 6 are proved as follows. Let \(X_1\) and \(X_2\) be, respectively, the set of tensors in \(\sigma _{r;n_1,\ldots ,n_d}\) which are not complex r-identifiable and which are not smooth points of \(\overline{\sigma _{r;n_1,\ldots ,n_d}}\). Both are Zariski-closed in \(\overline{\sigma _{r;n_1,\ldots ,n_d}}\) under Assumption 1, and hence so are the preimages \(\varPhi ^{-1}(X_1)\) and \(\varPhi ^{-1}(X_2)\). Moreover, the third defining condition of \(\mathcal {M}_{r;n_1,\ldots ,n_d}\) is also Zariski-closed in \((\mathcal {S}_{n_1,\ldots ,n_d})^{\times r}\) from the explicit formula for the condition number Eq. (12). Hence, \(\mathcal {M}_{r;n_1,\ldots ,n_d}\) is Zariski-open. An open subset of an embedded submanifold is itself an embedded submanifold so the claim for \(\mathcal {M}_{r;n_1,\ldots ,n_d}\) is proved. Moreover, the dimension of the complement of \(\mathcal {M}_{r;n_1,\ldots ,n_d}\) is at most \(r\varSigma -1\) and so its image by the rational map \(\varPhi \) is contained in an algebraic set of dimension at most \(r\varSigma -1\), thus proving that \(\mathcal {N}_{r;n_1,\ldots ,n_d}\) is also Zariski-open and indeed an embedded submanifold of the set of smooth points of \(\overline{\sigma _{r;n_1,\ldots ,n_d}}\), which is itself an embedded submanifold of its affine ambient space, see [12, Proposition 3.2.9].
The fourth item is due to the definition of the condition number, the fact that it is finite on \(\mathcal {N}_{r;n_1,\ldots ,n_d}\) by Definition 2, and the injectivity of \(\varPhi |_{\mathcal {M}_{r;n_1,\ldots ,n_d}}\) by Definition 2 (2).
The fifth item follows by noting that the three defining properties of \(\mathcal {N}_{r;n_1,\ldots ,n_d}\) are all true independent of a nonzero scaling. \(\square \)
Remark 3
The definition of r-nice tensors in [11, Definition 4.2] involves two more requirements, but those are not needed here.
Since the tangent space of \(\mathcal {N}_{r;n_1,\ldots ,n_d}\) at a point is the image of the derivative of the local diffeomorphism \(\varPhi \), we have the following characterization:
(11)
2.4 Sensitivity of CPDs
The condition number of the problem of computing the rank-1 terms of a CPD of a tensor was studied in a general setting in [20]; the following characterization of the condition number is Theorem 1.1 of [20]. Let , where the are rank-1 tensors. For each i let \(U_i\) be a matrix whose columns form an orthonormal basis of . Then,
(12)
The matrix \(U=[U_1, \ldots , U_r]\in \mathbb {R}^{\varPi \times r\varSigma }\) is also called a Terracini matrix. An explicit expression for the \(U_i\)’s is given in [20, equation (5.1)].
Since uniquely depends on , we can view the condition number of as a function of :
(13)
where the matrices \(U_i\) are as before. The benefit of Eq. (13) is that it is well-defined for any tuple (and not just those mapping into \(\mathcal {N}_{r,n_1,\ldots ,n_d}\)).
2.5 Integrals
For fixed \(t\in (0,1]\) and a point \(\mathbf {y} \in \mathbb {S}(\mathbb {R}^n)\), the spherical cap of radius t around \(\mathbf {y}\) is defined as \(\mathrm {cap}(\mathbf {y},t) := \{\mathbf {x} \in \mathbb {S}(\mathbb {R}^n): {\langle \mathbf {x}, \mathbf {y}\rangle \; >\sqrt{ 1-t^2}}\}\). Its volume satisfies
for some positive constants \(0<c_1{(n)}<c_2{(n)}\).
The following general lemma will be useful later.
Lemma 2
Let \(u,v>0\) be fixed. Then, \(0<\int _0^\infty t^u \,e^{-\frac{(t + v)^2}{2}}\,\mathrm {d}{} t<\infty .\)
Proof
It is clear that the integral is not zero. Furthermore, since \((t + v)^2 > t^2+v^2\) for \(t,v>0\), we see that \(\int _0^\infty t^u \,e^{-\frac{(t + v)^2}{2}}\,\mathrm {d}{} t \le \int _0^\infty t^u \,e^{-\frac{t^2 + v^2}{2}}\,\mathrm {d}{} t = e^{-\frac{v^2}{2}}\sqrt{2}^{u-1}\varGamma (\frac{u+1}{2})\), which is finite. \(\square \)
2.6 The Coarea Formula
Let \(\mathcal {M}\) and \(\mathcal {N}\) be submanifolds of \(\mathbb {R}^n\) of equal dimension, and let \(F: \mathcal {M} \rightarrow \mathcal {N}\) be a smooth surjective map. A point \(y\in \mathcal {N}\) is called a regular value of F if for all points \(x\in F^{-1}(y)\) the differential \(\mathrm {d}{}_{x} F\) is of full rank. The preimage \(F^{-1}(y)\) of a regular value y is a discrete set of points. Let \(|F^{-1}(y)|\) be the number of elements in this preimage. Then, the coarea formula [52] states that for every integrable function g we have
where \(\mathrm {Jac}(F)(x):=\vert \det \mathrm {d}{}_{x} F\vert \) is the Jacobian determinant of F at x. Note that almost all \(y\in \mathcal {N}\) are regular values of F by Sard’s theorem [58, Theorem 6.10]. Hence, integrating over \(\mathcal {N}\) is the same as integrating over all regular values of F.
Remark 4
In [52], the coarea formula is given in the more general case when \(\dim \mathcal {M} \ge \dim \mathcal {N}\). In this article, we only need the case when the dimension of \(\dim \mathcal {M}\) and \(\dim \mathcal {N}\) coincide. Moreover, if F is injective, then Eq. (15) reduces to the well-known change-of-variables formula.
3 The Average Condition Number of Gaussian Tensors of Rank Two
The goal of this section is to prove Theorem 1. We will proceed in three steps. First, the 2-nice tensors are conveniently parameterized via elementary manifolds such as one-dimensional intervals and spheres in Sect. 3.1. Second, the Jacobian determinant of this map is computed in Sect. 3.2. Third, the integral can be bounded from below with the help of a few technical auxiliary lemmas in Sect. 3.3. In the next section, we will exploit Theorem 1 for generalizing the argument to most higher ranks. To simplify notation, in this section we let
The preimage of has cardinality . By composing \(\varPsi := \psi \times \psi \) with the addition map from Eq. (4), we get the following alternative representation of tensors of rank bounded by 2:
We would like to apply the coarea formula Eq. (15) to pull back the integral of over \(\sigma _{2}\) via the parameterization \(\varPhi \circ \varPsi \). However, \(\sigma _{2}\) in general is not a manifold, so the formula does not apply. Nevertheless, we can use the manifold \(\mathcal {N}_{2}\) of 2-nice tensors instead. By Proposition 1(3), \(\mathcal {N}_2\) is Zariski open in \(\sigma _2\), so that
where \(C_2 := C_{2;n_1,\ldots ,n_d}\) is as in Definition 1. By applying the coarea formula Eq. (15) to the smooth map \(\varPhi \mid _{\mathcal {M}_2}\), we get
where is the Jacobian determinant of \(\varPhi \) at . In the first equality, we used for 2-identifiable tensors; indeed, we have that and because has rank equal to 2.
In the following, we switch to the notation from Eq. (13): . Since \(\mathcal {M}_{2}\) is also Zariski open in \(\mathcal {S} \times \mathcal {S}\) by Proposition 1(2), we may replace the integral over \({\mathcal {M}}_{2}\) by an integral over \(\mathcal {S} \times \mathcal {S}\), thus obtaining
We use the coarea formula again, but this time for \(\varPsi = \psi \times \psi \), where \(\psi \) is the parameterization from Eq. (17). Note that for we have . We get
(18)
where and are both tuples in \((0,\infty ) \times \mathcal {P}\). Next, we compute the Jacobian determinant .
3.2 Computing the Jacobian Determinant
Note that the dimension of the domain of \(\varPhi \circ \varPsi \) is equal to \(2\varSigma \). As above, let and be tuples in \((0,\infty ) \times \mathcal {P}\) with \(\mathcal {P}\) as in Eq. (16). In the following, we write
The Jacobian determinant of \(\varPhi \circ \varPsi \) at is, by definition, the absolute value of the determinant of the linear map
Consider the matrix of partial derivatives of \(\varPhi \circ \varPsi \) with respect to the standard orthonormal basis of \(\mathbb {R}^{n_1\times \cdots \times n_d}\):
Then, the Jacobian determinant of \(\varPhi \circ \varPsi \) at is
(21)
The latter is the volume of the parallelepiped spanned by the columns of Q. We fix notation in the next definition.
Definition 3
Let \(N{\,\ge \,}n\) be positive integers and \(U\in {\mathbb {R}}^{N\times n}\) be a matrix with columns \(\mathbf {u}_1,\ldots ,\mathbf {u}_n\in {\mathbb {R}}^N\). We denote by \(\mathrm {vol}(U)\) the volume of the parallelepiped spanned by the \(\mathbf {u}_i\):
The reason why we write the partial derivatives of \(\varPhi \circ \varPsi \) with respect to the standard basis of \(\mathbb {R}^{n_1\times \cdots \times n_d}\) is that we get the following convenient description:
be matrices containing as columns an ordered orthonormal basis of \((\mathbf {u}^k)^\perp = \mathrm {T}_{\mathbf {u}^k} {\, \mathbb {S}(\mathbb {R}^{n_k})}\) and \((\mathbf {v}^k)^\perp = \mathrm {T}_{\mathbf {v}^k} {\, \mathbb {S}(\mathbb {R}^{n_k})}\), respectively. Then, by linearity and the product rule of differentiation, we have that \(L = \begin{bmatrix} \lambda L_1&\mu L_2 \end{bmatrix}\) is the block matrix consisting of 2 blocks of the form
Both \(L_1\) and \(L_2\) have \(\sum _{k=1}^d (n_k-1) = \varSigma -1\) columns. Note that M depends only on the \(\mathbf {u}^k\)’s and \(\mathbf {v}^k\)’s, whereas L also depends on the parameters \(\lambda \) and \(\mu \); we do not emphasize these dependencies in the notation.
Comparing with Breiding and Vannieuwenhoven [20, equation (5.1)], we see that the matrix \(L_1\) has as columns an orthonormal basis for the orthogonal complement of in . Analogously, the columns of \(L_2\) form an orthonormal basis for the orthogonal complement of in . Consequently, for , Terracini’s matrix from Eq. (12) can be chosen as
(24)
This entails that
(25)
having used the notation from Definition 3 and the fact that singular values are invariant under orthogonal transformations such as permutations of columns.
3.3 Bounding the Integral
We are now ready to conclude the proof of Theorem 1, by showing that the expected value of the condition number of tensor rank decomposition is bounded from below by infinity.
By Eq. (12), the condition number at is the inverse of the smallest singular value of the Terracini’s matrix U from Eq. (24). Therefore, if we plug Eqs. (24) and (25) into (18), then we get
(26)
where \( {q(U) = \frac{\mathrm {vol}(U)}{\varsigma _{\min }(U)}} \) is as in Eq. (8), and
(27)
From Eq. (24), it is clear that U is a function of and but is independent of \(\lambda \) and \(\mu \). Therefore, if we integrate first over \(\lambda \) and \(\mu \), then we can ignore the factor q(U). In Appendix A.1, we compute this integral; the result is stated here as the next lemma.
Lemma 3
Let \((\mathbf {u}^1,\ldots ,\mathbf {u}^d), (\mathbf {v}^1,\ldots ,\mathbf {v}^d) \in \mathcal {P}\) be fixed. Then,
where and .
The foregoing integral can be bounded from below by exploiting the next lemma, which is proved in Appendix A.2.
Lemma 4
Let \(\mathbf {x},\mathbf {y}\in \mathbb {S}(\mathbb {R}^p)\) be two unit-norm vectors and \(s\ge 1\). Then, there exists a constant \(k=k(p,s)\) independent of \(\mathbf {x},\mathbf {y}\) such that
Combining the foregoing lemmata and plugging the result into Eq. (26), we obtain
Next, we exploit the symmetry of the domain \(\mathbb {S}(\mathbb {R}^{n_1})\) by flipping the sign of \(\mathbf {v}^1\) and, hence, of . This substitution transforms U into UD, where D is a diagonal matrix with some pattern of \(\pm 1\) on the diagonal. Since D is orthogonal, \(q(U) = q(UD)\), so that
Denote this last integral by J, and then, it remains to show that \(J=\infty \). Consider the open set
Since \(D(\epsilon )\) is open, we have
(28)
We now need two lemmata. The first one is straightforward.
Lemma 5
Let \(\epsilon >0\) be sufficiently small. For all with and , we have
where and .
Proof
For proving the upper bound, apply the triangle inequality to the telescoping sum
and exploit \(\Vert \mathbf {u}^k - \mathbf {v}^k\Vert \le \Vert \mathbf {u}^1 -\mathbf {v}^1\Vert \) for all \(k=1,\ldots ,d\). The lower bound follows from
having used \(0 < \langle \mathbf {u}^k, \mathbf {v}^k \rangle \le 1\) for sufficiently small \(\epsilon \). \(\square \)
The second one is the final piece of the puzzle. We prove it in Appendix A.3.
Lemma 6
For sufficiently small \(\epsilon >0\), we have for all with and that
where \(c>0\) is some constant. Note that the integrand in this equation only depends on \(\mathbf {u}^1\) and \(\mathbf {v}^1\). By definition of \(D(\epsilon )\), for each \(2\le k \le d\), and if we fix \(\mathbf {u}^k\), the domain of integration of \(\mathbf {v}^k\) contains the difference of two spherical caps of respective affine radii \(\frac{9}{10} \Vert \mathbf {u}^1 - \mathbf {v}^1 \Vert \) and \(\Vert \mathbf {u}^1 - \mathbf {v}^1 \Vert \). From Eq. (14), the volume of this difference of caps is greater than a constant times \(\Vert \mathbf {u}^1 - \mathbf {v}^1 \Vert ^{n_j-1}\). Therefore, if we keep \(\mathbf {u}^1,\mathbf {v}^1 \in \mathbb {S}(\mathbb {R}^{n_1})\) constant and integrate over \(\mathbf {u}^k, \mathbf {v}^k \in \mathbb {S}(\mathbb {R}^{n_k})\), \(k=2,\ldots ,d\), then we get
By rotational invariance, the inner integral does not depend on \(\mathbf {u}^1\) and moreover for small \(\epsilon \) projecting through the stereographic projection (which has a Jacobian bounded above and below by a positive constant close to its center) we conclude that, for some other constant \(c''\),
This proves \(J = \infty \), so that for tensors of rank bounded by 2, constituting a proof of Theorem 1.
4 The Average Condition Number: From Rank 2 to Higher Ranks
Having established that the average condition number of tensor rank decomposition of rank 2 tensors is infinite, we extend this result to higher ranks. That is, we will prove Theorem 2. As before, we abbreviate \(\mathcal {S}:= \mathcal {S}_{n_1,\ldots ,n_d}\), \(\sigma _r:=\sigma _{r,n_1,\ldots ,n_d}\), \(\mathcal {N}_r:=\mathcal {N}_{r,n_1,\ldots ,n_d}\), and \(\mathcal {M}_r:=\mathcal {M}_{r,n_1,\ldots ,n_d}.\)
We proceed with an observation that is of independent interest.
Lemma 7
Let and be \(n_1 \times \cdots \times n_d\) tensors, where the and are rank-1 tensors. If is \((r+s)\)-identifiable, then we have
Proof
First, we observe that is r-identifiable, and is s-identifiable. Indeed, if the tensor is \((r+s)\)-identifiable, then the unique set C of cardinality \(|C| \le r\) consisting of rank-1 tensors summing to is . If had an alternative decomposition , potentially of a shorter length \(r' \le r\), then would be an alternative decomposition of . Hence, needs to equal , so that is r-identifiable. By symmetry, the result for follows. For all i, let \(U_i\) be a matrix with orthonormal columns that span , and \(V_i\) be a matrix with orthonormal columns that span . Consider the matrices \(U=[U_1,\ldots ,U_r]\) and \(V=[V_1,\ldots ,V_s]\). By Eq. (12), we have
The claim follows from standard interlacing properties of singular values; see [51, Chapter 3]. \(\square \)
The next simple lemma is immediate.
Lemma 8
Consider the map The following holds.
1.
For \(r > 2\), we have \(\phi (\sigma _2\times \mathcal {S}^{\times (r-2)}) = \sigma _r\).
2.
Let be r-identifiable. Then, .
Finally, the next lemma is the key to Theorem 2, providing a lower bound for the Jacobian determinant of \(\phi \) in a special open subset of \(\sigma _2 \times \mathcal {S}^{\times (r-2)}\). We postpone its proof to Appendix B.
Lemma 9
On top of Assumption 1 we assume that \(\sigma _{r-2; n_1-2,\ldots ,n_d-2}\) is generically complex identifiable. Then, there are constants \(\mu ,\epsilon , \nu _1, \ldots , \nu _{r-2} >0\) depending only on \(r,n_1,\ldots ,n_d\) with the following property: For all there exists a tuple with and
Given any , by taking a sequence converging to one can generate the corresponding sequences from Lemma 9. Now, by compactness we can find an accumulation point . Since \(\mathrm {Jac}(\phi )\) is continuous and hence uniformly continuous when restricted to a compact set, by choosing small enough \(\epsilon \) we can assure that for all , and for all , we have , where \(\epsilon \) and \(\mu \) do not depend on .
Recall the surjective map \(\phi : \sigma _2\times {\mathcal {S}^{\times (r-2)}} \rightarrow \sigma _r\) from Lemma 8. From Theorem 1 and the fact that for \(t>0\), there exists a tensor such that for every \(\delta >0\) we have
From Lemma 9 and Remark 5, there exist tensors such that
for all such that , and . Let \(\mathcal {U}\subseteq \mathcal {N}_2\times \mathcal {S}^{\times r-2}\) be the set of all satisfying the foregoing conditions. From Lemma 7, we have
Moreover, by Lemma 9 and the inverse function theorem, by taking small enough \(\epsilon \) and \(\delta \) we can assume that \(\phi |_\mathcal {U}\) is a diffeomorphism onto its image4 and hence \(\phi (\mathcal {U})\) is open. The coarea formula Eq. (15) thus applies yielding
The theorem follows since \(\phi (\mathcal {U})\subseteq \sigma _r\). \(\square \)
5 The Angular Condition Number of Tensor Rank Decomposition
In this section, we prove Theorem 3. As in the previous section, to ease notation, we abbreviate \(\mathcal {M}_2:= \mathcal {M}_{2;n_1,\ldots ,n_d}\), \(\mathcal {N}_2:= \mathcal {N}_{2;n_1,\ldots ,n_d}\), \(\mathcal {S}_2:= \mathcal {S}_{2;n_1,\ldots ,n_d}\), and \(\sigma _2:= \sigma _{2;n_1,\ldots ,n_d}\).
5.1 A Characterization of the Angular Condition Number as a Singular Value
We first derive a formula for the angular condition number in terms of singular values, similar to the one from Eq. (12). Recall from Eq. (6) that the angular condition number for rank \(r=2\) is
where \(p: \mathbb {R}^{n_1\times \cdots \times n_d} \rightarrow \mathbb {S}(\mathbb {R}^{n_1\times \cdots \times n_d})\) is the canonical projection onto the sphere and where is a local inverse of \(\varPhi :\mathcal {S} \times \mathcal {S} \rightarrow \sigma _2\) at with . As before, the value of \(\kappa _{\mathrm {ang}}\) on \(\sigma _2{\setminus }\mathcal {N}_2\) is not relevant for our analysis, so we do not specify it.
Proposition 2
Under Assumption 1, let , where for \(1\le k\le d\) we have \(\mathbf {u}^k,\mathbf {v}^k\in \mathbb {S}(\mathbb {R}^{n_k})\). Recall from Eq. (20) the definitions of the matrices M and L, associated to . The following equality holds:
as far as the right–hand term is finite.
Proof
By Proposition 1, any local inverse is differentiable at . The projection p is also differentiable, so that
where \(\Vert \cdot \Vert _2\) is the spectral norm from Eq. (7). We compute this norm.
Let and . Then, by linearity of the derivative, we have . Furthermore, for \(i=1,2\), the derivative is the orthogonal projection onto the orthogonal complement of in \(\mathbb {R}^\varPi \). According to this, we decompose and as
Then, we have and, consequently,
(29)
Recall from Eq. (20) the matrices \(L=\begin{bmatrix} \lambda L_1&\mu L_2\end{bmatrix}\) and . We can find vectors \(\mathbf {x}_1,\mathbf {x}_2 \in \mathbb {R}^{\varSigma -1}\) with and , and such that and . Observe that and . This yields
(30)
Writing
Since we are assuming that \((\mathrm {I}- MM^\dagger )L\) is injective (for \(\varsigma _{\min }((\mathrm {I}-MM^\dagger )L)\ne 0\)), it has a left inverse and we can write
the second equality from \( \left( PL\right) ^\dagger P= \left( PL\right) ^\dagger \), which is a basic property of the Moore–Penrose pseudo-inverse holding for any orthogonal projector P. This finishes the proof. \(\square \)
Now comes the actual proof of Theorem 3. Proceeding in exactly the same way as in Sect. 3.1 and using Proposition 2, we get
(32)
where \(C_2 = C_{2;n_1,\ldots ,n_d}\) is as in Definition 1, \(\mathcal {P}\) is as in Eq. (16), \(Q = \begin{bmatrix} L&M \end{bmatrix}\) is as in Eq. (19), the volume \(\mathrm {vol}\) is as in Definition 3, and
is as in Eq. (27), so that . Next, we relate \(\mathrm {vol}(Q)\) to the volume of \((\mathrm {I}- M M^\dagger )L\).
Lemma 10
We have \( \mathrm {vol}(Q) = \mathrm {vol}(M)\,\mathrm {vol}((\mathrm {I}-MM^\dagger )L). \)
Proof
Let \(Q^\perp \) be a matrix whose columns contain an orthonormal basis for the orthogonal complement of the column span of Q. Then, from the definition,
These two blocks are mutually orthogonal, since \((\mathrm {I}-MM^\dagger )\) is the projection on the orthogonal complement of the span of M, and hence, the volume is the product of the volumes corresponding to each block. The assertion follows. \(\square \)
where q is as in Eq. (8). Recall from Eq. (22) that M is independent of \(\lambda \) and \(\mu \). We first compute the integral over \(\lambda , \mu \) using the next lemma. We prove the lemma in Appendix C.1.
Lemma 11
Let \(L_1,L_2\) be the matrices defined as in Eq. (23), such that \(L=\begin{bmatrix} \lambda L_1&\mu L_2\end{bmatrix}\). Let
Then,
Inserting the results from this lemma into Eq. (33), we get
where
In the remaining part of this section, we show that \(J_\mathrm {outer}\) is bounded by a constant, which would conclude the proof. We do this by giving a sequence of upper bounds. We have no hope of providing sharp bounds, so rather than keeping track of all the constants, we will exploit the following definition for streamlining the proof.
Definition 4
For \(A,B\in [0,\infty ]\), we will write \(A \preceq B\) if \(B\in \mathbb {R}\) implies \(A\in \mathbb {R}\). That is, \(A\preceq B\) is an equivalent statement to “\(B<\infty \Rightarrow A<\infty \).”
First, note that , so that
Next, we exploit the symmetry of \(\mathbb {S}(\mathbb {R}^{n_1})\) and transform \(\mathbf {v}^1 \mapsto -\mathbf {v}^1\). This transformation flips the sign of , but the value of q is not affected. Indeed, the matrix \(\mathrm {I}- M M^\dagger \) still projects onto , and \(L_2\) is transformed into \(L_2 D\), where D is a diagonal matrix with some pattern of \(\pm 1\) on the diagonal. Since \(\left[ {\begin{matrix}I &{} \\ &{} D\end{matrix}}\right] \) is an orthogonal transformation, the singular values do not change. Thus, we obtain
Let \(\theta \in [0,\tfrac{\pi }{2}]\) and fix and . There is a constant \(K>0\), depending only on \(n_1,\ldots ,n_d\) and d, such that
(34)
The lemma implies
(35)
For bounding the integral over \(\theta \), we need the next lemma, which we prove in Appendix C.3.
Lemma 13
Let \(a>1,p\ge 1\). There exists a constant \(K>0\), depending only on a, such that for any unit vectors \(\mathbf {x},\mathbf {y}\in \mathbb {S}{}(\mathbb {R}^p)\), \(\mathbf {x}\ne \mathbf {y}\), we have
By orthogonal invariance, we may fix \(\mathbf {u}^k\in \mathbb {S}(\mathbb {R}^{n_k})\) to be \(\mathbf {u}^k = (1,0,\ldots ,0)\), and integrate the constant function 1 over one copy of \(\mathbb {S}{}(\mathbb {R}^{n_1}) \times \cdots \times \mathbb {S}{}(\mathbb {R}^{n_d})\). Ignoring the product of volumes \(\prod _{k=1}^d\mathrm {vol}(\mathbb {S}{}(\mathbb {R}^{n_k}))\) we have
Now, this spherical integral is particularly simple because the integrand depends uniquely on one of the components of each vector. One can thus transform each integral in a sphere into an integral in an interval (see, for example, [10, Lemma 1]) getting:
For this last integral, we consider the partition of the cube \([-1,1]^d\) into \(2^d\) pieces corresponding to the different signs of the coordinates. In the pieces where the number of negative coordinates is odd, the denominator of the integrand is bounded below by 1 and thus the whole integrand is also bounded above by 1. Hence, it suffices to check that the integral in the rest of the pieces is bounded. Assume now that \(t_{i_1},\ldots ,t_{i_k}\) with \(k\ge 2\) even are the negative coordinates in some particular piece of the partition. The mapping that leaves all coordinates fixed but maps \(t_{i_{k-1}} \mapsto -t_{i_{k-1}}\) and \(t_{i_{k}} \mapsto -t_{i_{k}}\) preserves the integrand and moves the domain to another piece of the partition with \(k-2\) negative coordinates. This process can then be repeated until none of the coordinates is negative. All in one, we have
Using the lemma and the inequality \(\sin (\theta )<\theta \) on \(0\le \theta \le \tfrac{\pi }{2}\), we find that the integral in Eq. (36) is bounded by a constant times the following integral:
Changing the name of the variables to \(x_1,\ldots ,x_d\) and integrating over the d-dimensional ball of radius \(\tfrac{\pi }{2}\sqrt{d}\), which contains the domain \([0,\tfrac{\pi }{2}]^d\), we get a new upper bound for the last integral, which implies
We demonstrate how our main results can be extended to many other distributions as well.
Consider the first item of Theorem 4. We assume that has the density \(\hat{\rho }\) and that there exists positive constants \(c_1,c_2\) such that \(c_1 \le \frac{{\hat{\rho }}}{\rho } \le c_2\), where \(\rho \) is the density of a GIT. Then, for any measurable function we have
and
Thus, if and only if . Replacing f by \(\kappa \) and \(\kappa _{\mathrm {ang}}\) proves the first part of Theorem 4.
By Breiding and Vannieuwenhoven [20, Proposition 4.4], \(\kappa \) is invariant under multiplication of by a scalar. Therefore, the expected value of \(\kappa \) for the Gaussian is equal to the expected value when is chosen uniformly in the unit ball, and also when is chosen uniformly in the unit sphere of the space of tensors. Namely, we have (see, e.g., [28, Section 2.2.4])
This proves the second and third item of Theorem 4 for \(\kappa \).
For \(\kappa _{\mathrm {ang}}\), we need the following lemma.
Lemma 15
If is an r-nice tensor, then for all \(t>0\).
Proof
Since is r-nice, we have . Similar as for Eq. (29), we can show where is the CPD of and is the corresponding decomposition the tangent vector. The derivative is the orthogonal projection onto and independent of scaling. Moreover, \(\sigma _{r;n_1,\ldots ,n_d}\) is a cone and so can be identified with . This shows that after scaling the tensor we get and hence .
\(\square \)
Now, we can prove the rest of Theorem 4. Recall from Definition 1 that the density of a GIT on \(\sigma _{r;n_1,\ldots ,n_d}\) is , where . Since our results for \(\kappa _{\mathrm {ang}}\) are for rank-2 tensors, we put \(r=2\) in the following. We also abbreviate \(\sigma _2:=\sigma _{2;n_1,\ldots ,n_d}\) and \(C_2:=C_{2;n_1,\ldots ,n_d}\). Then, using Lemma 15 we can integrate in polar coordinates to obtain
It follows immediately that the last integral is finite, proving that a randomly chosen has finite expected \(\kappa _{\mathrm {ang}}\). Finally, if is chosen randomly in the unit ball in \(\sigma _2\), the same argument shows that the expected value is again finite:
Having proved that the expected value of the condition number is infinite in most cases, we provide further computational evidence in support of Conjecture 1. To this end, a natural idea is to perform Monte Carlo experiments in a few of the unknown cases as in [23].
Sampling GITs is hard in practice, as the defining polynomial equalities and inequalities of the semialgebraic set \(\sigma _r = \sigma _{r;n_1,\ldots ,n_d}\) of tensors of rank bounded by r are not known in the literature.5 Nevertheless, there are a few cases that we can treat numerically. If \(r = \frac{\varPi }{\varSigma }\) and the algebraic closure \(\overline{\sigma _r}(\mathbb {C})\) has \(\dim \overline{\sigma _r}(\mathbb {C}) = \varPi \), a so-called perfect tensor space, then \(\sigma _r\) is an open subset of the ambient \(\mathbb {R}^{n_1 \times \cdots \times n_d}\); see, e.g., [15, 57].
From Remark 2, we can sample from the density \(\rho \) on \(\sigma _r\) via an acceptance–rejection method: Randomly sample tensors from the density until we find one that belongs to \(\sigma _r\). While this scheme will yield tensors distributed according to the density \(\rho \) on \(\sigma _r\), it does not yield Gaussian identifiable tensors in general. The reason is that most perfect tensor spaces are not (expected to be) generically r-identifiable [47]. Fortunately, there are a few known exceptions: matrix pencils (\(\mathbb {R}^{n \times n \times 2}\) for all \(n\ge 2\)), \(\mathbb {R}^{5 \times 4 \times 3}\) and \(\mathbb {R}^{3 \times 2 \times 2 \times 2}\) are proved to be generically complex r-identifiable for \(r = \frac{\varPi }{\varSigma }\). By applying the acceptance–rejection method to these spaces, every sampled tensor is a GIT with probability 1.
For numerically checking, if a random tensor in a perfect tensor space lies in \(\sigma _r\) with \(r = \frac{\varPi }{\varSigma }\), we apply a homotopy continuation method to the square system of \(\varPi \) equations
where the \(\varPi = r \varSigma \) entries of the \(\mathbf {a}_{i}^{k}\)’s are treated as variables, and the \(n_1 \times \cdots \times n_d\) tensor is the tensor to decompose. We generate a start system with one solution to track by randomly sampling the entries of the vectors \(\mathbf {a}_{i}^{k}\) i.i.d. from a real standard Gaussian distribution and then constructing the corresponding tensor . Since \(r = \frac{\varPi }{\varSigma }\) is the so-called generic rank of tensors in perfect tensor spaces \(\mathbb {C}^{n_1 \times \cdots \times n_d}\), the above system has at least one complex solution with probability 1 as well. If we consider complex r-identifiable perfect tensor spaces at the generic rank, we can thus determine if by solving the square system and checking whether the unique solution is real. Assuming that we use a certified homotopy method such as alphaCertified [48], this approach will correctly classify with probability 1, thus not impacting the overall distribution produced by the acceptance–rejection scheme.
We implemented the above scheme in Julia 1.0.3 using version 0.4.3 of the package HomotopyContinuation.jl [19], employing the solve function with default parameter settings. We deem a solution real if the norm of the imaginary part is less than \(10^{-8}\). Note that this package does not offer certified tracking; however, the failure rate observed in our experiments was very low, namely 0.0512498%—see Table 1. For this reason, we are convinced that the distribution produced by the acceptance–rejection scheme is very close to the true distribution.
We performed the following experiment for estimating the distribution of the condition numbers of GITs of generically complex r-identifiable tensors in perfect tensor spaces with \(r = \frac{\varPi }{\varSigma }\), the complex generic rank. As explained above, we randomly sampled an element of \(\mathbb {R}^{n_1 \times \cdots \times n_d}\) from the density by choosing its entries i.i.d. standard normally distributed. Then, we generated one random starting system and applied the solve function from HomotopyContinuation.jl for tracking the starting solution to the target . If the final solution of the square system was real, we recorded both the regular and angular condition numbers at the CPD of computed via homotopy continuation. These computations were performed in parallel using 20 computational threads until 100, 000 finite, nonsingular, real solutions and corresponding condition numbers were obtained. This experiment was performed on a computer system consisting of 2 Intel Xeon E5-2697 v3 CPUs with 12 cores clocked at 2.6 GHz and 128GB main memory. Information about the sampling process via the acceptance–rejection method is summarized in Table 1, and Fig. 1 visualizes the complementary cumulative distribution functions of the regular and angular condition numbers.
Table 1
Results of sampling GITs in \(\sigma _{r;n_1,n_2,n_3} \subset \mathbb {R}^{n_1 \times n_2 \times n_3}\) via an acceptance–rejection method
Columns three to five list the number of samples where the final tracked solution of the homotopy was real, complex or failed, respectively. The next column shows the fraction of successful samples that were real; in the case of \(n \times n \times 2\) the analytical solution from Bergqvist and Forrester [13] is also stated and the correct digits from the empirical estimate are underlined. The final column indicates the total wall-clock time required to perform the Monte Carlo experiments
In Table 1, the total fractions of solutions that are real when sampling random Gaussian tensors (with i.i.d. standard normally distributed entries) seem to agree very well with the known theoretical results by Bergqvist and Forrester [13]; they showed that for random Gaussian \(n \times n \times 2\) tensors the rank is \(n = \frac{\varPi }{\varSigma }\) with probability \(p_n := \varGamma \bigl (\frac{n+1}{2}\bigr )^n \bigl ( G(n+1) \bigr )^{-1}\), where \(\varGamma \) is the gamma function and G the Barnes G-function (or double gamma function). The correct digits in the numerical approximation are underlined in the penultimate column of Table 1.
Fig. 1
Empirical complementary cumulative distribution function of the regular and angular condition numbers for the tensor spaces from Table 1. Both plots are on the same scale
×
The empirical complementary cumulative distribution functions of the regular and angular condition numbers are shown in Fig. 1. The full lines correspond to the empirical data and the thinner dashed lines correspond to an exponential model fitted to the data. From the figure, it is namely reasonable to postulate that the complementary cumulative distribution function c(x) for large x has the form
which corresponds to a straight line in the log–log plot in Fig. 1. We fitted the parameters a and b of the postulated model to the data restricted to the range \(10^{-1} \le c(x) \le 10^{-3}\). The reason for restricting the data set is that for small condition numbers it is visually evident in Fig. 1 that the model is incorrect and for large condition numbers the data contain few samples, which negatively impacts the robustness of the fit. The parameters were fitted using fminsearch from MATLAB R2017b with starting point (1, 1) and default settings. In all cases, the algorithm terminated because the relative change of the parameters fell below \(10^{-4}\). The obtained parameters are shown in Table 2, along with the coefficient of determination \(R^2\) between the log-transformed data and log-transformed model predictions; 1 indicates perfect correlation.
Table 2
Estimated parameters of the exponential model Eq. (37) fitted to the complementary cumulative distribution functions from Fig. 1
\(n_1 \times n_2 \times n_3\)
Regular
Angular
a
b
\(R^2\)
a
b
\(R^2\)
\(2 \times 2 \times 2\)
0.6624
0.6904
0.9999
1.7288
1.8624
0.9995
\(3 \times 3 \times 2\)
2.2348
0.6636
0.9999
5.5496
1.8856
0.9998
\(4 \times 4 \times 2\)
4.7318
0.6388
0.9997
11.4165
1.8455
0.9994
\(5 \times 4 \times 3\)
22.3141
0.6461
0.9998
102.4887
1.6337
0.9992
\(5 \times 5 \times 2\)
9.8634
0.6436
0.9997
23.6951
1.8662
0.9996
The coefficient of determination \(R^2\) between the log-transformed data and log-transformed model predictions is also indicated
We may estimate the expected values of the regular and angular condition numbers based on their empirical distributions. If p(x) denotes the probability density function of the regular condition number, then
From the postulated model of c(x), we find that \(p(x) = ab x^{-b-1}\) for large x, so that we postulate that the expected value will be well approximated by
for some finite \(\kappa _0\). The expression on the right is finite only if \(b > 1\). The same discussion applies to the angular condition number as well. Regarding the estimated parameters in Table 2, our empirical data strongly suggest that the expected value of the condition number is infinite for \(r = \frac{\varPi }{\varSigma }\) in the tested cases, as \(b \approx 0.6 < 1\). On the other hand, the expected angular condition number seems finite in all cases, as \(b \approx 1.8 > 1\). This suggests that both Theorems 2 and 3 might hold for higher ranks as well.
Acknowledgements
We thank the reviewers for helpful suggestions. Part of this work was made while the second and third author were visiting the Universidad de Cantabria, supported by the funds of Grant 21.SI01.64658 (Banco Santander and Universidad de Cantabria), Grant MTM2017-83816-P from the Spanish Ministry of Science. The third author was additionally supported by the FWO Grant for a long stay abroad V401518N. We thank these institutions for their support.
Open Access
This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
(for the first equality, make the change of variables \(\varphi \rightarrow \pi /2-\varphi \)) where we are denoting \(a=|\langle \mathbf {x},\mathbf {y}\rangle |\in [0,1]\). With the \(+\) sign the inequality is clear (choosing an appropriate k(s)). For the other case, we have, up to a constant k(s), the lower bound
Recall from the definition of \(D(\epsilon )\) that \(\Vert \mathbf {u}^1-\mathbf {v}^1\Vert < \epsilon \), and that \(\frac{9}{10} \Vert \mathbf {u}^1 - \mathbf {v}^1\Vert< \Vert \mathbf {u}^k - \mathbf {v}^k\Vert <\Vert \mathbf {u}^1 - \mathbf {v}^1\Vert \) for \(2\le k\le d\). If \(\epsilon > 0\) is sufficiently small, we can assume
$$\begin{aligned} \delta _k := \langle \mathbf {u}^k, \mathbf {v}^k \rangle \ge \frac{9}{10}, \quad 1 \le k \le d. \end{aligned}$$
having used in the right sequence of inequalities that Eq. (38) implies \(\frac{9}{10} \delta _1 \epsilon _1 \ge \left( \frac{9}{10} \right) ^2 \epsilon _1\). Then,
$$\begin{aligned} z := \delta _1\cdots \delta _d. \end{aligned}$$
(42)
Transforming q(U)
For computing q(U), we will first make a convenient orthogonal transformation of U’s columns. Recall from Eq. (24) that . As in Eq. (22), we write . Then, \(q(U) = q(\begin{bmatrix} M&L_1&L_2 \end{bmatrix})\). The block structure of \(L_1,L_2\in \mathbb {R}^{\varPi \times (\varSigma -1)}\) was given in Eq. (23): \(L_1\) is made up of the d blocks
where \( \dot{U}^k = \begin{bmatrix} \dot{\mathbf{u }}_{2}^{k}&\dot{\mathbf{u }}_{3}^{k}&\cdots&\dot{\mathbf{u }}_{n_k}^{k} \end{bmatrix} \in \mathbb {R}^{n_k \times n_k-1}\) and \(\dot{V}^k = \begin{bmatrix} \dot{\mathbf{v }}_{2}^{k}&\dot{\mathbf{v }}_{3}^{k}&\cdots&\dot{\mathbf{v }}_{n_k}^{k} \end{bmatrix} \in \mathbb {R}^{n_k \times n_k-1} \) are matrices whose columns form an orthonormal basis of \((\mathbf {u}^k)^\perp := \mathrm {T}_{\mathbf {u}^k} {\, \mathbb {S}(\mathbb {R}^{n_k})}\) and \((\mathbf {v}^k)^\perp := \mathrm {T}_{\mathbf {v}^k} {\, \mathbb {S}(\mathbb {R}^{n_k})}\), respectively.
The columns of M are rotated into
(43)
while the columns of \(L_1\) and \(L_2\) are rotated as follows. We define the \(\varPi \times (\varSigma -1)\)-matrices \(R_\downarrow := \begin{bmatrix} R_\downarrow ^1&\ldots&R_\downarrow ^d\end{bmatrix}\) and \(R_\uparrow := \begin{bmatrix} R_\uparrow ^1&\ldots&R_\uparrow ^d\end{bmatrix}\), where
The reason for using \(\downarrow \) and \(\uparrow \) will become clear from the computations below: Inner products of two quantities with arrows pointing in opposite directions are zero, and swapping the directions of both arrows flips a sign in the expression of the inner product.
Now, instead of considering the matrix U we work with the matrix
Note that the choice of \(\dot{U}^k\) and \(\dot{V}^k\) does not affect the value of q. In particular, we may choose the matrices as follows. Let H be the plane in \(\mathbb {R}^{n_k}\) spanned by \(\mathbf {u}^k\) and \(\mathbf {v}^k\). By definition of \(D(\epsilon )\), \(\mathbf {u}^k \ne \pm \mathbf {v}^k\). Let O be the rotation that sends \(\mathbf {u}^k\) to \(\mathbf {v}^k\), but leaves the orthogonal complement \(H^\perp \) of H fixed. Take \(\dot{\mathbf{u }}_{2}^{k} \in H\) with \(\dot{\mathbf {u}}_2^k \perp \mathbf {u}^k\) as the unit norm vector making the smallest angle with \(\mathbf {v}^k\), as follows:
We also take \(\dot{\mathbf{v }}_{2}^{k} := O \dot{\mathbf{u }}_{2}^{k}\), as in the illustration above. If \(\mathbf {h}_3,\ldots , \mathbf {h}_{n_k}\) is any orthogonal basis of \(H^\perp \), then our choice of bases is
$$\begin{aligned} \dot{\mathbf{u }}_{2}^{k} \text { and } \dot{\mathbf{v }}_{2}^{k} = O \dot{\mathbf{u }}_{2}^{k} \text { as above, and for } 3\le j \le n_k: \dot{\mathbf{u }}_{j}^{k} = \dot{\mathbf{v }}_{j}^{k} = \mathbf {h}_j. \end{aligned}$$
(45)
In other words, we can assume that all but the first columns of \(\dot{U}^k\) and \(\dot{V}^k\) are equal. Moreover, as can be seen from the foregoing figure, the following properties hold:
By construction, we have \((\dot{U}^k)^T \dot{U}^k = (\dot{V}^k)^T \dot{V}^k =\mathrm {I}_{n_k-1} \), where \(\mathrm {I}_{n_k-1}\) is the \((n_k-1)\times (n_k-1)\) identity matrix. Furthermore, by our choice of tangent vectors from Eqs. (45) and (46), we have \((\dot{U}^k)^T \dot{V}^k = \mathrm {diag}(\langle \dot{\mathbf{u }}_{j}^{k},\dot{\mathbf{v }}_{j}^{k} \rangle )_{j=2}^{n_k} = \mathrm {diag}(\delta _k, 1,\ldots , 1).\) This implies
From the definition of the vector \(\mathbf {f}\) in Eq. (48), it is clear that we can construct a permutation matrix P that moves the nonzero elements of \(\mathbf {f}\) to the first d positions:
and analogously for \(T_\uparrow \) replacing the subtraction by an addition; the matrices \(S_\downarrow \) and \(S_\uparrow \) contain the remainder of the columns of \(R_\downarrow \) and \(R_\uparrow \), respectively. Then, we have
Hence, by swapping rows and columns of G, which leaves the value of q unchanged because they are orthogonal operations, we find that \(q(G) = q(G')\) with
where we swapped some rows and columns again. Because the smallest singular value of the matrix \(G_\uparrow - z\mathbf {h}\mathbf {h}^T\) is larger than or equal to the smallest singular value of the positive semidefinite matrix \(G'\), we obtain the bound
Note that we used \(2 \left( \frac{9}{10}\right) ^2 (1-\delta _1) = \left( \frac{9}{10}\right) ^2 \Vert \mathbf {u}^1 - \mathbf {v}^1 \Vert ^2 < \Vert \mathbf {u}^k - \mathbf {v}^k \Vert ^2 = 2 (1-\delta _k)\) in the last inequality. As a result, we obtain
The final determinant in Eq. (52) can be computed as follows. Note that \(z \mathbf {h} \mathbf {h}^T\) is a symmetric matrix with one positive eigenvalue and all others zero. Hence, it follows from Weyl’s inequalities [51, Theorem 4.3.7] that the eigenvalues of \(G_\downarrow \) cannot decrease by adding \(z \mathbf {h} \mathbf {h}^T\). Hence,
$$\begin{aligned} \mathrm {disk}_0&:= \Bigl \{ x \in \mathbb {C}\;\;|\;\; | (1-z) - x | \le z \sum _{k=1}^d \epsilon _k \Bigr \}, \text { and}\\ \mathrm {disk}_i&:= \Bigl \{ x \in \mathbb {C}\;\;|\;\; | (1+z) - x | \le z\epsilon _k + z\epsilon _k \sum _{j\ne k} \epsilon _j\Bigr \}, \quad i=1, \ldots , d. \end{aligned}$$
Recall from Eq. (42) that \(z = \delta _1\cdots \delta _d\) and from Eq. (39) that \(\delta _k = \sqrt{\tfrac{1}{1+\epsilon _k^2}}\). By choosing \(\epsilon = \epsilon _1\) small enough, we can get z as close to 1 and \(\epsilon _k \le \epsilon _1\) as close to 0 as we want. Therefore, if we choose \(\epsilon \) small enough, \(\mathrm {disk}_0\) is a small disk near zero, and \(\mathrm {disk}_k\) are small, pairwise overlapping disks near two. When \(\epsilon \) is sufficiently small, \(\mathrm {disk}_0\) is disjoint from the other disks, so that \(\mathrm {disk}_0\) contains exactly 1 eigenvalue close to 0, and \(\bigcup _{i=1}^d \mathrm {disk}_i\) contains d eigenvalues close to 2. Furthermore, since we are dealing with symmetric matrices, all the eigenvalues are real. Therefore, for sufficiently small \(\epsilon \),
$$\begin{aligned} q(G_\uparrow - z \mathbf {h}\mathbf {h}^T) \ge (1 + z - d \epsilon _1)^d \ge 1. \end{aligned}$$
(57)
Finally, plugging Eqs. (53)–(57) into Eq. (52), we find
For the proof of Lemma 9, we need the following two simple results. The first one is a well-known result.
Lemma 16
For \(1\le k\le d\), let \(\mathcal {A}_k \subset \mathbb {R}^{n_k}\) be a linear subspace of dimension \(m_k\) and let \(\mathcal {A}_k^\perp \) be its orthogonal complement. Put \(\mathcal {V} := \mathcal {A}_1 \otimes \cdots \otimes \mathcal {A}_d\) and \(\mathcal {W} := \mathcal {A}_1^\perp \otimes \cdots \otimes \mathcal {A}_d^\perp \) and let and . Then, the tangent spaces and are orthogonal to each other.
Proof
Let us write and . By Eq. (9), all vectors of the form \(\mathbf {a}^1\otimes \cdots \otimes \mathbf {a}^{k-1}\otimes \mathbf {v}\otimes \mathbf {a}^{k+1}\otimes \cdots \otimes \mathbf {a}^d\) for \(1\le k\le d\) and where \(\mathbf {v}\in \mathbb {R}^{n_k}\) constitute a generating set of . A similar statement holds for . Then, by Eq. (10), the inner product between two such generators \(\mathbf {t}:=\mathbf {a}^1\otimes \cdots \otimes \mathbf {a}^{k-1}\otimes \mathbf {v}\otimes \mathbf {a}^{k+1}\otimes \cdots \otimes \mathbf {a}^d\) and \(\mathbf {s}:=\mathbf {b}^1\otimes \cdots \otimes \mathbf {b}^{\ell -1}\otimes \mathbf {w}\otimes \mathbf {b}^{\ell +1}\otimes \cdots \otimes \mathbf {b}^d\) is
because \(d\ge 3\) and \(\langle \mathbf {a}^j, \mathbf {b}^j \rangle =0\) for all \(1\le j\le d\). This completes the proof. \(\square \)
Lemma 17
For all \(1\le k\le d\), let \(\mathcal {A}_k\subset \mathbb {R}^{n_k}\) be a linear subspace of dimension \(m_i\), and define the tensor space \(\mathcal {V} := \mathcal {A}_1\otimes \cdots \otimes \mathcal {A}_d\). Then, the following holds.
1.
\(\mathcal {S}_{n_1,\ldots ,n_d} \cap \mathcal {V}\) is a manifold.
2.
For \(1\le k\le d\), let \(U_k\in \mathbb {R}^{n_k\times m_k}\) be a matrix whose columns form an orthonormal basis for \(\mathcal {A}_k\). The map
Let us write \(U_1\otimes \cdots \otimes U_d\) for the map from (2). It extends to a linear map \(\mathbb {R}^{m_1}\otimes \cdots \otimes \mathbb {R}^{m_d} \rightarrow \mathbb {R}^{n_1}\otimes \cdots \otimes \mathbb {R}^{n_d}\) because of the universal property [44, Chapter 1]. By definition, we have \((U_1\otimes \cdots \otimes U_d)(\mathcal {S}_{m_1,\ldots ,m_d}) = \mathcal {S}_{n_1,\ldots ,n_d} \cap \mathcal {V}\) and \((U_1^T\otimes \cdots \otimes U_d^T)(\mathcal {S}_{n_1,\ldots ,n_d} \cap \mathcal {V}) = \mathcal {S}_{m_1,\ldots ,m_d}\). Hence, \(\mathcal {S}_{n_1,\ldots ,n_d} \cap \mathcal {V}\) is the image of a manifold under an invertible linear map. This implies that \(\mathcal {S}_{n_1,\ldots ,n_d} \cap \mathcal {V}\) itself is a manifold. Furthermore, U preserves the Euclidean inner product, and so the manifolds \(\mathcal {S}_{n_1,\ldots ,n_d} \cap \mathcal {V}\) and \(\mathcal {S}_{m_1,\ldots ,m_d}\) are isometric. \(\square \)
We assumed that \(\sigma _{r-2; n_1-2,\ldots ,n_d-2}\subset \mathbb {R}^{n_1-2}\otimes \cdots \otimes \mathbb {R}^{n_d-2}\) is generically complex identifiable. Then, Proposition 1(2) tells us that \(\mathcal {M}_{r-2;n_1-2,\ldots ,n_d-2}\) is Zariski-open in \((\mathcal {S}_{n_1-2,\ldots ,n_d-2})^{\times (r-2)}\). Fix any tuple . By definition of \(\mathcal {M}_{r-2;n_1-2,\ldots ,n_d-2}\), the least singular value of the derivative of the addition map \(\varPhi : (\mathcal {S}_{n_1-2,\ldots ,n_d-2})^{\times (r-2)}\rightarrow \mathcal {N}_{r-2;n_1-2,\ldots ,n_d-2}\) is positive. This implies that Hence, if \(X_i\) is a matrix whose columns form an orthonormal basis for , we have
Moreover, if we write with \(\Vert \mathbf {x}_i^k\Vert =1\) and , then we have
for all subsets \(\{h_1,\ldots ,h_{d-1}\}\subset \{1,\ldots ,d\}\) of cardinality \(d-1\). Indeed, suppose to the contrary that the foregoing matrix would have linearly dependent columns for some subset; w.l.o.g., we can assume \(h_i = i\) for \(i=1,\ldots ,d-1\). Then, there are nonzero \(\lambda _i\) such that \(\sum _{i=1}^{r-2} \lambda _i \mathbf {x}_{i}^{1}\otimes \cdots \otimes \mathbf {x}_{i}^{d-1} = 0\). Tensoring with an arbitrary vector \(\mathbf {v}\in \mathbb {R}^{n_d-2}\) yields \(\sum _{i=1}^{r-2} \lambda _i \mathbf {x}_{i}^{1}\otimes \cdots \otimes \mathbf {x}_{i}^{d-1} \otimes \mathbf {v} = 0 \otimes \mathbf {v} = 0\), having exploited multilinearity. Note that the ith term in the last sum lives in and can be obtained as a linear combination of the columns of the i-th block of Terracini’s matrix, so that Eq. (12) implies that , which contradicts . We define the following constant, which will play an important role in this proof:
It is important to note that \(\mu > 0\) is only defined through the choice of . The key observation is that we can choose \(\mu \)independently of what follows.
Recall that the restriction of \(\phi \) to \(\mathcal {N}_{2;n_1,\ldots ,n_d} \times (\mathcal {S}_{n_1,\ldots ,n_d})^{\times (r-2)}\) is
In the terminology of Breiding and Vannieuwenhoven [20], \(\mathcal {N}_r^*\) is the join of \(\mathcal {N}_{2;n_1,\ldots ,n_d}\) and \(r-2\) copies of \(\mathcal {S}_{n_1,\ldots ,n_d}\).
Let . By construction, the tensor has multilinear rank bounded by \((2,\ldots ,2)\), meaning that there exists a tensor subspace \(\mathcal {V} = \mathcal {A}_1 \otimes \cdots \otimes \mathcal {A}_d \subset \mathbb {R}^{n_1} \otimes \cdots \otimes \mathbb {R}^{n_d}\) where the linear subspace \(\mathcal {A}_k \subset \mathbb {R}^{n_k}\) has \(\dim \mathcal {A}_k = 2\) and such that . For each \(1\le k\le d\), we denote the orthogonal complement of \(\mathcal {A}_k\) in \(\mathbb {R}^{n_k}\) by \(\mathcal {A}_k^\perp \). Let us define \(\mathcal {W} := \mathcal {A}_1^\perp \otimes \cdots \otimes \mathcal {A}_d^\perp \).
Now, we make the following choice of rank-1 tensors : for \(1\le k \le d\) let \(U_k \in \mathbb {R}^{\varPi \times n_k-2}\) be a matrix whose columns form an orthonormal basis of \(\mathcal {A}_k^\perp \). Then, by Lemma 17, the map
is an isometry of manifolds. For \(1\le i\le r-2\), we define , where are the rank-1 tensors from above. We write . Because U is an isometry, , so we can choose \(\Vert \mathbf {a}^1_i \Vert = \cdots =\Vert \mathbf {a}^d_i\Vert = 1\). The plan for the rest of the proof is to show that is a finite value which does not depend on , and that there is a neighborhood around , whose size is also independent of , on which the Jacobian does not deviate too much.
For showing this, we first compute the derivative of \(\phi \) at the point :
where . Let \(V\in \mathbb {R}^{\varPi \times 2\varSigma }\) be a matrix whose columns form an orthonormal basis of , and for \(1\le i\le r-2\) let \(W_i\in \mathbb {R}^{\varPi \times \varSigma }\) be a matrix whose columns form an orthonormal basis of . Then, we have
(58)
Let us write with . From [25, Corollary 2.2], we know that . Moreover, by Eq. (11), . Since are, by assumption, elements of \(\mathcal {W}\), Lemma 16 implies that is orthogonal to for all \(1\le i\le r-2\). Therefore, we get the following equation for Eq. (58):
Because \(\mathbf {a}_i^k\in \mathcal {A}_k^\perp \) for \(1\le i\le r-2\), and because \(\Vert \mathbf {a}_i^j\Vert =1\), the tensors listed even form orthogonal bases for \(\mathcal {K}_i\) and \(\mathcal {L}_i\), respectively. Furthermore, we have for all pairs of indices i, j that
Therefore, we have the following orthogonal decomposition:
The columns of \(UX_i\) form an orthonormal basis of . Altogether, we have
The rest of the proof is a variational argument: Let us denote by \(\mathrm {Gr}(\varSigma ,\varPi )\) the Grassmann manifold of \(\varSigma \)-dimensional linear spaces in \(\mathbb {R}^\varPi \). We endow \(\mathrm {Gr}(\varSigma ,\varPi )\) with the standard Riemannian metric, such that the distance between two spaces is the Euclidean length of the vector of principal angles [14]. Let us denote this distance by \(d(\cdot ,\cdot )\). Furthermore, let be the Gauss map.
From Breiding and Vannieuwenhoven [23, Proposition 4.3], we get for each \(1\le i\le r-2\) that . This means, that for \(\epsilon >0\) and any tuple satisfying for \(1\le i\le r-2\), we have for sufficiently small \(\epsilon \). Let \(W_i'\in \mathbb {R}^{\varPi \times \varSigma }\) be a matrix with orthonormal columns that span . Consequently, there is a constant \(K>0\), which depends only on \(n_1,\ldots ,n_d\), such that \(\Vert W_i - W_i'\Vert <\epsilon K\sqrt{\varSigma }\).
Recall that the columns of \(\left[ {\begin{matrix} W_1&\cdots&W_{r-2}\end{matrix}}\right] \) are orthogonal to the columns of V. Moreover, \(r\varSigma \le \varPi \), since we have assumed that \(\sigma _{r;n_1,\ldots ,n_d}\) is generically complex identifiable. Hence, there is a matrix \(M\in \mathbb {R}^{\varPi \times \varPi }\) with \(MV=V\) and \(MW_i=W_i'\) for \(1\le i\le r-2\) that leaves the orthogonal complement of \(V+W_1+\cdots +W_{r-2}\) fixed. This implies
where \(I_\varPi \) is the \(\varPi \times \varPi \) identity matrix. Therefore, if we choose \(\epsilon \) small enough, we may assume \(\det M > \tfrac{1}{2}\). Note that such a choice of \(\epsilon \) is independent of .
Altogether, we have shown that for all tuples satisfying we have that
and both \(\epsilon \) and \(\mu \) have been chosen independent of . This concludes the proof. \(\square \)
The proof is similar to the proof of Lemma 3. Integrating in polar coordinates, we have
Note that the argument of q is a \(\varPi \times (2\varSigma -2)\) matrix. Since \(q(A) = \varsigma _1(A) \cdots \varsigma _{n-1}(A)\) for \(A \in \mathbb {R}^{m \times n}\) with \(n\le m\), we have
First, note that the left-hand term in (34) is bounded above by a constant depending on \(n_1,\ldots ,n_d,d\). Thus, by choosing an appropriate constant K in (34) we can assume that is smaller than any predefined quantity. We thus assume from now on that for some \(\epsilon >0\) that can be chosen as small as desired. Furthermore, as in Eq. (39), we write
We also assume that \(\delta _1 = \min \{\delta _1,\ldots ,\delta _d\}\), or, equivalently, \(\epsilon _1 = \max \{\epsilon _1,\ldots ,\epsilon _d\}\). Note that if \(\epsilon \approx 0\), then one can assume \(\epsilon _k \approx 0\) and \(\delta _k\approx 1\) for all \(1\le k\le d\). In particular, all inequalities from the proof of Lemma 6 in Appendix A.3 are still valid here.
so that \(AB = (\mathrm {I}-MM^\dagger )\begin{bmatrix} \cos (\theta ) L_1&\sin (\theta ) L_2\end{bmatrix}\). Observe that, by definition, A ultimately depends on and ; that is, .
Recall from Eq. (8) that \(q(\cdot )\) is the product of all but the smallest singular value of its argument. We first show that \(q(AB)\le q(A)\). To see this, let \(\varsigma _1 \ge \cdots \ge \varsigma _{2(\varSigma -1)} \ge 0\) be the singular values of A. Then,
Moreover, for \(0\le \theta \le \tfrac{\pi }{2}\) we have \(0\le \cos (\theta )\le 1\) and \(0\le \sin (\theta )\le 1\). Altogether, this implies \(q(AB)\le \varsigma _1\cdots \varsigma _{2(\varSigma -1)-1} = q(A)\). In the rest of the proof, we bound the \(\varsigma _i\)’s.
Simplifying the Matrix by Orthogonal Transformations
Recall from the proof of Lemma 6 that applying the orthogonal transformation in Eq. (44) on the right, we have
where \(P = M M^\dagger \). Let \(\mathbf {a}_\uparrow \) and \(\mathbf {a}_\downarrow \) be as in Eq. (43). The matrix \(M M^\dagger \) projects orthogonally onto the span of and , which coincides with the span of the orthonormal vectors \(\frac{\mathbf {a}_\uparrow }{\Vert \mathbf {a}_\uparrow \Vert }\) and \(\frac{\mathbf {a}_\downarrow }{\Vert \mathbf {a}_\downarrow \Vert }\). Moreover, by Eq. (47) we have \(\mathbf {a}_\downarrow ^T \mathbf {a}_\downarrow = 1+z\) and \(\mathbf {a}_\uparrow ^T \mathbf {a}_\uparrow = 1-z\). This shows that
so that the singular values of \(\widetilde{N}\) are given by the square roots of the eigenvalues of the matrices on the block diagonal.
Bounding the Singular Values
In the remainder, let \(\lambda _i(A)\) denote the ith largest eigenvalue of the positive semidefinite matrix A. Since \(0 < \delta _k \le 1\) for all \(1\le k\le d\), the eigenvalues \(1+z\delta _k^{-1} = 1 + \prod _{j\ne k}\delta _j\) for \(1\le k\le d,\) of the diagonal matrix \(F_\uparrow \) satisfy
The eigenvalues of \(E_\downarrow + \frac{z}{1+z} \mathbf {g}\mathbf {g}^T\) can be bounded by using that the spectral norm of the rank-1 term is bounded by \(\Vert \mathbf {g}\Vert ^2 = \sum _{k=1}^d \epsilon _k^2 \le d \epsilon _1^2\). It follows from Weyl’s perturbation inequality; see, e.g., [51, Corollary 7.3.8], and the positive semidefiniteness of \(E_\downarrow + \frac{z}{1+z} \mathbf {g}\mathbf {g}^T\) that
provided that \(\epsilon \) is sufficiently small. The eigenvalues of the diagonal matrix \(E_\downarrow \) are bounded from above by \(C (d+1) \epsilon _1^2\) due to Eq. (54). Putting all of these together and using \(d \ge 1\), we find
$$\begin{aligned} \lambda _i\left( E_\downarrow + \frac{z}{1+z} \mathbf {g}\mathbf {g}^T \right) \le C' d (1 - \delta _1), \quad i = 1,\ldots , d, \end{aligned}$$
(62)
for some universal constant \(C'>0\).
For computing an upper bound on the eigenvalues of \(E_\uparrow - \frac{z}{1-z} \mathbf {g}\mathbf {g}^T\), we start by noting that
the spectral norm of the last diagonal matrix is bounded by \(C (d+1) \epsilon _1^2\) because of Eq. (54). Adding the matrix \(2\mathrm {I}_d\) causes all eigenvalues to be shifted by 2; hence, it suffices to compute the nonzero eigenvalue of the rank-1 matrix. Its eigenvalues are
the eigenvector corresponding to the last eigenvalue is \(\frac{\mathbf {g}}{\Vert \mathbf {g}\Vert }\). In order to bound that eigenvalue, note that from (55) and (54) we have for some constant \(c=c(d)>0\):
where the last inequality is proved as follows. Note that \(\sqrt{1+t^2}\le 1+\frac{t^2}{2}\), which can be verified by squaring the terms and comparing. Then,
where \(p=p(\epsilon _1,\ldots ,\epsilon _d)\) is a polynomial expression in the \(\epsilon _i\) of degree and coefficients bounded by a constant depending only on d, with all its monomials of degree at least 4 in \(\epsilon _1,\ldots ,\epsilon _d\). Hence, for some constant \(c=c(d)\) we have \(|p|\le c(d)\epsilon _1^4\) and we conclude that
for some new constant \(\hat{c}(d)\); the last step follows from Eq. (40).
Putting all of the foregoing together with Eq. (61), we have thus shown that \(E_\uparrow - \frac{z}{1-z} \mathbf {g}\mathbf {g}^T\) has eigenvalues satisfying
where \(c'(d)\) is again a constant depending only on d.
In Eqs. (59), (60), (62) and (63), we have shown that precisely \(\varSigma -d-1 + d + 1 = \varSigma \) eigenvalues are smaller than some constant times \(1 - \delta _1\), while the remaining eigenvalues are clustered near 2. It follows that there exists a constant K, depending only on \(n_1, \ldots , n_d\) and d, such that
where the last step is by lemma 5. This finishes the proof. \(\square \)
the inequality is due to the change of variables \(\sin (2\theta )=1-t\) and \(\sqrt{2t-t^2}\ge \sqrt{t}\) for \(|t|\le 1\). Let us write \(h:= \langle \mathbf {x},\mathbf {y}\rangle \). We distinguish between two cases. In the case \(h\le \tfrac{1}{2}\), we can bound
We prove the lemma by induction. The first case \(d=1\) reads \(\cos (\theta _1) \le 1-\tfrac{\theta _1^2}{7}\). In fact, in this case we have the stronger inequality \(\cos (\theta ) \le 1-\tfrac{\theta ^2}{4}\) as the following argument shows: Consider the map \(f:[0,\tfrac{\pi }{2}] \rightarrow \mathbb {R}, \theta \mapsto 1 - \tfrac{\theta ^2}{4} - \cos (\theta )\). We have \(f(0)=0\) and \(f(\tfrac{\pi }{2}) = 1 - \tfrac{\pi ^2}{16}>0\). Moreover, \(f'(\theta )=\sin (\theta )- \tfrac{\theta }{2}>0\) for \(0\le \theta \le \tfrac{\pi }{2}\). This implies that we have \(f\ge 0\) proving the case \(d=1\). For general d, note that by the induction hypothesis
This is exactly the concern of Remark 1: What computational problem are we interested in solving when a tensor has several distinct CPDs? Are we interested in the CPD with the best sensitivity? Or the worst? Or the expected condition number of one randomly chosen CPD in the fiber? This depends on the context. The results of this paper are valid regardless of the particular variation of the problem one is interested in.
The integer d is called the order of
. The tensor product of d vectors \(\mathbf {u}^{1} \in \mathbb {R}^{n_1},\ldots , \mathbf {u}^{d} \in \mathbb {R}^{n_d}\) is defined to be the tensor \(\mathbf {u}^{1} \otimes \cdots \otimes \mathbf {u}^{d} \in \mathbb {R}^{n_1 \times \cdots \times n_d}\) with entriesAny nonzero multidimensional array obeying this relation is called a rank-1 tensor. Not every multidimensional array represents a rank-1 tensor, but every tensor
is a finite linear combination of rank-1 tensors:
Hitchcock [50] coined the name polyadic decomposition for the decomposition Eq. (1). The smallest number r for which
admits an expression as in Eq. (1) is called the (real) rank of
. A corresponding minimal decomposition is called a canonical polyadic decomposition (CPD).
, the condition number must be defined at a decomposition
. However, in this article, we will restrict our analysis to tensors
having a unique decomposition. Such tensors are called identifiable. In this case, the condition number of the tensor rank decomposition of a tensor
is well-defined, and we denote it by
. We will explain in Section 1.3 in greater detail the notion of identifiability of tensors. At this point, the reader should mainly bear in mind that the assumption of being identifiable is comparably weak as most tensors of low rank satisfy it. However, note that matrices (\(d=2\)) are never identifiable, so we assume that the order of the tensor is \(d\ge 3\).
of rank r, compute the set of rank-1 terms
in the decomposition Eq. (1). This condition number measures the sensitivity of the rank-1 terms with respect to perturbations of the tensor
. In other words, when the condition number
of the rank-r identifiable tensor
in Eq. (1) is finite, it is the smallest value
such that
holds for all rank-r tensors
(with
of rank 1) sufficiently close to
. Herein, the norm on \(\mathbb {R}^{n_1\times \cdots \times n_d}\) is the usual Euclidean norm, and \(\mathfrak {S}_r\) is the permutation group on \(\{1,\ldots ,r\}\). It was shown in [24, Corollary 5.5] that the same expression holds if
is any tensor close to
and
is the best rank-r approximation of
in the Euclidean norm.
.
for a given
in [20] requires the CPD of
itself. This forces us to rely on probabilistic studies to establish reasonable a priori values of the condition number. Settling this is the main purpose of this paper.
and studying
. The probabilistic study is feasible, in principle, because one can obtain a closed expression for
which is polynomial in terms of the \(\mathbf {u}_{i}^{k}\), so that the question boils down to an explicit but nontrivial integration problem.
is chosen at random within the set of rank-r tensors (see the definition of random tensors in Definition 1 and the extension in Theorem 4) and we wonder about the expected value of
. The difficulty now is that even if we assume that a decomposition (1) exists, we do not have it and hence we lack a closed expression for
.
as in Eq. (1), output the set of normalized rank-1 tensors
” will be called the angular condition number
. Analogously to the bound Eq. (2), one can show that when \(\kappa _{\mathrm {ang}}\) is finite, it is the smallest number such that
for all rank-r tensors
(with
rank-1 tensors) in a sufficiently small open neighborhood of
. By Breiding and Vannieuwenhoven [24, Corollary 5.5], the same expression holds for all tensors
in a small open neighborhood of
if
is the best rank-r approximation of
.
where
is as in Eq. (1). One could conclude from this that a tensor decomposition algorithm should aim to produce the normalized rank-1 terms
from the tensor rank decomposition
accurately. Once these terms are obtained, one can recover the \(\lambda _i\)’s by solving a linear system of equations. Since, as a general principle, the condition number of a composite smooth map \(g \circ f\) between manifolds satisfies [16, 28]it follows that the condition number of tensor decomposition is bounded by the product of the condition numbers of the problem of finding the angular part of the CPD and the condition number of solving a linear least-squares problem. Our main results suggest that precisely the last problem will on average be ill-conditioned.
randomly, and then apply the algorithm to the associated tensor
. However, our analysis in this paper and the analyses in [11, 23] show that this procedure generates tensors that are heavily biased toward being numerically well-conditioned. Hence, this way of testing algorithms probably does not correspond to a realistic distribution on the inputs. We acknowledge that it is currently not easy to sample rank-r tensors uniformly even though some methods exist [18]. In part, this is because equations for the algebraic variety containing the tensors of rank bounded by r are hard to obtain [57]. Nevertheless, in Sect. 7, using the observation from Remark 2, we present an acceptance–rejection method that can be applied to a few cases and yields uniformly distributed rank-r tensors, relative to the Gaussian density in Definition 1. In any case we strongly advocate that the (range of) condition numbers are reported when testing the performance of iterative methods for solving the tensor rank decomposition problem, so that one can assess the difficulty of the problem instances. We believe it is always recommended to include models that are known to lead to instances with high condition numbers, such as those used in [20, 22].
is called r-identifiable if there is a unique set
of cardinality r such that
and all
’s are rank-1 tensors. A celebrated criterion by Kruskal [55] gives a tool to decide if a given tensor of order 3 satisfies this property.
a tensor of order 3 and assume that
where
Define the factor matrices \(U_\ell = [\mathbf {u}_{i}^{\ell }]_{1\le i \le r} \in \mathbb {F}^{n_\ell \times r}\) for \(\ell =1,2,3\), and let \(k_\ell \) be the largest integer k such that every subset of k columns of \(U_\ell \) has rank equal to k. If \( r \le \frac{1}{2}( k_1 + k_2 + k_3 - 2) \) and \(k_1, k_2, k_3 > 1\), then the tensor
is r-identifiable over \(\mathbb {F}\).
that satisfies the assumptions of Lemma 1 is r-identifiable over \(\mathbb {R}\) and also automatically r-identifiable over \(\mathbb {C}\). In other words, Kruskal’s criterion is certifying complex r-identifiability of tensors, which is a strictly stronger notion than r-identifiability over \(\mathbb {R}\) [5].
This constructible1 set turns out to be an open dense subset (in the Euclidean topology) of its Zariski closure \(\overline{\sigma _{r;n_1,\ldots ,n_d}^\mathbb {C}}\); see [57]. One says that \(\sigma _{r;n_1,\ldots ,n_d}^\mathbb {C}\) is generically complex r-identifiable if the subset of points of \(\sigma _{r;n_1,\ldots ,n_d}^\mathbb {C}\) that are not complex r-identifiable is contained in a proper closed subset in the Zariski topology on the algebraic variety \(\overline{\sigma _{r;n_1,\ldots ,n_d}^\mathbb {C}}\); see [32]. It is known from dimensionality arguments [32] that there is a maximum value of r for which generic r-identifiability of \(\sigma _{r;n_1,\ldots ,n_d}\) can hold, namelyIn fact, it is conjectured that the inequality is strict in general; see [47] for details. For all other values of r, generic r-identifiability does not hold. In [17, 32, 33, 40], it is proved that in the majority of choices for \(n_1, \ldots , n_d\), generic complex r-identifiability holds for most ranks with \(r < r_\text {crit}\); see [17, Theorem 7.2] for a result that is asymptotically optimal. For a summary of the conjecturally complete picture of complex r-identifiability results, see [34, Section 3].
Then, under Assumption 1, there exists an open dense subset \(\mathcal {N}_{r;n_1,\ldots ,n_d}\) of \(\sigma _{r;n_1,\ldots ,n_d}\) such that for all
we have
by Beltrán et al. [11, Proposition 4.5–4.7].2 In particular, the points in the fiber are isolated, so there is a local inverse map
of \(\varPhi \) for each
. Recall from [20] that the condition number of the CPD at
is then the condition number (in the classic sense of Rice [61]; see also [28, 69]) of any of these local inverses:
where
is arbitrary; it is a corollary of Breiding and Vannieuwenhoven [20, Theorem 1.1] that the above definition does not depend on the choice of
. Herein, \(\Vert \cdot \Vert \) in the denominator is the Euclidean norm induced by the ambient \(\mathbb {R}^{n_1\times \cdots \times n_d}\), and the norm in the numerator is the product norm of the Euclidean norms inherited from the ambient \(\mathbb {R}^{n_1\times \cdots \times n_d}\)’s. The right-hand side
is the spectral norm of the derivative of \(\varPhi _a^{-1}\) at
. See Sect. 2 for more details. By Breiding and Vannieuwenhoven [20, Proposition 4.4], the condition number
does not depend on the norm of
:
for \(t\in \mathbb {R}{\setminus }\{0\}\).
. The main reason is that our analysis is independent of the values that the condition number takes on this set of measure zero, so that for simplicity we decided against including the more complicated general case where there can be several distinct elements in the preimage.
on \(\sigma _{r;n_1,\ldots ,n_d}\) by specifying its density as
is the normalization constant. Under Assumption 1, if
and
, we say that
is a Gaussian Identifiable Tensor (GIT) of rank r.
of rank r has the distribution
, where
is a tensor with independent and identically distributed (i.i.d.) standard Gaussian entries. We exploit this fact in our numerical experiments to sample GITs using an acceptance–rejection method.
be a GIT of rank \(r= 2\). Then,
, \(r \ge 3\), we have
we have
for allwhere \( \lim _{n_1,\ldots ,n_d \rightarrow \infty } \epsilon _{n_1,\ldots ,n_d} \rightarrow 0. \)
have positive dimension [46]. It follows from Breiding and Vannieuwenhoven [20] that the condition number of the tensor rank decomposition problem at each expression Eq. (1) of length r of such a tensor
is \(\infty \). In this case,
, regardless of how the tensor decomposition problem is defined3 when
has multiple distinct decompositions; see also the discussion in [28, Remark 14.14]. In this case the average condition number is infinite, as well.
be a GIT of rank \(r\ge 2\). Then,
is
where
is an arbitrary local inverse of \(\varPhi \) with
. As before we do not specify what happens on the measure-zero set \(\sigma _{r;n_1,\ldots ,n_d}{\setminus }\mathcal {N}_{r;n_1,\ldots ,n_d}\), because it is not relevant for this paper. The angular condition number only accounts for the angular part of the CPD, i.e., the directions of the tensors, not for their magnitude, hence the name.
for tensors of rank two that we prove in Sect. 5.
be a GIT of rank 2. Then,
.
be a GIT of rank r. Then,
.
has a density \(\hat{\rho }\) for which there exists positive constants \(c_1,c_2\) such that \(c_1 \le \frac{{\hat{\rho }}}{\rho } \le c_2\).
in the unit sphere \({\mathbb {S}}(\sigma _r)\).
in the unit ball
.
,
), and manifolds and linear spaces in a different calligraphic font (\(\mathcal {A}, \mathcal {B}\)).
and \(\mathbf {a} \in \mathbb {R}^{n_1 \cdots n_d}\) is its coordinate array with respect to an orthogonal basis, then
. Similarly, if the coordinates \(\mathbf {a}\) are reshaped into a multidimensional array \(A \in \mathbb {R}^{n_1 \times \cdots \times n_d}\), then
. It is important to note that this notation can conflict with the usual meaning of \(\Vert A\Vert \) when \(d=2\); to distinguish the spectral norm from the standard norm in this paper, we write \(\Vert A\Vert _2\) for the former; see Eq. (7).
it is a semialgebraic set of dimension at most \(\min \{r\varSigma , \varPi \}\); see, e.g., [60]. Under Assumption 1, the dimension of \(\sigma _{r;n_1,\ldots ,n_d}\) is exactly \(r\varSigma \).
of rank-1 tensors satisfying all of the following properties: The set of r-nice tensors is \(\mathcal {N}_{r;n_1,\ldots ,n_d}:=\varPhi (\mathcal {M}_{r;n_1,\ldots ,n_d})\).
is a smooth point of the algebraic variety \(\overline{\sigma _{r;n_1,\ldots ,n_d}}\);
is complex r-identifiable; and
.
, where the
are rank-1 tensors. For each i let \(U_i\) be a matrix whose columns form an orthonormal basis of
. Then,
The matrix \(U=[U_1, \ldots , U_r]\in \mathbb {R}^{\varPi \times r\varSigma }\) is also called a Terracini matrix. An explicit expression for the \(U_i\)’s is given in [20, equation (5.1)].
uniquely depends on
, we can view the condition number of
as a function of
:
where the matrices \(U_i\) are as before. The benefit of Eq. (13) is that it is well-defined for any tuple
(and not just those mapping into \(\mathcal {N}_{r,n_1,\ldots ,n_d}\)).
has cardinality
. By composing \(\varPsi := \psi \times \psi \) with the addition map from Eq. (4), we get the following alternative representation of tensors of rank bounded by 2:We would like to apply the coarea formula Eq. (15) to pull back the integral of
over \(\sigma _{2}\) via the parameterization \(\varPhi \circ \varPsi \). However, \(\sigma _{2}\) in general is not a manifold, so the formula does not apply. Nevertheless, we can use the manifold \(\mathcal {N}_{2}\) of 2-nice tensors instead. By Proposition 1(3), \(\mathcal {N}_2\) is Zariski open in \(\sigma _2\), so that
where \(C_2 := C_{2;n_1,\ldots ,n_d}\) is as in Definition 1. By applying the coarea formula Eq. (15) to the smooth map \(\varPhi \mid _{\mathcal {M}_2}\), we get
where
is the Jacobian determinant of \(\varPhi \) at
. In the first equality, we used
for 2-identifiable tensors; indeed, we have that
and
because
has rank equal to 2.
. Since \(\mathcal {M}_{2}\) is also Zariski open in \(\mathcal {S} \times \mathcal {S}\) by Proposition 1(2), we may replace the integral over \({\mathcal {M}}_{2}\) by an integral over \(\mathcal {S} \times \mathcal {S}\), thus obtaining
We use the coarea formula again, but this time for \(\varPsi = \psi \times \psi \), where \(\psi \) is the parameterization from Eq. (17). Note that for
we have
. We get
where
and
are both tuples in \((0,\infty ) \times \mathcal {P}\). Next, we compute the Jacobian determinant
.
and
be tuples in \((0,\infty ) \times \mathcal {P}\) with \(\mathcal {P}\) as in Eq. (16). In the following, we write
The Jacobian determinant of \(\varPhi \circ \varPsi \) at
is, by definition, the absolute value of the determinant of the linear map
Consider the matrix of partial derivatives of \(\varPhi \circ \varPsi \) with respect to the standard orthonormal basis of \(\mathbb {R}^{n_1\times \cdots \times n_d}\):whereThen, the Jacobian determinant of \(\varPhi \circ \varPsi \) at
is
The latter is the volume of the parallelepiped spanned by the columns of Q. We fix notation in the next definition.
The reason why we write the partial derivatives of \(\varPhi \circ \varPsi \) with respect to the standard basis of \(\mathbb {R}^{n_1\times \cdots \times n_d}\) is that we get the following convenient description:
For describing L, let for each \(1\le k \le d\),be matrices containing as columns an ordered orthonormal basis of \((\mathbf {u}^k)^\perp = \mathrm {T}_{\mathbf {u}^k} {\, \mathbb {S}(\mathbb {R}^{n_k})}\) and \((\mathbf {v}^k)^\perp = \mathrm {T}_{\mathbf {v}^k} {\, \mathbb {S}(\mathbb {R}^{n_k})}\), respectively. Then, by linearity and the product rule of differentiation, we have that \(L = \begin{bmatrix} \lambda L_1&\mu L_2 \end{bmatrix}\) is the block matrix consisting of 2 blocks of the formBoth \(L_1\) and \(L_2\) have \(\sum _{k=1}^d (n_k-1) = \varSigma -1\) columns. Note that M depends only on the \(\mathbf {u}^k\)’s and \(\mathbf {v}^k\)’s, whereas L also depends on the parameters \(\lambda \) and \(\mu \); we do not emphasize these dependencies in the notation.
in
. Analogously, the columns of \(L_2\) form an orthonormal basis for the orthogonal complement of
in
. Consequently, for
, Terracini’s matrix from Eq. (12) can be chosen as
This entails that
having used the notation from Definition 3 and the fact that singular values are invariant under orthogonal transformations such as permutations of columns.
is the inverse of the smallest singular value of the Terracini’s matrix U from Eq. (24). Therefore, if we plug Eqs. (24) and (25) into (18), then we get
where \( {q(U) = \frac{\mathrm {vol}(U)}{\varsigma _{\min }(U)}} \) is as in Eq. (8), and
From Eq. (24), it is clear that U is a function of
and
but is independent of \(\lambda \) and \(\mu \). Therefore, if we integrate first over \(\lambda \) and \(\mu \), then we can ignore the factor q(U). In Appendix A.1, we compute this integral; the result is stated here as the next lemma.
where
and
.
Next, we exploit the symmetry of the domain \(\mathbb {S}(\mathbb {R}^{n_1})\) by flipping the sign of \(\mathbf {v}^1\) and, hence, of
. This substitution transforms U into UD, where D is a diagonal matrix with some pattern of \(\pm 1\) on the diagonal. Since D is orthogonal, \(q(U) = q(UD)\), so that
Denote this last integral by J, and then, it remains to show that \(J=\infty \). Consider the open set
Since \(D(\epsilon )\) is open, we have
We now need two lemmata. The first one is straightforward.
with
and
, we have
where
and
.
and exploit \(\Vert \mathbf {u}^k - \mathbf {v}^k\Vert \le \Vert \mathbf {u}^1 -\mathbf {v}^1\Vert \) for all \(k=1,\ldots ,d\). The lower bound follows from
having used \(0 < \langle \mathbf {u}^k, \mathbf {v}^k \rangle \le 1\) for sufficiently small \(\epsilon \). \(\square \)
where \(c>0\) is some constant. Note that the integrand in this equation only depends on \(\mathbf {u}^1\) and \(\mathbf {v}^1\). By definition of \(D(\epsilon )\), for each \(2\le k \le d\), and if we fix \(\mathbf {u}^k\), the domain of integration of \(\mathbf {v}^k\) contains the difference of two spherical caps of respective affine radii \(\frac{9}{10} \Vert \mathbf {u}^1 - \mathbf {v}^1 \Vert \) and \(\Vert \mathbf {u}^1 - \mathbf {v}^1 \Vert \). From Eq. (14), the volume of this difference of caps is greater than a constant times \(\Vert \mathbf {u}^1 - \mathbf {v}^1 \Vert ^{n_j-1}\). Therefore, if we keep \(\mathbf {u}^1,\mathbf {v}^1 \in \mathbb {S}(\mathbb {R}^{n_1})\) constant and integrate over \(\mathbf {u}^k, \mathbf {v}^k \in \mathbb {S}(\mathbb {R}^{n_k})\), \(k=2,\ldots ,d\), then we getwhere \(c'>0\) is a constant. Recall that \(\varSigma = 1 + \sum _{k=1}^d (n_k - 1)\), so thatBy rotational invariance, the inner integral does not depend on \(\mathbf {u}^1\) and moreover for small \(\epsilon \) projecting through the stereographic projection (which has a Jacobian bounded above and below by a positive constant close to its center) we conclude that, for some other constant \(c''\), This proves \(J = \infty \), so that
for tensors of rank bounded by 2, constituting a proof of Theorem 1.
and
be \(n_1 \times \cdots \times n_d\) tensors, where the
and
are rank-1 tensors. If
is \((r+s)\)-identifiable, then we have
is r-identifiable, and
is s-identifiable. Indeed, if the tensor
is \((r+s)\)-identifiable, then the unique set C of cardinality \(|C| \le r\) consisting of rank-1 tensors summing to
is
. If
had an alternative decomposition
, potentially of a shorter length \(r' \le r\), then
would be an alternative decomposition of
. Hence,
needs to equal
, so that
is r-identifiable. By symmetry, the result for
follows. For all i, let \(U_i\) be a matrix with orthonormal columns that span
, and \(V_i\) be a matrix with orthonormal columns that span
. Consider the matrices \(U=[U_1,\ldots ,U_r]\) and \(V=[V_1,\ldots ,V_s]\). By Eq. (12), we have
The claim follows from standard interlacing properties of singular values; see [51, Chapter 3]. \(\square \)
The following holds. 
be r-identifiable. Then,
.
there exists a tuple
with
and
where \(\phi \) is as in Lemma 8.
, by taking a sequence
converging to
one can generate the corresponding sequences
from Lemma 9. Now, by compactness we can find an accumulation point
. Since \(\mathrm {Jac}(\phi )\) is continuous and hence uniformly continuous when restricted to a compact set, by choosing small enough \(\epsilon \) we can assure that for all
,
and for all
, we have
, where \(\epsilon \) and \(\mu \) do not depend on
.
for \(t>0\), there exists a tensor
such that for every \(\delta >0\) we have
From Lemma 9 and Remark 5, there exist tensors
such that
for all
such that
, and
. Let \(\mathcal {U}\subseteq \mathcal {N}_2\times \mathcal {S}^{\times r-2}\) be the set of all
satisfying the foregoing conditions. From Lemma 7, we have
Moreover, by Lemma 9 and the inverse function theorem, by taking small enough \(\epsilon \) and \(\delta \) we can assume that \(\phi |_\mathcal {U}\) is a diffeomorphism onto its image4 and hence \(\phi (\mathcal {U})\) is open. The coarea formula Eq. (15) thus applies yielding
The theorem follows since \(\phi (\mathcal {U})\subseteq \sigma _r\). \(\square \)
where \(p: \mathbb {R}^{n_1\times \cdots \times n_d} \rightarrow \mathbb {S}(\mathbb {R}^{n_1\times \cdots \times n_d})\) is the canonical projection onto the sphere and where
is a local inverse of \(\varPhi :\mathcal {S} \times \mathcal {S} \rightarrow \sigma _2\) at
with
. As before, the value of \(\kappa _{\mathrm {ang}}\) on \(\sigma _2{\setminus }\mathcal {N}_2\) is not relevant for our analysis, so we do not specify it.
is differentiable at
. The projection p is also differentiable, so that
where \(\Vert \cdot \Vert _2\) is the spectral norm from Eq. (7). We compute this norm.
and
. Then, by linearity of the derivative, we have
. Furthermore, for \(i=1,2\), the derivative
is the orthogonal projection onto the orthogonal complement of
in \(\mathbb {R}^\varPi \). According to this, we decompose
and
as
Then, we have
and, consequently,
Recall from Eq. (20) the matrices \(L=\begin{bmatrix} \lambda L_1&\mu L_2\end{bmatrix}\) and
. We can find vectors \(\mathbf {x}_1,\mathbf {x}_2 \in \mathbb {R}^{\varSigma -1}\) with
and
, and such that
and
. Observe that
and
. This yields
Writing
Since we are assuming that \((\mathrm {I}- MM^\dagger )L\) is injective (for \(\varsigma _{\min }((\mathrm {I}-MM^\dagger )L)\ne 0\)), it has a left inverse and we can write
Combining Eqs. (30) and (31), we see that
the second equality from \( \left( PL\right) ^\dagger P= \left( PL\right) ^\dagger \), which is a basic property of the Moore–Penrose pseudo-inverse holding for any orthogonal projector P. This finishes the proof. \(\square \)
where \(C_2 = C_{2;n_1,\ldots ,n_d}\) is as in Definition 1, \(\mathcal {P}\) is as in Eq. (16), \(Q = \begin{bmatrix} L&M \end{bmatrix}\) is as in Eq. (19), the volume \(\mathrm {vol}\) is as in Definition 3, and
is as in Eq. (27), so that
. Next, we relate \(\mathrm {vol}(Q)\) to the volume of \((\mathrm {I}- M M^\dagger )L\).
where q is as in Eq. (8). Recall from Eq. (22) that M is independent of \(\lambda \) and \(\mu \). We first compute the integral over \(\lambda , \mu \) using the next lemma. We prove the lemma in Appendix C.1.
Then,
where
In the remaining part of this section, we show that \(J_\mathrm {outer}\) is bounded by a constant, which would conclude the proof. We do this by giving a sequence of upper bounds. We have no hope of providing sharp bounds, so rather than keeping track of all the constants, we will exploit the following definition for streamlining the proof.
, so that
Next, we exploit the symmetry of \(\mathbb {S}(\mathbb {R}^{n_1})\) and transform \(\mathbf {v}^1 \mapsto -\mathbf {v}^1\). This transformation flips the sign of
, but the value of q is not affected. Indeed, the matrix \(\mathrm {I}- M M^\dagger \) still projects onto
, and \(L_2\) is transformed into \(L_2 D\), where D is a diagonal matrix with some pattern of \(\pm 1\) on the diagonal. Since \(\left[ {\begin{matrix}I &{} \\ &{} D\end{matrix}}\right] \) is an orthogonal transformation, the singular values do not change. Thus, we obtain
The next lemma is proved in Appendix C.2.
and
. There is a constant \(K>0\), depending only on \(n_1,\ldots ,n_d\) and d, such that
For bounding the integral over \(\theta \), we need the next lemma, which we prove in Appendix C.3.
Writing
, we arrive at
By orthogonal invariance, we may fix \(\mathbf {u}^k\in \mathbb {S}(\mathbb {R}^{n_k})\) to be \(\mathbf {u}^k = (1,0,\ldots ,0)\), and integrate the constant function 1 over one copy of \(\mathbb {S}{}(\mathbb {R}^{n_1}) \times \cdots \times \mathbb {S}{}(\mathbb {R}^{n_d})\). Ignoring the product of volumes \(\prod _{k=1}^d\mathrm {vol}(\mathbb {S}{}(\mathbb {R}^{n_k}))\) we have
Now, this spherical integral is particularly simple because the integrand depends uniquely on one of the components of each vector. One can thus transform each integral in a sphere into an integral in an interval (see, for example, [10, Lemma 1]) getting:For this last integral, we consider the partition of the cube \([-1,1]^d\) into \(2^d\) pieces corresponding to the different signs of the coordinates. In the pieces where the number of negative coordinates is odd, the denominator of the integrand is bounded below by 1 and thus the whole integrand is also bounded above by 1. Hence, it suffices to check that the integral in the rest of the pieces is bounded. Assume now that \(t_{i_1},\ldots ,t_{i_k}\) with \(k\ge 2\) even are the negative coordinates in some particular piece of the partition. The mapping that leaves all coordinates fixed but maps \(t_{i_{k-1}} \mapsto -t_{i_{k-1}}\) and \(t_{i_{k}} \mapsto -t_{i_{k}}\) preserves the integrand and moves the domain to another piece of the partition with \(k-2\) negative coordinates. This process can then be repeated until none of the coordinates is negative. All in one, we haveThe change of variables \(t_k=\cos (\theta _k)\) for \(1\le k\le d\) converts this last integral intoThe next lemma is proved in Appendix C.4.
, finishing the proof of Theorem 3. \(\square \)
has the density \(\hat{\rho }\) and that there exists positive constants \(c_1,c_2\) such that \(c_1 \le \frac{{\hat{\rho }}}{\rho } \le c_2\), where \(\rho \) is the density of a GIT. Then, for any measurable function
we have
and
Thus,
if and only if
. Replacing f by \(\kappa \) and \(\kappa _{\mathrm {ang}}\) proves the first part of Theorem 4.
by a scalar. Therefore, the expected value of \(\kappa \) for the Gaussian is equal to the expected value when
is chosen uniformly in the unit ball, and also when
is chosen uniformly in the unit sphere of the space of tensors. Namely, we have (see, e.g., [28, Section 2.2.4])
This proves the second and third item of Theorem 4 for \(\kappa \).
is an r-nice tensor, then
for all \(t>0\).
is r-nice, we have
. Similar as for Eq. (29), we can show where
is the CPD of
and
is the corresponding decomposition the tangent vector. The derivative
is the orthogonal projection onto
and independent of scaling. Moreover, \(\sigma _{r;n_1,\ldots ,n_d}\) is a cone and so
can be identified with
. This shows that after scaling the tensor
we get and hence
.
. Since our results for \(\kappa _{\mathrm {ang}}\) are for rank-2 tensors, we put \(r=2\) in the following. We also abbreviate \(\sigma _2:=\sigma _{2;n_1,\ldots ,n_d}\) and \(C_2:=C_{2;n_1,\ldots ,n_d}\). Then, using Lemma 15 we can integrate in polar coordinates to obtain
It follows immediately that the last integral is finite, proving that a randomly chosen
has finite expected \(\kappa _{\mathrm {ang}}\). Finally, if
is chosen randomly in the unit ball in \(\sigma _2\), the same argument shows that the expected value is again finite:
This finishes the proof of Theorem 4.
from the density
until we find one that belongs to \(\sigma _r\). While this scheme will yield tensors distributed according to the density \(\rho \) on \(\sigma _r\), it does not yield Gaussian identifiable tensors in general. The reason is that most perfect tensor spaces are not (expected to be) generically r-identifiable [47]. Fortunately, there are a few known exceptions: matrix pencils (\(\mathbb {R}^{n \times n \times 2}\) for all \(n\ge 2\)), \(\mathbb {R}^{5 \times 4 \times 3}\) and \(\mathbb {R}^{3 \times 2 \times 2 \times 2}\) are proved to be generically complex r-identifiable for \(r = \frac{\varPi }{\varSigma }\). By applying the acceptance–rejection method to these spaces, every sampled tensor is a GIT with probability 1.
in a perfect tensor space lies in \(\sigma _r\) with \(r = \frac{\varPi }{\varSigma }\), we apply a homotopy continuation method to the square system of \(\varPi \) equations
where the \(\varPi = r \varSigma \) entries of the \(\mathbf {a}_{i}^{k}\)’s are treated as variables, and the \(n_1 \times \cdots \times n_d\) tensor
is the tensor to decompose. We generate a start system with one solution to track by randomly sampling the entries of the vectors \(\mathbf {a}_{i}^{k}\) i.i.d. from a real standard Gaussian distribution and then constructing the corresponding tensor
. Since \(r = \frac{\varPi }{\varSigma }\) is the so-called generic rank of tensors in perfect tensor spaces \(\mathbb {C}^{n_1 \times \cdots \times n_d}\), the above system has at least one complex solution with probability 1 as well. If we consider complex r-identifiable perfect tensor spaces at the generic rank, we can thus determine if
by solving the square system and checking whether the unique solution is real. Assuming that we use a certified homotopy method such as alphaCertified [48], this approach will correctly classify
with probability 1, thus not impacting the overall distribution produced by the acceptance–rejection scheme.
of \(\mathbb {R}^{n_1 \times \cdots \times n_d}\) from the density
by choosing its entries i.i.d. standard normally distributed. Then, we generated one random starting system and applied the 
to the target
. If the final solution of the square system was real, we recorded both the regular and angular condition numbers at the CPD of
computed via homotopy continuation. These computations were performed in parallel using 20 computational threads until 100, 000 finite, nonsingular, real solutions and corresponding condition numbers were obtained. This experiment was performed on a computer system consisting of 2 Intel Xeon E5-2697 v3 CPUs with 12 cores clocked at 2.6 GHz and 128GB main memory. Information about the sampling process via the acceptance–rejection method is summarized in Table 1, and Fig. 1 visualizes the complementary cumulative distribution functions of the regular and angular condition numbers.
From the postulated model of c(x), we find that \(p(x) = ab x^{-b-1}\) for large x, so that we postulate that the expected value will be well approximated by
for some finite \(\kappa _0\). The expression on the right is finite only if \(b > 1\). The same discussion applies to the angular condition number as well. Regarding the estimated parameters in Table 2, our empirical data strongly suggest that the expected value of the condition number is infinite for \(r = \frac{\varPi }{\varSigma }\) in the tested cases, as \(b \approx 0.6 < 1\). On the other hand, the expected angular condition number seems finite in all cases, as \(b \approx 1.8 > 1\). This suggests that both Theorems 2 and 3 might hold for higher ranks as well.
