Identifiability of Complete Dictionary Learning
  Sparse component analysis (SCA), also known as complete dictionary learning,
is the following problem: Given an input matrix $M$ and an integer $r$, find a
dictionary $D$ with $r$ columns and a matrix $B$ with $k$-sparse columns (that
is, each column of $B$ has at most $k$ non-zero entries) such that $M \approx
DB$. A key issue in SCA is identifiability, that is, characterizing the
conditions under which $D$ and $B$ are essentially unique (that is, they are
unique up to permutation and scaling of the columns of $D$ and rows of $B$).
Although SCA has been vastly investigated in the last two decades, only a few
works have tackled this issue in the deterministic scenario, and no work
provides reasonable bounds in the minimum number of samples (that is, columns
of $M$) that leads to identifiability. In this work, we provide new results in
the deterministic scenario when the data has a low-rank structure, that is,
when $D$ is (under)complete. While previous bounds feature a combinatorial term
$r \choose k$, we exhibit a sufficient condition involving
$\mathcal{O}(r^3/(r-k)^2)$ samples that yields an essentially unique
decomposition, as long as these data points are well spread among the subspaces
spanned by $r-1$ columns of $D$. We also exhibit a necessary lower bound on the
number of samples that contradicts previous results in the literature when $k$
equals $r-1$. Our bounds provide a drastic improvement compared to the state of
the art, and imply for example that for a fixed proportion of zeros (constant
and independent of $r$, e.g., 10\% of zero entries in $B$), one only requires
$\mathcal{O}(r)$ data points to guarantee identifiability.
