Name
Abstract | ||
|---|---|---|
We give new algorithms based on the sum-of-squares method for tensor decomposition. Our results improve the best known running times from quasi-polynomial to polynomial for several problems, including decomposing random overcomplete 3-tensors and learning overcomplete dictionaries with constant relative sparsity. We also give the first robust analysis for decomposing overcomplete 4-tensors in the smoothed analysis model. A key ingredient of our analysis is to establish small spectral gaps in moment matrices derived from solutions to sum-of-squares relaxations. To enable this analysis we augment sum-of-squaresrelaxations with spectral analogs of maximum entropy constraints. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1109/FOCS.2016.54 | 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) |
Keywords | DocType | Volume |
tensor decomposition,smoothed analysis,FOOBI algorithm,sum-of-squares method,Lasserre hierarchy,simultaneous diagonalization | Conference | abs/1610.01980 |
ISSN | ISBN | Citations |
0272-5428 | 978-1-5090-3934-0 | 19 |
PageRank | References | Authors |
0.70 | 23 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tengyu Ma | 1 | 596 | 41.23 |
| Jonathan Shi | 2 | 62 | 3.29 |
| David Steurer | 3 | 934 | 44.91 |