Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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