# Tag Info

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. ...
• 31.5k

### 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)...
• 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 ...
• 22.5k

### 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 ...
• 22.5k

### 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 ...
• 1,423

### 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 ...
• 26.7k

### 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 ...
• 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 ...
• 80.2k

### 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 ...
• 37.1k
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$ ...
• 80.2k
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 ...
• 4,828

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(... • 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(... • 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-... • 5,067 -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) \ \...
• 5,067
\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(\...