Convergence radius and sample complexity of ITKM algorithms for dictionary learning

Code

• github.com/cristian-rusu-research/ADL-TOOLBOX
  none★ 0

Abstract

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 K factor inversely proportional to the dynamic range of the signals, and the sample size is proportional to K 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/( K).

Tasks

Reproductions