The Noiselet Transform featured in the Monday Morning Algorithm 15 was not designed to be fast. However there is an increasing number of applications in the imaging world that requires it to be so. Laurent Jacques, another reader of this blog, decided to share his fast noiselet transform with us. In his words:
Since I needed that personally for my research, and since I read on Nuit Blanche that you were perhaps both interested in it for CS applications (or for Monday Morning Algos), I have "implemented" a Fast Noiselet Transform (1-D and 2-D). I put that in the attached archive FNT.zip (five .m files : fnt*d.m ifnt*.m, with *=1,2, + one internal file)The implementation of this fast algorithm requires N log2 N additions and subtractions, with N being the total number of elements in the signals. It is now listed in the Compressed Sensing Code page and can be downloaded here. It's a coincidence but I just attended a talk by Jean-Luc Starck where he described the scheme to be used on Herschel in 2009, which will use a 2-D randomized noiselet transform.
Actually, this is nothing but a slight variation of a Fast Hadamard Transform found on Matlab exchange, but it does the job. The initial Hadamard code is the one of Gylson Thomas at the Mathworks site: fwht1d.zip and fwht2d.zip
I liked Laurent's implementation (seen on both of your blogs) but, if I'm right, it was just for the noiselet matrix construction and not for a fast noiselet transform. This matrix is however very helpful for small-length vector multiplications. I have checked that a multiplication with Psi'=Build_Noiselets' and the use of fnt1d() provides the same outputs.
Thank you Laurent.
No comments:
Post a Comment