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 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-ℓ if S scales as S ≤ d/(ℓ log K).