Efficient Tensor Decomposition

07/30/2020

∙

by   Aravindan Vijayaraghavan, et al.

∙

0

∙

share

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.