Linear expansion with dictionaries of basis functions, with respect to which you wish your representation to be sparse; i.e. in the statistical case, basis-sparse regression. But even outside statistics, you wish simply to approximate some data compactly. My focus here is on the noisy-observation case, although the same results are recycled enough throughout the field.

There are several senses in which people seem to use sparse coding; these do not necessarily mean the same thing, but they frequently connect.

I know that my signal happens to be compressible, in the sense that under some transform its coefficient vector is mostly zeros, even in a plain old orthogonal basis expansion. Or, relatedly, I know that under such a transform, the fidelity of my reproduction of the signal decays rapidly with the number of bits, in some metric.

I am using a redundant dictionary such that I wonβt need most of it to represent even a dense signal. This means that the representations of the signals might have lots of zeros, but nonetheless may not be compressible in an information-theoretic sense.

I should break these two notions apart here. For now, Iβm especially interested in adaptive bases.

This is merely a bunch of links to important articles at the moment; I might write a little exposition one day.

Decomposition of stuff by matching pursuit, wavelets, curvelets, chirplets, framelets, shearlets, camelhairbrushlets, content-specific basis dictionaries, designed or learned. Mammals visual cortexes seem to use something like this, if you squint right at the evidence.

To discuss:

connection to mixture models.

Sampling complexity versus approximation complexity

I am especially interested in approaches where we learn the transform or the basis dictionary unsupervised

## Resources

Baraniukβs lab has a comprehensive, but not usefully annotated, selection of articles in this field, which I include less as a useful starting point, than to demonstrate the virtue of a literature review by showing the pathology of its absence.

## Scattering transform coefficients

See scattering transform.

## Matching Pursuits

I do a lot of this now. I should document it. π

## Learnable codings

Adaptive dictionaries!

I want to generalise or extend this idea, ideally in some shift-invariant way (see below.)

(Bruno A. Olshausen and Field 1996) 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 (Ngiam et al. 2011; HyvΓ€rinen, Hurri, and Hoyer 2009; Hahn et al. 2015).

See (Mairal, Bach, and Ponce 2014) for some a summary of methods to 2009 in basis learning.

Question: how do you do this in a big data / offline setting?

TRANSFORM LEARNING: Sparse Representations at Scale.

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.

### 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β, (Blumensath and Davies 2004) 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. (Lattner, Dorο¬er, and Arzt 2019) presents an adaptive sparse coding method preserving desired invariants.

## Bayesian

Unsure. See perhaps Schniter, Potter, and Ziniel (2008), ZhouNonparametric2009.

## Incoming

Affine *tight framelets* (Ingrid Daubechies et al. 2003) and their
presumably less-computationally-tractable, more flexible cousins,
*shearlets* also sound interesting.
For reasons I do not yet understand
I am told they can naturally be used on sundry graphs and manifolds, not just
lattices, is traditional in DSP.
I saw Xiaosheng Zhuang
present these
(see, e.g. (Y. G. Wang and Zhuang 2016; B. Han, Zhao, and Zhuang 2016), where the latter demonstrates a
*Fast Framelet Transform*
which is supposedly as computationally as cheap as the FFT.)

I have some ideas I call learning gamelan which relate to this.

## Implementations

Implementations boil down to clever optimisation and/or good use of functional transforms to make the calculations tractable.

Shailesh Kumar, Wavelet Transforms in Python with Google JAX introduces CR.Sparse β cr-sparse documentation, a JAX/XLA based library of accelerated models and algorithms for inverse problems in sparse representation and compressive sensing.

the standard wavelet toolkits.

- scipyβs wavelet transform has no frills and little coherent explanation, but it goes
- pywavelets does various fancy wavelets and seems to be a standard for python.
- Matlabβs Wavelet toolbox seems to be the reference.
- scikit-learn dictionary learning version here
- also pydbm
- Fancy easy GPU wavelet implementation, PyTorchWavelets.

SParse Optimization Research COde (SPORCO) is an open-source Python package for solving optimization problems with sparsity-inducing regularization, consisting primarily of sparse coding and dictionary learning, for both standard and convolutional forms of sparse representation. In the current version, all optimization problems are solved within the Alternating Direction Method of Multipliers (ADMM) framework. SPORCO was developed for applications in signal and image processing, but is also expected to be useful for problems in computer vision, statistics, and machine learning.

Sparse-filtering: Unsupervised feature learning based on sparse-filtering

This implements the method described Jiquan Ngiam, Pang Wei Koh, Zhenghao Chen, Sonia Bhaskar, Andrew Y. Ng: Sparse Filtering. NIPS 2011: 1125-1133 and is based on the Matlab code provided in the supplementary material

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,...).

## References

*IEEE Transactions on Signal Processing*54 (11): 4311β22.

*Proceedings of The 28th Conference on Learning Theory*, 40:113β49. Paris, France: PMLR.

*Journal of Machine Learning Research*7 (Oct): 1963β2001.

