Efficient Tensor Decomposition
This addresses the computational challenge of tensor decomposition for machine learning and data analysis applications, but it is incremental as it builds on existing frameworks.
The paper tackles the NP-hard problem of tensor decomposition by designing efficient algorithms with provable guarantees under mild assumptions, using frameworks like smoothed analysis.
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.