-2
$\begingroup$

We know fft(cos), and abs(cos) is just positive cos with halved period, so seems there should be an exact relationship between fft(cos) and fft(abs(cos)), and therefore between any fft(x) and fft(abs(x)). For example:

enter image description here

I've not seen it anywhere, and some publications rely on approximations in case of continuous Fourier Transform, which seems unnecessary. But this question concerns the DFT: is there such a property?

I only seek a relationship $\text{ifft}(\text{operation}(\text{fft}(x))) \equiv |x|$.

$\endgroup$
21
  • $\begingroup$ what do you mean with "abs(cos) is just positive cos? Yes, there's a relationship, so what are you wondering about? $\endgroup$ Jun 29 at 18:00
  • $\begingroup$ @MarcusMüller Relating fft(abs(x)) to fft(x), like time shift property. $\endgroup$ Jun 29 at 18:15
  • 2
    $\begingroup$ there's no such reversible relationship – abs is not invertible, so there can't be. It's especially also a non-linear operation, so fft(abs(signal_a+signal_b) != fft(abs(signal_a))+fft(abs(signal_b)). But none of this is surprising to you, I think, right? $\endgroup$ Jun 29 at 18:42
  • 2
    $\begingroup$ I'm still confused what your title means, what it has to do with the text of your question? $\endgroup$ Jun 29 at 18:43
  • 1
    $\begingroup$ @MarcusMüller Invertibility is not a criterion for a relationship. E.g. subsampling. $\endgroup$ Jun 29 at 18:51
3
$\begingroup$

I only seek a relationship $\text{ifft}(\text{operation}(\text{fft}(x))) \equiv |x|$.

So, let's $\DeclareMathOperator{\DFT}{DFT}\DeclareMathOperator{\IDFT}{IDFT}$ be a bit more clean here:

The FFT (IFFT) is just a fast-to-compute implementation of the DFT, so let's use the mathematical concept instead of the method to calculate its result. You demand an $\text{operation}$ for which

$$\IDFT\left(\text{operation}\left(\DFT(x)\right)\right) = |x|.$$

Since $\DFT(x)$ is an $N$-long vector of complex numbers, $\text{operation}$ maps $\mathbb C^N \mapsto C^N$, so let's give it a letter: $g(y): \mathbb C^N \mapsto \mathbb C^N$.

Let's rewrite your equation in this notation (nothing changed from your original statement):

$$\IDFT\left(g\left(\DFT(x)\right)\right) = |x|.$$

Now, the $\IDFT$ is bijective, even invertible (by, surprise, the $\DFT$), so this is equivalent to

$$g\left(\DFT(x)\right) = \DFT\left(\lvert x\rvert\right).$$

Now, there's infinitely many $x$ with the same $|x|$, and even for real-only $x$, it's still $N^2$ different $x$. (You get $N^2$ permutations of signs for all the elements of $x$).

Let's substitute $y=\DFT(x)$: $$g\left(y\right) = \DFT\left(\lvert \IDFT(y)\rvert\right)$$

What is written literally spells out: The operation you're looking for is first IDFT'ing your input, then calculating the absolute, then DFT'ing the result (that suggests there's no shortcut).

