Enzymind Labs

Flipping through a friends copy of Wolfram's "A New Kind of Science", I ran across an illustration of a 2-D basis set that exactly mirrored pencil drawings that Ted Bell made of all unique subsets of the 2-D Thue-Morse tiling. These drawings triggered an engineering geek response that they could be used to "decompose a sequence in terms of possible Thue-Morse subsequences (which forms a basis set for any sequence)".

The whole idea of doing function decomposition using this basis set has been done for a long time: they are called Walsh functions, and their symmetry and the details of using them (with Walsh transforms, known generally as Hadamard transforms) have been worked out. In fact, as I suspected, there is a fast Walsh transform that runs in O(nlogn) time, like the FFT.

And like PSR and I hinted, they can (and have) been used for image compression. This is the context within which they are presented in Wolfram's book.

Besides having interesting applications -- for example they are used in quantum computing -- I'm pumped because now I don't have to develop a whole new concept/method/code, it's all been done! I still think it might have new uses that haven't been developed. In particular I think the "Walsh spectrum" might be a good way to think about redundancy in images (or other signals), in the same way that the Fourier spectrum is used to think about periodicity. I'm betting that EE and information theory geeks have used them for this purpose with 1-D signals/codes for a long time.

As an aside, PSR might be interested to note that Walsh functions are closely related to the Haar wavelet, the first and simplest wavelet, before the name wavelet was used.

12:01:55 Here's an interesting link between the Walsh transform and "art theory".

12:05:05 From Wiki imgSeek: "imgSeek is a photo collection manager and viewer with content-based search and many other features. The query is expressed either as a rough sketch painted by the user or as another image you supply (or an image in your collection). The searching algorithm makes use of multiresolution Haar wavelet decomposition of the query and database images."

12:21:46 From Walsh Functions , A Digital Fourier Series : "Walsh functions are the digital answer to sines and cosines used in Fourier analysis."