I am quite glad to witness a revival around the Walsh-Paley-Hadamard (or sometimes called Waleymard) transformations, see How we can use the Hadamard transform in feature extraction from an image?
They are particular instance of Rademacher functions. They form orthogonal transformations which can, omitting power normalizations, be implemented with only adds and subtracts, and potentially binary shifts. Basically, they require no multiply, allowing fast computations and little fancy floating point needs.
Their vector coefficients are made of $\pm 1$, that mimic a binarized version of sine or cosine bases. The ordering of Walsh vectors is in sequency (instead of frequency) that counts the number of sign changes. They enjoy similar butterfly algorithms for even faster implementation.
Walsh-sequences of length $2^n$ can also be interpreted as instances of a Haar wavelet packet.
As such, they can be used in any application where cosine/sine or wavelet bases are used, with a very cheap implementation. On integer data, they can remain integer, and allow truly lossless transformations and compression (similarly to integer DCT or binary wavelets or binlet). So one can use them in binary codes. They are used in compressive sensing as well.
Their performance is often considered poorer than other harmonic transforms on natural signals and images, because of their blocky nature. However, some variants are still in use like for reversible color transformations (RCT) or low-complexity video coding transforms (Low-complexity transform and quantization in H.264/AVC).
- Agaian, S. S., Hadamard Matrices and Their Applications, 1985
- Beauchamp, K. G., Walsh functions and their applications, 1975
- Harmut, H. F., Transmission of information by orthogonal functions, 1970
- Real-time video compression algorithm for Hadamard transform processing (NASA, 196)
- A real-time adaptive Hadamard transform video compressor (NASA, 196)