Approximate Guarantees for Dictionary Learning
  In the dictionary learning (or sparse coding) problem, we are given a
collection of signals (vectors in $\mathbb{R}^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 \times 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 \approx 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.
