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).

  • 1
    $\begingroup$ I know this is not answering your question, but how about padding your block with zeros? Working with powers of 2 is always comforting! $\endgroup$ – Atul Ingle Feb 23 '13 at 23:20
  • 2
    $\begingroup$ @AtulIngle That is a very bad idea in the context of the Walsh-Hadamard transform. $\endgroup$ – Dilip Sarwate Feb 24 '13 at 3:39
  • 1
    $\begingroup$ Just for completeness @dilip, why would it be a bad idea? $\endgroup$ – trican Feb 24 '13 at 11:34
  • 1
    $\begingroup$ The DFT method of computing a convolution always gives the cyclic or circular convolution of the input sequences. It is adapted to compute the linear convolution of sequences of lengths $L$ and $M$, say, by zero-padding the sequences to common length $N \geq L+M-1$ where $N$ is chosen so as to be able to use the FFT algorithm for the DFT most efficiently. The Walsh-Hadmard transform supports a different convolution, and cannot be used to compute linear convolutions via zero-padding. So, you could zero-pad, and use the FHT, but is $\mathbf xH$ really useful for anything? $\endgroup$ – Dilip Sarwate Feb 25 '13 at 3:12

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$.

| improve this answer | |
  • $\begingroup$ Many thanks for the extremely detailed response $\endgroup$ – trican Feb 24 '13 at 11:11
  • $\begingroup$ I never knew these things about the WHT. Thanks! $\endgroup$ – Atul Ingle Feb 25 '13 at 20:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.