Great news!! A fast, butterfly (aka FFT-like), implementation of the Noiselet Transform [1] is now integrated into the LazyLinop toolbox [2] – “a python toolbox to ease and accelerate computations with (“matrix-free”) linear operators.” Thank you to Pascal Carrivain and Rémi Gribonval from the OCKHAM/INRIA team [3], in ENS Lyon, France (where I’m currently invited for a sabbatical year in 25-26) for this implementation. The idea came from common discussions we had together (I share my office with Pascal at ENS Lyon) about possible additional butterfly transformations to complete the (already long) list of operators integrated to LazyLinop. The whole Noiselet Tansform (and its inverse) is described here in the LazyLinop documentation, with a demonstration code in python. Enjoy!

---

[1] https://laurentjacques.gitlab.io/post/some-comments-on-noiselets/

[2] https://faustgrp.gitlabpages.inria.fr/lazylinop/index.html "Lazylinop is a python toolbox to ease and accelerate computations with (“matrix-free”) linear operators. It provides glue to combine linear operators as easily as NumPy arrays, PyTorch/CuPy compatibility, standard signal/image processing linear operators, as well as advanced tools to approximate large matrices by efficient butterfly operators."

[3] https://team.inria.fr/ockham/

#Noiselet #CompressiveSensing #Butterfly #fft #InverseProblem #Python #Numeric #PyTorch

[New Python code: PyNoiselet] About 15 years ago, I wrote a simple set of matlab functions to compute the #Noiselet transform of Coifman et al (R. Coifman, F. Geshwind, and Y. Meyer, "Noiselets", *Applied and Computational Harmonic Analysis*, 10(1):27–44, 2001). The noiselet transform is used in #CompressiveSensing applications as well as in #Sparse signal coding as noiselets have minimally low coherence with wavelet bases (Haar and Daubechies), which is useful for sparse signal recovery.

Today, from a code request received yesterday by email, I decided to quickly rewrite this old code in Python (with the useful help of one LLM I admit).

Here is the result if you need an O(N log N) (butterfly like) algorithm to compute this transformation:

https://gitlab.com/laurentjacques/PyNoiselet

More information also in this old blog post : https://laurentjacques.gitlab.io/post/some-comments-on-noiselets/

Feel free to fork it and improve this non-optimized code.