Under what conditions does DFT(f(x)) = f(DFT(x)) hold?

Question

I have encountered a text (a specification) in which $$\text{FFT}\left(f\left(x\right)\right) = f\left(\text{FFT}\left(x\right)\right)$$ is clearly presumed (for the functions they are applying).

Thus, I believe a composite function and the property sought is commutativity (of the composite function).

What I would like is an accessible reference about the conditions where $\text{DFT}\left(f\left(x\right)\right) = f\left(\text{DFT}\left(x\right)\right)$ holds, to both:

• read, and boost my confidence in any conclusion, and
• to cite in my summary of the text I'm reading (which is a specification and simply describes an implemented procedure/algorithm, and doesn't provide any references or citations).

Oh, of course, the application is DSP, these are discrete functions (a sampled analogue signal already filtered and downsampled a few times but hey), at this point an FFT is taken for the frequency spectrum and I see this emergent premise in the presented spec: $\text{FFT}\left(f\left(x\right)\right) = f\left(\text{FFT}\left(x\right)\right)$

It's a classic engineering document in that sense ;-). The goal is not to teach the reader DSP, it is simply to specify a required implementation.

Answer 1

The fft is an efficient computation of the DFT.
So your question is about the DFT, not the fft.

The DFT of a signal can be applied using a matrix operation:

$$ \boldsymbol{f}_{x} = D \boldsymbol{x} $$

Where $ \boldsymbol{f}_{x} $ is the vector of the DFT transform of $ \boldsymbol{x} $.

What you're asking is when:

$$ g \left( D \boldsymbol{x} \right) = D g \left( \boldsymbol{x} \right) $$

Where $ g : \mathbb{C}^{d} \to \mathbb{C}^{d} $.

Linear Model

One trivial solution is the identity matrix / function.
Another solution is assuming the function $ g $ is a linear operator, then:

$$ G D \boldsymbol{x} = D G \boldsymbol{x} $$

So basically we're looking for a commuting pair of matrices.
As written in the Wikipedia page, commuting can be assured if both operators share the same underlying eigen vectors (Roughly speaking).

You may find many algorithms to generate matrices which commutes with the DFT operator:

• Generalized Commuting Matrices and Their Eigenvectors for DFTs, Offset DFTs, and Other Periodic Operations.
• Efficient computation of DFT commuting matrices by a closed form infinite order approximation to the second differentiation matrix.

It is worth also to have a peek at Discovering Transforms: A Tutorial on Circulant Matrices, Circular Convolution, and the Discrete Fourier Transform.

Sylvester Equation

As @RodrigodeAzevedo wrote, we can formulate the above as a Sylvester Equation:

$$ A X + X B = 0 $$

Where $ A = D $, $ B = -D $ and $ X = G $.

Since in our case $ A $ and $ -B $ share an eigen value (Share all eigenvalues) we don't have a unique solution but many solutions.

Answer 2

One (almost trivial) function is the ifft.

So fft(ifft(x))=ifft(fft(x)).

Answer 3

Nonlinear examples

1. Sum of square moduli

$$ f(\cdot) = \sum |\cdot|^2 \tag{1} $$

-->

$$ \texttt{DFT}\left\{ \sum_{n=0}^{N-1} \left|x[n]\right|^2 \right\} = \sum_{k=0}^{N-1} \left| \texttt{DFT}\left\{ x[n] \right\} \right|^2 $$

assuming the $1/\sqrt{N}$ definition. This is simply Parseval-Plancherel's theorem.

The result can be interpreted as a joint statement on conservation of energy and information, in that the equality of sums is former, and that the fft(x) == x for len(x) == 1 is enabled by an invertible basis which returns an identity to refelct that there's no "variation" in a length-one sequence, only an offset that equals itself.

$(1)$ can be made much stronger by realizing that the result is permutation-invariant - e.g.

$$ f(\cdot) = \sum \left| \texttt{random_shuffle}(\cdot) \right|^2 \tag{1b} $$

so now $f$ is non-deterministic.

2. Sum of Lebesgue measure

$$ f(\cdot) = \sum \lambda (\cdot ) \tag{2} $$

-->

$$ \begin{align} \texttt{DFT}\left\{ \sum_{n=0}^{N-1} \lambda(x[n]) \right\} &= \sum_{k=0}^{N-1} \lambda\left( \texttt{DFT}\left\{ x[n] \right\} \right) \\ \Rightarrow N &= N \end{align} $$

