The discrete Fourier transform $$ X_k = \sum_{m=0}^{n-1} x_m e^{-2\pi ikm/n} $$ can be computed via Cooley–Tukey FFT algorithm
The key of the algorithm is the butterfly transform, given by $$ X_k = E_k + \omega^k \cdot O_k\\ X_{k + N/2} = E_k - \omega^k \cdot O_k\\ \omega = e^{\frac{2\pi i}{N}}. $$ The $\omega^k$ value is called "twiddle factor". I've implemented this algorithm and it worked flawlessly.
Then I've replaced twiddle factor with unity, making the butterfly transform look like $$ X_k = E_k + O_k\\ X_{k + N/2} = E_k - O_k $$ This looks very much like Haar transform, but is different.
This transform has some remarkable properties:
- It transforms real data to real data
- Its matrix is symmetric
- Its matrix is orthogonal (up to $\sqrt{n}$ factor)
- It is self inverse (follows from previous two)
- Its matrix contains only $\pm 1$ (no zeros). Here's the matrix portrait for $n = 32$
and the matrix for $n=8$ $$ \begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & -1 & -1 & -1 & -1 \\ 1 & 1 & -1 & -1 & 1 & 1 & -1 & -1 \\ 1 & 1 & -1 & -1 & -1 & -1 & 1 & 1 \\ 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1 \\ 1 & -1 & 1 & -1 & -1 & 1 & -1 & 1 \\ 1 & -1 & -1 & 1 & 1 & -1 & -1 & 1 \\ 1 & -1 & -1 & 1 & -1 & 1 & 1 & -1 \\ \end{pmatrix} $$
There are some questions that interest me:
- Is this discrete transform known?
- Can it be expressed like DFT?
- Is there any convolution theorem for this transform?
Update. Here's an explicit formula I've obtained. Let $\vec k$ be the binary representation of $k$ treated as a vector in $\mathbb Z^d$. Then $$ X_k = \sum_{m = 0}^{n-1} x_m (-1)^{\vec k^\top J \vec m} $$ where $J$ is the exchange matrix. In other words $$ X_k = \sum_{m = 0}^{n-1} x_m (-1)^{\phi(\vec k, \vec m)} $$ and $$ \phi(\vec k, \vec m) \equiv \sum_{i = 1}^{d} k_i m_{d+1-i} = \phi(\vec m, \vec k), \qquad d = \log_2 n $$
Also, removing bit-reversal permutation in CT algorithm leads to a similar transform with $$ X_k = \sum_{m = 0}^{n-1} x_m (-1)^{\psi(\vec k, \vec m)}\\ \psi(\vec k, \vec m) \equiv \sum_{i=1}^d k_i m_i = \psi(\vec k, \vec m). $$
The transform matrix is a Hadamard matrix, and the transform that you described is is known as fast Walsh-Hadamard transform. See also the more general description of Hadamard transforms.