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

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

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

• but, where's the boolean operation? Also does the multiplication takes less than $O(n^2)$ time? Nov 14, 2018 at 1:44
• The Boolean operation (which is actually not arbitrary) is the one used to define the convolution. Nov 14, 2018 at 1:45
• The multiplication can be done in time $O(n)$. Nov 14, 2018 at 1:45
• I mean that, if I calculate $\displaystyle C _ { i } = \sum _ { j \text{&} k = i } A _ { j } * B _ { k }$ and $\displaystyle C _ { i } = \sum _ { j\ xor\ k = i } A _ { j } * B _ { k }$, would the same Walsh matrix take effect? Nov 14, 2018 at 1:50
• or the matrix to multiply is not fixed? But thus the Walsh Matrix is fixed... Nov 14, 2018 at 1:53