Exact Recovery of Sparsely-Used Dictionaries

Daniel A. Spielman, Huan Wang, John Wright

We consider the problem of learning sparsely used dictionaries with an arbitrary square dictionary and a random, sparse coefficient matrix. We prove that $O(n\log n)$ samples are…