*IEEE Transactions on Information Theory*56 (4): 1982β2001.

*The Annals of Statistics*36 (1): 64β94.

*IEEE Transactions on Signal Processing*60 (4): 1597β1611.

*Annales de lβInstitut Henri PoincarΓ©, ProbabilitΓ©s Et Statistiques*47 (1): 43β74.

*Communications on Pure and Applied Mathematics*44 (2): 141β83.

*Independent Component Analysis and Blind Signal Separation*, edited by Carlos G. Puntonet and Alberto Prieto, 3195:1205β12. Berlin, Heidelberg: Springer Berlin Heidelberg.

*IEEE Transactions on Audio, Speech and Language Processing*14 (1): 50β57.

*International Conference on Machine Learning*, 537β46.

*IEEE Transactions on Pattern Analysis and Machine Intelligence*35 (8): 1872β86.

*arXiv:1801.02013 [Math-Ph, Stat]*, May.

*The Annals of Statistics*43 (1): 323β51.

*Applied and Computational Harmonic Analysis*, Special Issue on Mathematical Imaging β Part II, 24 (2): 131β49.

*IEEE Journal of Selected Topics in Signal Processing*5 (6): 1144β58.

*Finite Frame Theory: A Complete Introduction to Overcompleteness*.

*1994 Conference Record of the Twenty-Eighth Asilomar Conference on Signals, Systems and Computers, 1994*, 1:41β44 vol.1.

*arXiv:2112.01288 [Astro-Ph, Physics:physics]*, November.

*Journal of Neuroscience*41 (5): 1019β32.

*Communications on Pure and Applied Mathematics*57 (11): 1413β57.

*Communications on Pure and Applied Mathematics*41 (7): 909β96.

*Applied and Computational Harmonic Analysis*14 (1): 1β46.

*IEEE Transactions on Image Processing*7 (2): 141β54.

*Optical Engineering*33 (7): 2183β91.

*Wavelet Applications*, 2242:402β14. International Society for Optics and Photonics.

*Constructive Approximation*13 (1): 57β98.

*Acta Numerica*7 (January): 51β150.

*Applied and Computational Harmonic Analysis*.

*Journal of the American Statistical Association*90 (432): 1200β1224.

*Journal of the Royal Statistical Society. Series B (Methodological)*57 (2): 301β69.

*Bioinformatics*22 (17): 2059β65.

*2004 IEEE International Joint Conference on Neural Networks (IEEE Cat. No.04CH37541)*, 4:2529β2533 vol.4.

*IEEE Transactions on Signal Processing*59 (10): 4735β44.

*Journal of the American Statistical Association*96 (456): 1348β60.

*An Introduction to Wavelets Through Linear Algebra*. Springer.

*arXiv:1701.06106 [Cs, Stat]*.

*Vector Quantization and Signal Compression*. Springer Science & Business Media.

*The Annals of Probability*37 (4): 1605β46.

*IEEE Transactions on Signal Processing*64 (13): 3444β57.

*IEEE Workshop on Applications of Signal Processing to Audio and Acoustics*.

*IEEE Transactions on Signal Processing*47 (7): 1890β1902.

*1997 IEEE ASSP Workshop on Applications of Signal Processing to Audio and Acoustics, 1997*.

*IEEE ASSP Magazine*1 (2): 4β29.

*Proceedings of the 27th International Conference on Machine Learning (ICML-10)*, 399β406.

*arXiv:1105.5307 [Cs]*, May.

*The Twenty-Third Conference on Uncertainty in Artificial Intelligence (UAI2007)*, 9:8.

*arXiv:1605.07913 [Math, Stat]*, May.

*Multimedia Tools and Applications*74 (22): 10097β110.

*Applied and Computational Harmonic Analysis*, Sparse Representations with Applications in Imaging Science, Data Analysis, and Beyond, Part IISI: ICCHAS Outgrowth, part 2, 41 (2): 603β37.

*Applied and Computational Harmonic Analysis*39 (2): 300β338.

*Proceedings of the 1st ACM Workshop on Audio and Music Computing Multimedia*, 21β26. AMCMM β06. New York, NY, USA: ACM.

*ISMIR*.

*Journal of Machine Learning Research*5 (9): 1457β69.

*Proceedings of the 2002 12th IEEE Workshop on Neural Networks for Signal Processing, 2002*, 557β65.

*Neural Computation*12 (7): 1705β20.

*Natural Image Statistics: A Probabilistic Approach to Early Computational Vision.*Vol. 39. Springer Science & Business Media.

*IEEE Journal of Selected Topics in Signal Processing*5 (5): 1025β31.

*2010 IEEE International Conference on Acoustics, Speech and Signal Processing*, 5482β85.

*Advances in Neural Information Processing Systems 29*.

*SIAM Journal on Matrix Analysis and Applications*30 (2): 713β30.

*arXiv:1612.04468 [Cs, Stat]*, December.

*arXiv:1612.04111 [Cs, Stat]*, December.

