Abstract

This chapter studies the problem of decomposing a tensor into a sum ofconstituent rank one tensors. While tensor decompositions are very useful indesigning learning algorithms and data analysis, they are NP-hard in theworst-case. We will see how to design efficient algorithms with provableguarantees under mild assumptions, and using beyond worst-case frameworks likesmoothed analysis.

 

Quick Read (beta)