What's the connection between the two "Fast Walsh Transform"?

Question

First Let's take a look at the convolution $\displaystyle C _ { i } = \sum _ { j \oplus k = i } A _ { j } * B _ { k }$, and the $\oplus$represents any boolean operation. And we are able to evaluate $C$ in $O(n \log n)$ time, using an algorithm called Fast Walsh Transform, where $n$ represents the length of the binary digits.

However, when looking at wikipedia page, it says that the Walsh Transform is to accelerate the evaluation of an $n \times n$ Matrix called Walsh Matrix. I also found it reasonable.

My question is, what's the connection between the two evaluations? I know that a convolution is a linear transformation and can be represented as a vector multiplied by a matrix. But where's the matrix in the First convolution? I am so confused, and does it represent that some multiplications with specified matrixed could be accelerated to $O(n \log n)$? (Thus the matrix is $n \times n$)

Answer 1

Suppose that $A$ and $B$ are vectors of length $n$, where $n$ is a power of 2. We index $A$ and $B$ using binary vectors of length $\log_2 n$, and define their convolution $C$ as $$ C_i = \sum_{j \oplus k = i} A_j B_k. $$

You can calculate the convolution of $A$ and $B$ using the following algorithm:

• Compute the Walsh transform of $A$: $\alpha = H_n A$.
• Compute the Walsh transform of $B$: $\beta = H_n B$.
• Multiply $\alpha$ and $\beta$ pointwise: $\gamma(S) = \alpha(S)\beta(S)$ for all $S$.
• Compute the inverse Walsh transform of $\gamma$: $C = H_n^{-1} \gamma$.

(Note that up to normalization, $H_n^{-1}$ and $H_n$ are the same matrix.)

The way we compute the convolution of $A$ and $B$ is using the Walsh transform and its inverse. The Walsh transform itself simply consists of multiplying a vector by the Walsh matrix, which can be done in $O(n\log n)$ time. Since the third step takes only $O(n)$ time, the entire algorithm runs in $O(n\log n)$.