  In this work we show that iterative thresholding and K-means (ITKM)
algorithms can recover a generating dictionary with K atoms from noisy $S$
sparse signals up to an error $\tilde \varepsilon$ as long as the
initialisation is within a convergence radius, that is up to a $\log K$ factor
inversely proportional to the dynamic range of the signals, and the sample size
is proportional to $K \log K \tilde \varepsilon^{-2}$. The results are valid
for arbitrary target errors if the sparsity level is of the order of the square
root of the signal dimension $d$ and for target errors down to $K^{-\ell}$ if
$S$ scales as $S \leq d/(\ell \log K)$.