*Proceedings of the 20th Conference of the International Society for Music Information Retrieval*, 8.

*Advances in Neural Information Processing Systems*19: 801.

*IEEE Transactions on Information Theory*42 (6): 2118β32.

*NIPS*, 11:730β36. Denver, CO: MIT Press.

*Neural Computation*12 (2): 337β65.

*arXiv:1601.00238 [Cs, Stat]*, January.

*IEEE Transactions on Neural Networks and Learning Systems*PP (99): 1β1.

*Journal of Machine Learning Research*21 (251): 1β49.

*Signal Processing*, Advances in Multirate Filter Bank Structures and Multiscale Representations, 91 (12): 2822β35.

*Sparse Modeling for Image and Vision Processing*. Vol. 8.

*Proceedings of the 26th Annual International Conference on Machine Learning*, 689β96. ICML β09. New York, NY, USA: ACM.

*The Journal of Machine Learning Research*11: 19β60.

*Transactions of the American Mathematical Society*315 (1): 69β87.

*A Wavelet Tour of Signal Processing: The Sparse Way*. Academic Press.

*Communications on Pure and Applied Mathematics*65 (10): 1331β98.

*IEEE Transactions on Signal Processing*41 (12): 3397β3415.

*Time-Frequency and Time-Scale Analysis, 1992., Proceedings of the IEEE-SP International Symposium*, 7β10.

*Science*346 (6209): 551β52.

*arXiv Preprint arXiv:1312.4695*.

*Annals of the Institute of Statistical Mathematics*64 (1): 27β53.

*Journal of Machine Learning Research*.

*Advances in Neural Information Processing Systems 24*, edited by J. Shawe-Taylor, R. S. Zemel, P. L. Bartlett, F. Pereira, and K. Q. Weinberger, 1125β33. Curran Associates, Inc.

*Network (Bristol, England)*7 (2): 333β39.

*Nature*381 (6583): 607β9.

*Current Opinion in Neurobiology*14 (4): 481β87.

*Statistical Science*16 (2): -134-153.

*arXiv Preprint arXiv:1703.08961*.

*Signal Processing*, Sparse Approximations in Signal and Image ProcessingSparse Approximations in Signal and Image Processing, 86 (3): 417β31.

*Signal Processing*36 (1): 1β11.

*arXiv:1501.02923 [Cs, Stat]*, January.

*Proceedings of the IEEE*98 (6): 1045β57.

*Iterative Methods for Sparse Linear Systems: Second Edition*. 2nd ed. SIAM.

*2008 Information Theory and Applications Workshop*, 326β33. San Diego, CA, USA: IEEE.

*Scopus*, 2834β63. World Scientific.

*Annual Review of Neuroscience*24 (1): 1193β1216.

*Nature*439 (7079): 978β82.

*arXiv:1701.01207 [Cs, Math, Stat]*, January.

*arXiv:1412.7022 [Cs]*, December.

*IEEE Transactions on Pattern Analysis and Machine Intelligence*42 (8): 1968β80.

*Wavelet Theory and Its Application to Pattern Recognition*. World Scientific.

*Bulletin of the American Meteorological Society*79 (1): 61β78.

*IEEE Signal Processing Magazine*28 (2): 27β38.

*Proceedings of the IEEE*98 (6): 948β58.

*Signal Processing*, Sparse Approximations in Signal and Image ProcessingSparse Approximations in Signal and Image Processing, 86 (3): 589β602.

*Signal Processing*, Sparse Approximations in Signal and Image ProcessingSparse Approximations in Signal and Image Processing, 86 (3): 533β48.

*Signal Processing*, Sparse Approximations in Signal and Image ProcessingSparse Approximations in Signal and Image Processing, 86 (3): 549β71.

*arXiv:1507.03194 [Cs, Stat]*, July.

*Journal of Machine Learning Research*12 (Nov): 3259β81.

*AeroSenseβ99*, 3723:28β31. International Society for Optics and Photonics.

*arXiv:1701.01595 [Cs, Math]*, January.

*arXiv:1608.04026 [Math]*, August.

*Proceedings of the 31st International Conference on International Conference on Machine Learning - Volume 32*, 730β38. ICMLβ14. Beijing, China: JMLR.org.

*IEEE Transactions on Information Theory*58 (8): 4969β92.

*High-dimensional data analysis with low-dimensional models: Principles, computation, and applications*. S.l.: Cambridge University Press.

*IEEE Transactions on Signal Processing*57 (12): 4800β4810.

*IEEE Transactions on Signal Processing*61 (9): 2341β55.

*Proceedings of the 31st International Conference on International Conference on Machine Learning - Volume 32*, 127β35. Beijing, China: JMLR.org.

*Proceedings of the 22nd International Conference on Neural Information Processing Systems*, 22:2295β2303. NIPSβ09. Red Hook, NY, USA: Curran Associates Inc.

*SIAM Journal on Imaging Sciences*9 (3): 1437β66.

## No comments yet. Why not leave one?