  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 sufficient to uniquely determine the
coefficient matrix. Based on this proof, we design a polynomial-time algorithm,
called Exact Recovery of Sparsely-Used Dictionaries (ER-SpUD), and prove that
it probably recovers the dictionary and coefficient matrix when the coefficient
matrix is sufficiently sparse. Simulation results show that ER-SpUD reveals the
true dictionary as well as the coefficients with probability higher than many
state-of-the-art algorithms.
