Convergence radius and sample complexity of ITKM algorithms for dictionary learning
This provides theoretical guarantees for dictionary learning in signal processing, but is incremental as it builds on existing ITKM methods.
The paper establishes that ITKM algorithms can recover a generating dictionary from noisy sparse signals within a convergence radius, requiring sample size proportional to K log K ε̃^{-2} and sparsity scaling with signal dimension.
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^{-\ell}$ if $S$ scales as $S \leq d/(\ell \log K)$.