## Local Identifiability of $\ell_1$-minimization Dictionary Learning: a Sufficient and Almost Necessary Condition

*Siqi Wu, Bin Yu*; 18(168):1−56, 2018.

### Abstract

We study the theoretical properties of learning a dictionary
from $N$ signals $\mathbf{x}_i\in \mathbb R^K$ for $i=1,\ldots,N$ via
$\ell_1$-minimization. We assume that $\mathbf{x}_i$'s are $i.i.d.$
random linear combinations of the $K$ columns from a complete
(i.e., square and invertible) reference dictionary $\mathbf{D}_0 \in
\mathbb R^{K\times K}$. Here, the random linear coefficients are
generated from either the $s$-sparse Gaussian model or the
Bernoulli-Gaussian model. First, for the population case, we
establish a sufficient and almost necessary condition for the
reference dictionary $\mathbf{D}_0$ to be locally identifiable, i.e., a
strict local minimum of the expected $\ell_1$-norm objective
function. Our condition covers both sparse and dense cases of
the random linear coefficients and significantly improves the
sufficient condition by Gribonval and Schnass (2010). In
addition, we show that for a complete $\mu$-coherent reference
dictionary, i.e., a dictionary with absolute pairwise column
inner-product at most $\mu\in[0,1)$, local identifiability
holds even when the random linear coefficient vector has up to
$O(\mu^{-2})$ nonzero entries. Moreover, our local
identifiability results also translate to the finite sample case
with high probability provided that the number of signals $N$
scales as $O(K\log K)$.

[abs][pdf][bib]