2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ but, where's the boolean operation? Also does the multiplication takes less than $O(n^2)$ time? $\endgroup$ – FFjet Nov 14 '18 at 1:44
  • $\begingroup$ The Boolean operation (which is actually not arbitrary) is the one used to define the convolution. $\endgroup$ – Yuval Filmus Nov 14 '18 at 1:45
  • $\begingroup$ The multiplication can be done in time $O(n)$. $\endgroup$ – Yuval Filmus Nov 14 '18 at 1:45
  • $\begingroup$ 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? $\endgroup$ – FFjet Nov 14 '18 at 1:50
  • $\begingroup$ or the matrix to multiply is not fixed? But thus the Walsh Matrix is fixed... $\endgroup$ – FFjet Nov 14 '18 at 1:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.