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 (epsilon) over tilde 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 (epsilon) over tilde (-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-l if S scales as S <= d/(l log K). (C) 2016 Elsevier Inc. All rights reserved.