# Sparse coding with learnable dictionaries

November 18, 2014 — March 2, 2023

convolution
high d
Hilbert space
linear algebra
nonparametric
optimization
regression
signal processing
sparser than thou

Adaptive dictionaries for sparse coding. How is this different from matrix factorisation, you ask? It is not. AFAICT these are emphases of the same thing.

kicked this area off by arguing sparse coding tricks are revealing of what the brain does.

For a walk through of one version of this, see Theano example of dictionary learning by Daniel LaCombe, who bases his version on .

See for some a summary of methods to 2009 in basis learning.

Question: how do you do adaptive sparse coding in a big data / offline setting?

We have proposed several methods for batch learning of square or overcomplete sparsifying transforms from data. We have also investigated specific structures for these transforms such as double sparsity, union-of-transforms, and filter bank structures, which enable their efficient learning or usage. Apart from batch transform learning, our group has investigated methods for online learning of sparsifying transforms, which are particularly useful for big data or real-time applications.

Huh.

### 0.1 Codings with desired invariances

I would like to find bases robust against certain transformations, especially phase/shift-robust codings, although doing this naively can be computationally expensive outside of certain convenient bases. (Sorry, that’s not very clear; I need to return to this section to polish it up. 🏗)

One method is “Shift Invariant Sparse coding”, and there are various extensions and approximations out there. (Grosse et al. (2007) etc) One way is to include multiple shifted copies of your atoms, another is to actually shift them in a separate optimisation stage. Both these get annoying in the time domain for various reasons. presents an adaptive sparse coding method preserving desired invariants.

spams does a huge variety of off-the-shelf sparse codings, although none of them are flexible. Nonetheless it does some neat things fast.

SPAMS (SPArse Modeling Software) is an optimization toolbox for solving various sparse estimation problems.

• Dictionary learning and matrix factorization (NMF, sparse PCA,…)
• Solving sparse decomposition problems with LARS, coordinate descent, OMP, SOMP, proximal methods
• Solving structured sparse decomposition problems (l1/l2, l1/linf, sparse group lasso, tree-structured regularization, structured sparsity with overlapping groups,…).

## 1 References

Blumensath, and Davies. 2004. In Independent Component Analysis and Blind Signal Separation.
Charles, Balavoine, and Rozell. 2016. IEEE Transactions on Signal Processing.
Garg, Rish, Cecchi, et al. 2017. In arXiv:1701.06106 [Cs, Stat].
Gehler, and Nowozin. n.d. “Let the Kernel Figure It Out; Principled Learning of Pre-Processing for Kernel Classiﬁers.”
Gregor, and LeCun. 2010. In Proceedings of the 27th International Conference on Machine Learning (ICML-10).
———. 2011. arXiv:1105.5307 [Cs].
Grosse, Raina, Kwong, et al. 2007. In The Twenty-Third Conference on Uncertainty in Artificial Intelligence (UAI2007).
Hahn, Lewkowitz, Lacombe, et al. 2015. Multimedia Tools and Applications.
Henaff, Jarrett, Kavukcuoglu, et al. 2011. In ISMIR.
Hyvärinen, and Hoyer. 2000. Neural Computation.
Hyvärinen, Hurri, and Hoyer. 2009. Natural Image Statistics: A Probabilistic Approach to Early Computational Vision.
Knudson, Yates, Huk, et al. 2014. In Advances in Neural Information Processing Systems 27.
Kreutz-Delgado, Murray, Rao, et al. 2003. Neural Computation.
Lattner, Dorﬂer, and Arzt. 2019. In Proceedings of the 20th Conference of the International Society for Music Information Retrieval.
Lewicki, M S, and Sejnowski. 1999. In NIPS.
Lewicki, Michael S., and Sejnowski. 2000. Neural Computation.
Mairal, Bach, Ponce, et al. 2009. In Proceedings of the 26th Annual International Conference on Machine Learning. ICML ’09.
———, et al. 2010. The Journal of Machine Learning Research.
Mairal, Bach, and Ponce. 2014. Sparse Modeling for Image and Vision Processing.
Meinshausen, and Yu. 2009. The Annals of Statistics.
Ngiam, Chen, Bhaskar, et al. 2011. In Advances in Neural Information Processing Systems 24.
Olshausen, B. A., and Field. 1996. Network (Bristol, England).
Olshausen, Bruno A., and Field. 1996. Nature.
Olshausen, Bruno A, and Field. 2004. Current Opinion in Neurobiology.
Qian, Hong, Cai, et al. 2016. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. IJCAI’16.
Rubinstein, Bruckstein, and Elad. 2010. Proceedings of the IEEE.
Scetbon, Cuturi, and Peyré. 2021. In Proceedings of the 38th International Conference on Machine Learning.
Schmitz, Heitz, Bonneel, et al. 2018. SIAM Journal on Imaging Sciences.
Shen, and Li. 2010. IEEE Transactions on Pattern Analysis and Machine Intelligence.
Simoncelli, and Olshausen. 2001. Annual Review of Neuroscience.
Soh, and Chandrasekaran. 2017. arXiv:1701.01207 [Cs, Math, Stat].
Yaghoobi, Nam, Gribonval, et al. 2013. IEEE Transactions on Signal Processing.