Name
Abstract | ||
|---|---|---|
We develop the first fast spectral algorithm to decompose a random third-order tensor over of rank up to $$O(d^{3/2}/polylog(d))$$. Our algorithm only involves simple linear algebra operations and can recover all components in time $$O(d^{6.05})$$ under the current matrix multiplication time. Prior to this work, comparable guarantees could only be achieved via sum-of-squares [Ma, Shi, Steurer 2016]. In contrast, fast algorithms [Hopkins, Schramm, Shi, Steurer 2016] could only decompose tensors of rank at most $$O(d^{4/3}/polylog(d))$$. Our algorithmic result rests on two key ingredients. A clean lifting of the third-order tensor to a sixth-order tensor, which can be expressed in the language of tensor networks. A careful decomposition of the tensor network into a sequence of rectangular matrix multiplications, which allows us to have a fast implementation of the algorithm. |
Year | Venue | DocType |
|---|---|---|
2022 | Annual Conference on Computational Learning Theory | Conference |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jingqiu Ding | 1 | 0 | 0.34 |
| Tommaso d'Orsi | 2 | 0 | 1.35 |
| Chih-Hung Liu | 3 | 0 | 0.68 |
| David Steurer | 4 | 934 | 44.91 |
| Stefan Tiegel | 5 | 0 | 0.68 |