image processing - Can the Walsh Hadamard transform be computed for non power of 2 sizes?

Can the walsh hadamard transform be calculated for odd image block sizes such as 5x5 or 7x7? Most of the examples I've seen are for 4x4 and 8x8?

I fear it probably can't from the description I read on Wikipedia ( though I'm still trying to fully digest that page).

Answer

The Walsh-Hadamard transform requires a Hadamard matrix -- which has entries $\pm 1$ and whose rows are orthogonal vectors. A $n \times n$ Hadamard matrix is known to exist for $n = 2$. Larger Hadamard matrices can exist only if $n$ is a multiple of $4$, though it is not known if there is a Hadamard matrix for every multiple of $4$. However, there is a recursive construction that can be used to construct a $2^m \times 2^m$ Hadamard matrix from a $2^{m-1}\times 2^{m-1}$ Hadamard matrix, and this structure allows for the use of the Fast Hadamard Transform algorithm, which reduces the computational cost from $2^{2m}$ additions and subtractions to $m2^m$ additions and subtractions (just like the $N$-FFT reduces the number of multiplications from $O(N^2)$ to $O(N\log N)$.

With this as background, the answer is Yes, you can use a Walsh-Hadamard transform of length $N$ if you can find a $N\times N$ Hadamard matrix, but your choices for $N$ are necessarily restricted. Also, fast algorithms may not exist for your choice of $N$, though some speed-up is usually possible.

Note that Walsh-Hadamard transforms (WHTs) do not support cyclic convolutions, but they do support what is sometimes called Poisson convolution. If $H$ denotes a $2^m\times 2^m$ Hadamard matrix and $\mathbf x$ and $\mathbf y$ are vectors of length $2^m$ with \WHTs $\mathbf xH$ and $\mathbf yH$, then the inverse WHT of the term-by-term multiplication of the entries in $\mathbf xH$ and $\mathbf yH$ can be described as follows. Suppose that the entries in $\mathbf x$ and $\mathbf y$ etc are indexed not by integers $0$ through $2^m-1$ but rather by the $m$-bit representations of these numbers. Thus, we talk not of $x[k]$ as the $k$-th entry in $\mathbf x$ but rather of $x[\mathbf k]$ where $\mathbf k$ is the $m$-bit representation of $k$. Then, the iWHT of the term-by-term product of the entries in $\mathbf xH$ and $\mathbf yH$ has $\mathbf k$-th entry $$\sum_{\mathbf i} x[\mathbf i]y[\mathbf k\oplus \mathbf i]$$ which is eerily reminiscent of $$\sum_i x[i]y[k-i]$$ and even more so if one notes that modulo two, addition and subtraction are the same and so that $\mathbf k\oplus \mathbf i$ could as well have been written as $\mathbf k\ominus \mathbf i$.