Compressed Dictionary Learning
| Autor: | Schnass, Karin, Teixeira, Flavio |
|---|---|
| Rok vydání: | 2018 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | In this paper we show that the computational complexity of the Iterative Thresholding and K-residual-Means (ITKrM) algorithm for dictionary learning can be significantly reduced by using dimensionality-reduction techniques based on the Johnson-Lindenstrauss lemma. The dimensionality reduction is efficiently carried out with the fast Fourier transform. We introduce the Iterative compressed-Thresholding and K-Means (IcTKM) algorithm for fast dictionary learning and study its convergence properties. We show that IcTKM can locally recover an incoherent, overcomplete generating dictionary of $K$ atoms from training signals of sparsity level $S$ with high probability. Fast dictionary learning is achieved by embedding the training data and the dictionary into $m < d$ dimensions, and recovery is shown to be locally stable with an embedding dimension which scales as low as $m = O(S \log^4 S \log^3 K)$. The compression effectively shatters the data dimension bottleneck in the computational cost of ITKrM, reducing it by a factor $O(m/d)$. Our theoretical results are complemented with numerical simulations which demonstrate that IcTKM is a powerful, low-cost algorithm for learning dictionaries from high-dimensional data sets. Comment: 5 figure, 4.6 pages per figure |
| Databáze: | arXiv |
| Externí odkaz: |
|