| In this thesis we analyze the theoretical foundations and the algorithmic applications of the dictionary learning problem. We first consider the problem of learning sparsely used dictionaries with an arbitrary square dictionary and a random, sparse coefficient matrix. We prove that O(nlogn) 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 coefficient matrix with higher probability than many state-of-the-art algorithms. We also propose a batchwise monotone algorithm for dictionary learning. By treating the samples as a batch and imposing a sparsity constraint on the whole, the batchwise dictionary learning algorithm is able to produce a better approximation with the same sparsity level compared to previous algorithms. |
