Complete Decomposition of Symmetric Tensors in Linear Time and Polylogarithmic Precision
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910868248199168 |
|---|---|
| author | Koiran, Pascal Saha, Subhayan |
| author_facet | Koiran, Pascal Saha, Subhayan |
| contents | We study symmetric tensor decompositions, i.e. decompositions of the input symmetric tensor T of order 3 as sum of r 3rd-order tensor powers of u_i where u_i are vectors in \C^n. In order to obtain efficient decomposition algorithms, it is necessary to require additional properties from the u_i. In this paper we assume that the u_i are linearly independent. This implies that r is at most n, i.e., the decomposition of T is undercomplete. We will moreover assume that r=n (we plan to extend this work to the case where r is strictly less than n in a forthcoming paper). We give a randomized algorithm for the following problem: given T, an accuracy parameter epsilon, and an upper bound B on the condition number of the tensor, output vectors u'_i such that u_i and u'_i differ by at most epsilon (in the l_2 norm and up to permutation and multiplication by phases) with high probability. The main novel features of our algorithm are: (1) We provide the first algorithm for this problem that works in the computation model of finite arithmetic and requires only poly-logarithmic (in n, B and 1/epsilon) many bits of precision. (2) Moreover, this is also the first algorithm that runs in linear time in the size of the input tensor. It requires O(n^3) arithmetic operations for all accuracy parameters epsilon = 1/poly(n). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2211_07407 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Complete Decomposition of Symmetric Tensors in Linear Time and Polylogarithmic Precision Koiran, Pascal Saha, Subhayan Data Structures and Algorithms Computational Complexity Numerical Analysis 68W40, 65F22, 68Q87 F.2.1; G.1.3 We study symmetric tensor decompositions, i.e. decompositions of the input symmetric tensor T of order 3 as sum of r 3rd-order tensor powers of u_i where u_i are vectors in \C^n. In order to obtain efficient decomposition algorithms, it is necessary to require additional properties from the u_i. In this paper we assume that the u_i are linearly independent. This implies that r is at most n, i.e., the decomposition of T is undercomplete. We will moreover assume that r=n (we plan to extend this work to the case where r is strictly less than n in a forthcoming paper). We give a randomized algorithm for the following problem: given T, an accuracy parameter epsilon, and an upper bound B on the condition number of the tensor, output vectors u'_i such that u_i and u'_i differ by at most epsilon (in the l_2 norm and up to permutation and multiplication by phases) with high probability. The main novel features of our algorithm are: (1) We provide the first algorithm for this problem that works in the computation model of finite arithmetic and requires only poly-logarithmic (in n, B and 1/epsilon) many bits of precision. (2) Moreover, this is also the first algorithm that runs in linear time in the size of the input tensor. It requires O(n^3) arithmetic operations for all accuracy parameters epsilon = 1/poly(n). |
| title | Complete Decomposition of Symmetric Tensors in Linear Time and Polylogarithmic Precision |
| topic | Data Structures and Algorithms Computational Complexity Numerical Analysis 68W40, 65F22, 68Q87 F.2.1; G.1.3 |
| url | https://arxiv.org/abs/2211.07407 |