Let's rule out any candidates for simpler representations:

  • $|x|$ is not linear ($|-2|+|1|\ne |-2+1|$), so $g$ can't be linear either;
    • it hence can't be an integral, or a polynomial
  • $g$ is not differentiable ($|x|$ isn't, and the DFT can't do anything about the points where it isn't)
    • therefore, $g$ can't also be a differentiable function or linear combination of such

Not quite sure for what other kinds of relationships you're looking for, but if a relationship isn't linear, not even differentiable, and the "native" way is IDFT->abs->DFT, then in my terms, there's no "easier" way to express the relationship than through actual computation of the abs.


This comes very natural to signal processing folks – we all know that nonlinear operations like abs (but also, squaring, taking the signal as exponent and such) lead to distortions that mean that suddenly all components in the signal mix with each other, and you can't find an easy expression for the result of a Fourier transform anymore. It's really that simple: While the FT of a sum of many tones is simply the combination of the FT of all the tones, as soon as you introduce any nonlinearity, the whole "summability" breaks down, and you get intermodulation problems.

This is especially easy to see for the abs of a sine: To calculate the abs, you just need to multiply the sine wave with a -1,+1 square wave that has the same frequency and is shifted just right so that the negative half-periods are the same (in other words, it's the signum function of the sine!). That means your spectrum is the convolution of the sine's spectrum, which is one (complex) or two (real sine) diracs, convolved with an infinite series of diracs (from the Fourier series of the square wave); the result is an infinite series of diracs....

Now, when you have more than one sine, you get one of two cases:

  1. both tones' frequencies are rationally related: the "absolutifying" "not-really-square"-wave for the sum of the two sines (i.e. the signum of the sum) is now a repeating, but within one periode irregular wave. Its spectrum is hence a line spectrum with infinitely many, interestingly-spaced diracs.
  2. both tones' frequencies are not rationally related: oh well; your signum function isn't periodic. So, you convolve the sum of the sine spectra with the spectrum of an aperiodic function - which is continuous. So, the spectrum becomes continuous! This is really really awkward.

So, the absolute value can make formerly easy spectra arbitrarily complex. Sorry, there's no easier representation for it!

$\endgroup$
13
  • $\begingroup$ whatta autopsy. +1 $\endgroup$ Jun 29 at 20:45
  • $\begingroup$ Nice Marcus! +1 $\endgroup$ Jun 29 at 22:02
  • $\begingroup$ I like the part where, in mentioning non-linear operators like abs() to SP folks, there's a sigh of relief similar to when someone cancels plans that you didn't want to participate in the first place lol. $\endgroup$
    – Envidia
    Jun 29 at 22:19
  • $\begingroup$ The $g(y)$ argument is tautological and can repeat for any other DFT property. Squaring is nonlinear and the relation is self-convolution, which is an integral. The rest of statements amount to "it's hard to figure out". Not convinced. $\endgroup$ Jun 30 at 2:27
  • 1
    $\begingroup$ @OverLordGoldDragon if the operation you are looking for is a function, it equals to $g(\cdot)$. I don't know if there is a "meaningful" property that is not shared between two functions that equal. $\endgroup$
    – AlexTP
    Jun 30 at 15:32
2
$\begingroup$

I like where you are heading, but don't see a consistent relationship would exist and here is why:

First consider a single DFT bin as a rotating phasor in time on the complex plane. The absolute value of that in time will be constant (so any single such tone would translate completely to bin 0 or the DC bin).

Now consider the real tones such as a cosine or sine, which result in two complex conjugate phasors that sum to the real axis. The absolute value of this will go up and down at twice the rate, and a DC offset (mean) would also be created, thus manifesting as a DC bin and a bin at twice the frequency (as depicted). Other tones will occur due to the non-linearity (abrupt change in direction) which should predictably be at higher harmonics of that 2f signal (also as depicted). Note that abrupt change occurs when the sum of the phasors (in time) passes through the origin on the complex plane.

So now consider what happens if we add in any other arbitrary single tone, another spinning phasor in time as another independent bin in frequency. To the extent that the combined sum of all the tones does not cross through the origin specifically, the absolute value will not create the non-linearity that creates additional frequency tones (other than the frequency translation property due to envelope restoration / AM demodulation, as further detailed below).

Note however this relationship that does occur: For real signals if the signal is never negative we get "Envelope Restoration" which is AM demodulation and with that we get a clean and predictable frequency translation from a carrier to baseband of all amplitude modulated components (and phase modulation is eliminated), with all relationships intact between the modulated signal and carrier (just after translation relative to baseband). The same effect applies to complex signals that never pass through the origin. This perspective assumes that a single tone carrier is being modulated such that we can get the simple translation of the AM spectrum. If the carrier itself is a modulated waveform with AM and PM components, we get an interesting result that the convolved AM spectrum will translate to baseband.

For all other cases, (with boils down to signals that pass through the origin on the complex plane), additional frequencies will be created due to the non-linear distortion of taking an absolute value of such a signal. Such passing through the origin reduces to a sign change for any real signal.

$\endgroup$
10
  • $\begingroup$ Thanks for your thoughts. 1) We can have a complex x whose abs(x) never decays to zero while still creating extra frequencies: xf = np.abs(np.random.randn(128)); xf[35:] = 0; x = ifft(xf) -- 2) It's true that abs of any cisoid will collapse to DC -- 3) What do you make of the real-only case? $\endgroup$ Jun 29 at 19:46
  • $\begingroup$ For context, this arose in a discussion on the claim that wavelet scattering is contractive in bandwidth, i.e. bw_new <= bw_old. There's proof in continuous time that, given some properties on psi, |conv(x, psi)| will be contractive in bandwidth - 4, 5, 6 here. However this holds only approximately in practice due to finiteness and discretization error, and I sought to find an exact quantification. $\endgroup$ Jun 29 at 19:46
  • $\begingroup$ Yes good clarification, it is that it is passing through zero (as a real function always will when it changes sign), even though we don't have an actual sample that lands on zero. Can you come up with a case that doesn't pass through the origin (so in this case a complex signal, as any real signal would have to be always positive or always negative for this condition to hold)? I have very limited time today so probably won't be back to see until tomorrow, including your last link etc but interesting! $\endgroup$ Jun 29 at 19:50
  • 1
    $\begingroup$ No I don't mean that, I mean specifically not passing through the origin on the complex plane (both real and imaginary can change sign, just not concurrently). Consider the single spinning phasor $e^{j \omega t}$, it's magnitude would be 1 constant and therefore a bin at DC...I guess that is one example right there of creating new frequencies (although this was a translation, no additional ones were created). How does the complete set of all such complex waveforms that don't pass through the origin behave? Is there any that would produce more tones than originally existed?) $\endgroup$ Jun 29 at 20:09
  • 1
    $\begingroup$ The result depends on what other frequencies are also present - to the point that nothing happens if we don’t cross zero (go negative for reals) and you have to consider all other components present to decide if it changes sign. Yes spinning phasers or more specifically viewing “frequency components” using $e^{j omega t}$ is much simpler mathematically and then intuitively as well once you visualize it than using sines and cosines (yuck!). Compare the formula for the Fourier Series Expansion in both forms to see what I am referring to; or analyze a single-sideband frequency translation $\endgroup$ Jun 30 at 17:52

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.