Fast Overcomplete Dictionary Construction with Probabilistic Guarantees

摘要

In dictionary learning, a matrix comprised of signalsYis factorized into the product of two matrices: a matrix of prototypical atomsD, and a sparse matrix containing coefficients for atoms inD, calledX. This process has applications in signal processing, image recognition, and a number of other fields. Many procedures for solving the dictionary learning problem follow the alternating minimization paradigm; that is, by alternating between solving forDandX, until the procedure converges to a solution. Our findings indicate that the costly step of alternating minimization can be avoided in some cases, by modifying an initialization procedure that was proposed in 2014. We provide theoretical justification and empirical evidence showing that atom recovery and reasonable data reconstruction is possible under these new assumptions.