  Let $A$ be an $n \times n$ matrix, $X$ be an $n \times p$ matrix and $Y =
AX$. A challenging and important problem in data analysis, motivated by
dictionary learning and other practical problems, is to recover both $A$ and
$X$, given $Y$. Under normal circumstances, it is clear that this problem is
underdetermined. However, in the case when $X$ is sparse and random, Spielman,
Wang and Wright showed that one can recover both $A$ and $X$ efficiently from
$Y$ with high probability, given that $p$ (the number of samples) is
sufficiently large. Their method works for $p \ge C n^2 \log^ 2 n$ and they
conjectured that $p \ge C n \log n$ suffices. The bound $n \log n$ is sharp for
an obvious information theoretical reason.
  In this paper, we show that $p \ge C n \log^4 n$ suffices, matching the
conjectural bound up to a polylogarithmic factor. The core of our proof is a
theorem concerning $l_1$ concentration of random matrices, which is of
independent interest.
  Our proof of the concentration result is based on two ideas. The first is an
economical way to apply the union bound. The second is a refined version of
Bernstein's concentration inequality for the sum of independent variables. Both
have nothing to do with random matrices and are applicable in general settings.
