Local Identification of Overcomplete Dictionaries

Karin Schnass

This paper presents the first theoretical results showing that stable identification of overcomplete

$\mu$ -coherent dictionaries

$\Phi \in \mathbb{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.

Local Identification of Overcomplete Dictionaries

Abstract