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 ε˜ 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 Klog⁡Kε˜−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).