Searching. Please wait…
1582
37
170
29108
4409
2600
347
389
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 r?3r?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.
Fuente: Foundations of Computational Mathematics, 2023, 23(2), 433 - 491
Publisher: Springer New York LLC
Publication date: 01/04/2023
No. of pages: 59
Publication type: Article
DOI: 10.1007/s10208-022-09551-1
ISSN: 1615-3375,1615-3383
Spanish project: MTM2017-83816-P
Publication Url: https://doi.org/10.1007/s10208-022-09551-1
Consult in UCrea Read publication
CARLOS BELTRAN ALVAREZ
BREIDING, PAUL
VANNIEUWENHOVEN, NICK
Back