New answers tagged

1 vote
Accepted

Can I reduce the complexity of multiplication with FFT if the input vector is repeating?

A few clarifications may help. You can implement the Discrete Fourier Transform (DFT) using a multiplication with Fourier Transform Matrix that's made up of the twiddle factors but this is NOT an FFT. ...
user avatar
  • 31.5k
2 votes

What are the criteria for a change-of-basis transform to be doable in $O(n \log(n))$?

It sounds like you want to design a process that will more or less automatically arrive at the FFT for its functional and computation cost trade-off when that is optimal. And any other related (or not)...
user avatar
  • 2,186
1 vote

What are the criteria for a change-of-basis transform to be doable in $O(n \log(n))$?

The usual reason you see $O(n \log(n))$ computations is when the $n^2$ direct-approach can be decomposed into two $n/2$ problems, and those can be decomposed into four $n/4$ problems etc. So the thing ...
user avatar
  • 22.5k
0 votes

What is the frequency representation of nonuniform sampling?

Matlab has the nufft which uses: For a vector $X$ of length $n$, sample points $t$, and frequencies $f$, the nonuniform discrete Fourier transform of $X$ is ...
user avatar
  • 22.5k
0 votes

What is the frequency representation of nonuniform sampling?

If the samples are finite (e.g. not a running process) then you'd have to take the greatest common divider and resample all the vector, resulting in a "toothless" train of impulses. For ...
user avatar
0 votes

What is the frequency representation of nonuniform sampling?

For the simplest case of $N$ random samples of $x(t)$ taken over a duration of $T$ and satisfying the average Nyquist rate criterion, then the resulting Fourier transform of the non-uniform samples ...
user avatar
  • 26.7k
0 votes

How to choose between taking the real part or the absolute value of an inverse discrete Fourier transform?

I happened to need solving the same question, so thanks for sharing this (although a while ago). However I'd like to complement or even somehow correct the accepted answer. There's a big difference ...
user avatar
  • 1
1 vote
Accepted

Problem with the existence of inverse DTFT

You're absolutely right, the given system doesn't have a frequency response, at least not as a conventional function. There's a pole on the unit circle, so the system is not stable (actually, it is ...
user avatar
  • 80.2k
0 votes

Why Does the DFT Assume the Transformed Signal Is Periodic?

I have a different way of describing this so will add an additional answer. How I interpret any comment that "the DFT assumes the input is periodic" is that the resulting answer in the DFT ...
user avatar
  • 37.1k
2 votes
Accepted

Validity of taking an inverse $\mathcal{Z}-$ transform instead of taking an inverse DTFT

Let's first clear up a misunderstanding: the inverse DTFT and the inverse $\mathcal{Z}$-transform are equally simple or difficult to compute; the integrals are the same. If you use the contour $|z|=1$ ...
user avatar
  • 80.2k
3 votes
Accepted

Axes of Discrete Fourier Transform

Actually there are more than two answers for the DFT’s x-axis. I’ve seen spectral plots where an N-point DFT’s positive-frequency axis range is labeled: • Zero -to- N/2 (Frequency axis value is ...
user avatar
0 votes

How does one interpret an element of the "transfer matrix" used to calculate frequency domain granger causality (via VAR models)?

If you take the Fourier Transform of your AR equation, you get $$\begin{align} Y(f) &= \sum_{k=1}^p A(k)e^{-j2\pi f k} Y(f) + U(f)\\ \left(I - \sum_{k=1}^p A(k)e^{-j2\pi f k}\right) Y(f) &= U(...
user avatar
  • 399
0 votes

Convolution of squares / boxcars

I'll give this a whirl. Let's define the causal rectangular function $R(t)$ to be $$ R(t) = \left\{\begin{matrix} 1 & 0 < t < 1 \\ 0 & else\\ \end{matrix}\right.$$ Let's find $Y(t) = R(...
user avatar
  • 31.5k
0 votes

Fourier transform of modulus of sum of sines

I have implemented and validated @AndyWalls' result for discrete use: Not yet performance optimized, and the optimal version is fairly quick, heaviest steps being 1) three $N$-sized FFTs, 2) one $N$-...
user avatar
-1 votes

Convolution of squares / boxcars

Apply convolution theorem: $$ |A||B|\ \mathrm{sinc}(A\omega/2) \ \mathrm{sinc}(B\omega/2) $$ WA gives for $\mathcal{F}^{-1}$, disregarding constants, $$ \begin{align} && (A + B - 2t) \ \...
user avatar
11 votes
Accepted

Fourier transform of modulus of sum of sines

$$\begin{align*}\mathscr{F}\left\{x(t)\right\} &= \mathscr{F}\left\{\left|\cos\left(\omega_0t\right)+\cos\left(\omega_1t\right)\right|\right\}\\ \\ &= 2 \mathscr{F}\left\{\left|\cos\left(\...
user avatar
  • 2,525

Top 50 recent answers are included