## Local Identification of Overcomplete Dictionaries

*Karin Schnass*; 16(Jun):1211−1242, 2015.

### Abstract

This paper presents the first theoretical results showing that
stable identification of overcomplete $\mu$-coherent
dictionaries $\Phi \in \R^{d\times K}$ is locally possible from
training signals with sparsity levels $S$ up to the order
$O(\mu^{-2})$ and signal to noise ratios up to $O(\sqrt{d})$. In
particular the dictionary is recoverable as the local maximum of
a new maximization criterion that generalizes the K-means
criterion. For this maximization criterion results for
asymptotic exact recovery for sparsity levels up to
$O(\mu^{-1})$ and stable recovery for sparsity levels up to
$O(\mu^{-2})$ as well as signal to noise ratios up to
$O(\sqrt{d})$ are provided. These asymptotic results translate
to finite sample size recovery results with high probability as
long as the sample size $N$ scales as $O(K^3dS \tilde
\epsilon^{-2})$, where the recovery precision $\tilde{\epsilon}$
can go down to the asymptotically achievable precision. Further,
to actually find the local maxima of the new criterion, a very
simple Iterative Thresholding and K (signed) Means algorithm
(ITKM), which has complexity $O(dKN)$ in each iteration, is
presented and its local efficiency is demonstrated in several
experiments.

[abs][pdf][bib]