Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have to process vectors through a Hadamard matrix of order N.

If N is a power of 2, I can use the Fast Walsh–Hadamard transform; but if N is not a power of two (for instance, N=12), it is not possible, however i would like to avoid the direct matrix product.

Is there any generalization of the Fast Walsh–Hadamard transform for N ≠ 2^k? Thanks.

share|cite|improve this question
The Fast Walsh-Hadamard Transform is based on the recursive block structure of Hadamard matrices of order $2^k$ as $$H_{2^k} = \left[\begin{matrix} H_{2^{k-1}} & H_{2^{k-1}}\\ H_{2^{k-1}} & -H_{2^{k-1}}\end{matrix}\right].$$ When the order is not a power of $2$, such a block structure would at best recurse a few times, and then you are still left with a (smaller) matrix-vector product to compute. The saving grace is, of course, that no multiplications need be used; additions and subtractions suffice to compute the matrix-vector product. – Dilip Sarwate Feb 16 '12 at 14:35
@Dilip: so, given a kernel of transform capable of processing a vector of order N (say, I build it for N=12), I can use the butterfly pattern to process any vector of size M=N*2^k. That's weird I can't find any optimized kernel (for instance of order 12) for such an usage. – moala Feb 16 '12 at 14:52
See "Decomposition of Binary Matrices and Fast Hadamard Transforms" (CSSP) by Hakob Sarukhanyan, Sos Agaian, Jaakko Astola, and Karen Egiazarian (not publicly available...) – moala Feb 26 '12 at 15:05

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.