Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method

Boaz Barak, Jonathan A. Kelner, David Steurer

We give a new approach to the dictionary learning (also known as "sparse coding") problem of recovering an unknown $n\times m$ matrix $A$ (for $m\ge n$) from examples of the form…