Get our free extension to see links to code for papers anywhere online!Free add-on: code for papers everywhere!Free add-on: See code for papers anywhere!
Add to Chrome
Add to Firefox
Add to EdgeEfficient Tensor Decomposition
Jul 30, 2020
This chapter studies the problem of decomposing a tensor into a sum of constituent rank one tensors. While tensor decompositions are very useful in designing learning algorithms and data analysis, they are NP-hard in the worst-case. We will see how to design efficient algorithms with provable guarantees under mild assumptions, and using beyond worst-case frameworks like smoothed analysis.
* Chapter 19 of the book "Beyond the Worst-Case Analysis of
Algorithms", edited by Tim Roughgarden and published by Cambridge University
Press (2020). We hope to occasionally update the survey here to include
discussions of new results and advances
View paper on