6
$\begingroup$

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.

$\endgroup$
10
  • 2
    $\begingroup$ It would certainly help if you provided more context. Do they claim this to hold for all possible choices of $x$ or a specifically chosen input? What do they say about $f$? ChatGPT's answer is wrong and misleading. If you want to understand commutativity like this, then looking at the eigenstructure of the DFT is helpful. Two linear operators commute, if and only if there is a common basis of eigenvectors of the two. If $f$ is smooth and can be expanded into a power series, then each term in the series must be a power of a linear operator that commutes with the DFT. $\endgroup$
    – Jazzmaniac
    Mar 29 at 7:00
  • 7
    $\begingroup$ You would do better to ask a cat about the mathematical properties for the FFT. "Meow" is a clearly incorrect answer - it will not lead you astray. The stuff ChatGPT barfs up is misleading, but phrased with a certainty that cloaks the ignorance of the algorithm. It says "yes" with certainty, when in truth it has no concept - it has flipped a coin and spit out an answer based solely on the result of the coin toss. Why do people persist in asking technical questions of a chatbot? $\endgroup$
    – JRE
    Mar 29 at 14:43
  • 5
    $\begingroup$ ChatGPT has no knowledge. It knows nothing. It is a language model that assembles words into reasonable looking sentences. It neither knows nor cares if the content is correct or not. That's not its job. Its job is solely to string together words so that they look like sentences. It is only by accident that it ever returns a correct fact in response to a prompt. That's the reason that its references never check out (bad URLs and author names.) They are generated at random, just like the text. $\endgroup$
    – JRE
    Mar 30 at 5:45
  • 3
    $\begingroup$ How do you know that you have learned anything correct from ChatGPT? If you have the knowledge to recognize a correct statement when it makes one, then you didn't need to ask it. If you are asking it things outside of your own knowledge, you cannot tell if what it says is correct. You will have to verify it against other sources - which you could have referred to in the first place. ChatGPT increases your workload. Not only do you have to look up sources to verify its "answers," but you also have to filter out thr BS it gave you. Unless, of course, you accept the BS as adequate. $\endgroup$
    – JRE
    Mar 30 at 5:50
  • 2
    $\begingroup$ My policy (used on math.se) is "We are not here to debug ChatGPT". Feel free to adopt it if you wish. :-) $\endgroup$
    – JonathanZ
    Mar 30 at 16:24

5 Answers 5

9
$\begingroup$

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:

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.

$\endgroup$
9
  • 1
    $\begingroup$ @OverLordGoldDragon Turns out it's not a bug: it's documented as a feature. (Apparently the browser only has partial MathJax support, because MathJax in its entirety is too big. I'll see about getting it to use my local copy of LaTeX.) $\endgroup$
    – wizzwizz4
    Mar 30 at 13:32
  • $\begingroup$ Sorry for a late reply. This is an interesting approach. It's the first I've seen of DFT being applied as a matrix. How do I reconcile that with the notion that FFT is a family of "algoithm"s for calculating a DFT? How id D defined? Can I find some accessible reading on-line around this, the representation of a DFT(FFT) as a matrix? $\endgroup$ Apr 2 at 0:28
  • $\begingroup$ @BerndWechner, The fft() is just an implementation of the DFT. Hence, for mathematical analysis we only look at the DFT. The DFT is a linear operator, hence it can be formulated as a matrix. For instance, in MATLAB: mathworks.com/help/signal/ref/dftmtx.html. $\endgroup$
    – Royi
    Apr 2 at 0:38
  • 1
    $\begingroup$ @BerndWechner import numpy as np; import matplotlib.pyplot as plt; N = 128; t = np.arange(N)/N; DFT = np.array([np.cos(2*np.pi * k * t) - 1j*np.sin(2*np.pi * k * t) for k in range(N)]); x = np.random.randn(N) + 1j*np.random.randn(N); assert np.allclose(np.fft.fft(x), DFT @ x); plt.imshow(DFT.real, cmap='bwr'); plt.show(); plt.imshow(DFT.imag, cmap='bwr'); plt.show() $\endgroup$ Apr 2 at 15:03
  • $\begingroup$ Thanks, will check this later today. $\endgroup$ Apr 2 at 20:50
5
$\begingroup$

One (almost trivial) function is the ifft.

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

$\endgroup$
5
  • 2
    $\begingroup$ -1 yes, it's trivial. I've asked similar questions and such answers are really missing the point. $\endgroup$ Mar 29 at 11:19
  • 1
    $\begingroup$ Another trivial one is scaling, e.g. f(x) = 5 x $\endgroup$
    – jpa
    Mar 29 at 14:23
  • $\begingroup$ @jpa, I guess all matrices of the form $\alpha I$ will do. $\endgroup$
    – Mark
    Mar 29 at 14:43
  • $\begingroup$ Yeah, more interested in knowing if there is a property of f(x) that is required for this to hold true, for example linearity (not an uncommonly encountered property for which certain laws hold true that break in non-linear systems) or set of properties that have names. $\endgroup$ Mar 29 at 21:53
  • $\begingroup$ @BerndWechner, I think my answer gave you that. At least for linear operators. They must commute with the DFT operator. $\endgroup$
    – Royi
    Mar 30 at 4:55
1
$\begingroup$

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)
$\endgroup$
1
  • $\begingroup$ I'm not sure whether this is a special case of the Lebesgue measure but it's what this synchrosqueezing paper does (and ssqueezepy implements). Either way it's a nonlinearity we can define. $\endgroup$ Apr 7 at 12:32
0
$\begingroup$

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

$\endgroup$
3
  • 2
    $\begingroup$ It's astounding that you believe this is an answer worth providing. $\endgroup$
    – Jazzmaniac
    Mar 30 at 15:53
  • $\begingroup$ Then downvote it.-------- "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" --------- Perhaps if $f(\cdot)$ isn't linear, it works? $\endgroup$ Mar 30 at 19:39
  • 2
    $\begingroup$ In case you are, in fact, implying that only linear functions can possibly commute with the DFT, then you are plain wrong. $\endgroup$
    – Jazzmaniac
    Apr 6 at 19:34
-2
$\begingroup$

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?

$\endgroup$
2
  • 2
    $\begingroup$ Are you sure you've understood the question? You've just very elaborately shown that the identity and its scalar multiples commute with the DFT. That's true for every linear operator. So what's your point? $\endgroup$
    – Jazzmaniac
    Apr 6 at 19:33
  • $\begingroup$ Okay, if $$\begin{align} \mathbf{AB} &= \mathbf{C} \\ \mathbf{A}^{-1}\mathbf{AB} &= \mathbf{A}^{-1}\mathbf{C} \\ \mathbf{B} &= \mathbf{A}^{-1}\mathbf{C} \\ \mathbf{BA} &= \mathbf{A}^{-1}\mathbf{C}\mathbf{A} \\ \end{align}$$ Similarly $$\mathbf{BA} = \mathbf{B}\mathbf{C}\mathbf{B}^{-1} $$ Now what if either $\mathbf{A}$ or $\mathbf{B}$ is the DFT twiddle matrix? $\endgroup$ Apr 7 at 21:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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