The average condition number of most tensor rank decomposition problems is infinite
arXiv:1903.05527 · doi:10.1007/s10208-022-09551-1
Abstract
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 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.
References in corpus (17)
- Tensor Decomposition for Signal Processing and Machine Learning
- Identifiability of parameters in latent structure models with many observed variables
- Ranks of tensors and a generalization of secant varieties
- An algorithm for generic and low-rank specific identifiability of complex tensors
- Generic uniqueness conditions for the canonical polyadic decomposition and INDSCAL
- Effective criteria for specific identifiability of tensors and forms
- The condition number of join decompositions
- Energy and discrepancy of rotationally invariant determinantal point processes in high dimensional spheres
- A Riemannian Trust Region Method for the Canonical Tensor Rank Approximation Problem
- A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time
- Pencil-based algorithms for tensor rank decomposition are not stable
- Convergence analysis of Riemannian Gauss-Newton methods and its connection with the geometric condition number
- The condition number of Riemannian approximation problems
- Real identifiability vs complex identifiability
- Probabilistic Condition Number Estimates For Real Polynomial Systems I: A Broader Family Of Distributions
- Rank probabilities for real random tensors
- On the average condition number of tensor rank decompositions