Exact Recovery of Sparsely-Used Dictionaries
This addresses dictionary learning for sparse representations, a key task in signal processing and machine learning, with theoretical guarantees and improved performance over state-of-the-art methods.
The paper tackles the problem of learning sparsely used dictionaries with arbitrary square dictionaries and random sparse coefficient matrices, proving that O(n log n) samples are sufficient for unique recovery and designing a polynomial-time algorithm (ER-SpUD) that recovers the dictionary and coefficients with high probability when sparsity is sufficient.
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.