This is simply fft(len(x)) == len(fft(x)). This is trivial-looking, but in general the Lebesgue measure is far from trivial.

The result is nothing special besides implying a possibility for invertibility via N_in >= N_out - but also the bit on fft(x) == x.

1 & 2 generalization

Works for all operation(x) == operation(fft(x)) if len(operation(x)) == 1.

3. Non-aggregate results

Aggregation destroys tons of information, which eases attaining commutativity and a bunch of other things. Still, $(1)$ isn't trivial.

If $f$ is to be nonlinear and pointwise-only, it must concern itself with symmetries and complex values. If $x$ is real-valued, then $\texttt{DFT}(x)$ is Hermitian-symmetric even if $x$ isn't, which forces symmetry and uniqueness (avoiding one-to-many) considerations onto $f(\texttt{DFT}(x))$. And $\texttt{DFT}(f(x))$ is guaranteed to be not Hermitian symmetric if $f(x)$ is complex-valued. Note that Royi's answer isn't pointwise-only, and the only pointwise-only $f$ that's linear appears to be the trivial $f(x) = \text{const} \cdot x$.

The case of non-aggregate output that involves aggregate operations has lot more freedom per not restricting its output at index $n$ to be derived only from input at index $n$; symmetry considerations remain, but are easier to satisfy.

Code

import numpy as np

def f1(g):
    np.random.shuffle(g)  # test the stronger version; in-place op
    return np.sum(np.abs(g)**2)
    
def f2(g):
    return np.sum(np.ones(len(g)))

def fft_alt_norm(x):
    x = np.atleast_1d(x)  # in case len(x) == 1
    return 1/np.sqrt(len(x)) * np.fft.fft(x)
    
for N in (128, 129):
    x = np.random.randn(N) + 1j*np.random.randn(N)
    for f in (f1, f2):
        a = fft_alt_norm(f(x))
        b = f(fft_alt_norm(x))
        assert np.allclose(a, b)

Answer 4

$f(\cdot)$ better, the hell, be linear.ㅤ

Answer 5

Let's see if Jazz dislikes this answer any less.

I am going to use the unitary definition of the DFT:

$$ X[k] \triangleq \mathcal{DFT}\Big\{x[n] \Big\} \ = \ \frac{1}{\sqrt{N}} \sum\limits^{N-1}_{n=0} x[n] \ e^{-j2\pi n k/N} \qquad x[n] \in \mathbb{C} $$

$$ x[n] \triangleq \mathcal{DFT}^{-1}\Big\{X[k] \Big\} \ = \ \frac{1}{\sqrt{N}} \sum\limits^{N-1}_{k=0} X[k] \ e^{+j2\pi n k/N} \qquad X[k] \in \mathbb{C} $$

I will insist that $N\in\mathbb{Z}>0$ and we know that

$$ x[n+N] = x[n] \qquad \forall \ n\in\mathbb{Z} $$ and that $$ X[k+N] = X[k] \qquad \forall \ k\in\mathbb{Z} $$

And, from that we also know that

$$ x[n+2N] = x[n] \qquad \forall \ n\in\mathbb{Z} $$ $$ X[k+2N] = X[k] \qquad \forall \ k\in\mathbb{Z} $$

and that

$$ x[n+mN] = x[n] \qquad \forall \ n,m\in\mathbb{Z} $$ $$ X[k+mN] = X[k] \qquad \forall \ k,m\in\mathbb{Z} $$

We also know that

$$ \mathcal{DFT}\Big\{\sum\limits_{\ell \in\mathbb{Z}} a_\ell x_\ell[n] \Big\} = \sum\limits_{\ell \in\mathbb{Z}} a_\ell\mathcal{DFT}\Big\{x_\ell[n] \Big\} \qquad a_\ell \in \mathbb{C} $$

So define your function $f(\cdot)$ to be

$$ f\big( x[n] \big) \triangleq \sum\limits_{\ell=0}^{N-1} a_\ell \ x[n+m_\ell N] \qquad m_\ell \in \mathbb{Z} $$

That $f(\cdot)$ is commutative with the DFT.

We know that

$$ \mathcal{DFT}\Big\{f\big(x[n]\big) \Big\} = f\left( \mathcal{DFT}\Big\{x[n] \Big\} \right) $$

Now the next step is: What about time (or frequency) reversal and what about even or odd symmetry?