Approximate Guarantees for Dictionary Learning

In the dictionary learning (or sparse coding) problem, we are given a collection of signals (vectors in ℝd), and the goal is to find a "basis" in which the signals have a sparse (approximate) representation. The problem has received a lot of attention in signal processing, learning, and theoretical computer science. The problem is formalized as factorizing a matrix X (d × n) (whose columns are the signals) as X = AY, where A has a prescribed number m of columns (typically m ll n), and Y has columns that are k-sparse (typically k ll d). Most of the known theoretical results involve assuming that the columns of the unknown A have certain incoherence properties, and that the coefficient matrix Y has random (or partly random) structure. The goal of our work is to understand what can be said in the absence of such assumptions. Can we still find A and Y such that X ≈ AY? We show that this is possible, if we allow violating the bounds on m and k by appropriate factors that depend on k and the desired approximation. Our results rely on an algorithm for what we call the threshold correlation problem, which turns out to be related to hypercontractive norms of matrices. We also show that our algorithmic ideas apply to a setting in which some of the columns of X are outliers, thus giving similar guarantees even in this challenging setting.