1
$\begingroup$

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.

  • 2
    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.2012-02-16
  • 0
    @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.2012-02-16
  • 1
    See "Decomposition of Binary Matrices and Fast Hadamard Transforms" (CSSP) by Hakob Sarukhanyan, Sos Agaian, Jaakko Astola, and Karen Egiazarian (not publicly available...)2012-02-26
  • 1
    Please see S.R. Webb ; J.D. Kennedy, "Some Comments on the Fast Hadamard Transform of Order Twelve", http://ieeexplore.ieee.org/abstract/document/1671898/2017-10-26

0 Answers 0