Convergence radius and sample complexity of ITKM algorithms for dictionary learning

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{\epsilon }$ 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{\epsilon }}^{-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^{-\mathrm{\ell }}$ if $S$ scales as $S\le d\mathrm{/}(\mathrm{\ell }\log K)$.