12

There is probably a bit of a misconception here. In many application the signal is runnning all the time or is VERY long: modem, audio stream, video etc. In this case you can't really define the "length" of the signal. The relevant metric is here "number of operations per input sample" not the "total number of operations". If ...


5

Disclaimer: I know this topic is older, but if one is looking for "fast accurate convolution high dynamic range" or similar this is one of the first of only a few decent results. I wanna share my insights I got on this topic so it might help somebody in the future. I apologize if I might use the wrong terms in my answer, but everything I found on this topic ...


5

I think you need to refine your definitions. The computational complexity for an $n$-element convolution on $m$ points of data is $\mathcal{O}(n\cdot m)$. Your $\mathcal{O}(n)$ only applies for each output sample. The computational complexity for an $n$-element FFT is, indeed $\mathcal{O}(n \log n)$. But it coughs up $n$ points. The savings in using the ...


4

In your case, since you have multiple images while you have a given set of kernels the DFT based Correlation would be the best fit. Pay attention that the DFT Based Convolution / Correlation Is Equivalent to Convolution / Correlation with Periodic / Circular Boundary Conditions. It means that if you need different boundary conditions (Like padding with ...


3

Google "overlap add". Quick outline zero pad filter to 256 taps, do an FFT Initialize and "overlap" buffer of length 128 taps to all zeros Initialize an input pointer to 0 Loop starts here Take 128 samples from your input starting at input pointer. Zero pad to 256, FFT Multiply the FFTs Inverse FFT, add overlap buffer to the first 128 samples, output these ...


3

I do a lot of decimation in the frequency domain. Little details are important. I assume you already know the basic rules for fast convolution: the FFT length N is equal to the data blocksize L plus the length of the filter impulse response M minus 1. Each operation uses L samples of new data plus M-1 samples of data from the old block. Ensure that the ...


3

Lets put forward the intuition behind the concept of the group delay before further discussing how to find the delay of FIR filters. Consider an input signal $x[n]$ of length $L_x$ which is nonzero between $n=0$ and $n=L_x-1$. And let a simplistic filter impulse response to be $h[n] = \delta[n-d]$. The output is immediately shown to be $y[n] = x[n-d]$ which ...


3

One candidate is the Karatsuba algorithm, which runs in $O\big(N^{\log_23}\big) \approx O\big(N^{1.5849625}\big)$ time. It's not transform-based. There's also some code with an explanation in the Music-DSP Source Code Archive, which looks like an independent discovery of a similar algorithm. Testing a Python implementation of the Karatsuba algorithm (...


3

Rather than scrapping the fast convolution algorithm, why not use an FFT with a higher dynamic range? An answer to this question shows how to use the Eigen FFT library with boost multiprecision.


3

you can split up your long impulse response into smaller segments and use multiple concurrent fast-convolutions that convolve each segment against your audio, align the delays correctly, and add up the result. what must be the case for each segment (or one big segment if you don't split it up) is that if the FFT length is $N$ and the impulse response (or ...


3

IDFT the smaller or both of the DFTs if needed. Zero pad one or both of the kernel and image to make them the same dimension and size. Re-DFT as needed, and now you can complex multiply the 2 DFT arrays element-by-element because they will now be the same size.


3

You need to know the length of the impulse response of your bandpass filter, and use an FFT longer than 256 by that length (to prevent circular convolution boundary artifacts). Combine the longer FFT results back into a sequence of length 256 windows by overlap-add or overlap-save.


3

FFT convolution is certainly scalable, but what you really ask is if it's faster when one of inputs is small (<1000) or input lengths differ greatly. Then indeed FFT convolution can be slower, as it must first pad both inputs to at least sum of their lengths minus 1. Note: answer only addresses 'direct' FFT convolution and linear convolution; ...


2

Zero-padding is one domain is equivalent to Sinc (or Dirichlet) convolution in the other, which is O(n^2), so that won't save you. For less computation, you might want to try different filter design methods (compositing existing FIR filters, IIRs, etc.) or finding a way to recompute your filter less often.


2

An FFT of twice the filter order is kind of short. Take a look at the "Choice of FFT size" section from this article I wrote a while back. Also your whole signal will fit into a reasonable size FFT, so I think the single FFT approach is fine in this case.


2

I'm actually in a discussion with Bill Gardner about this at this very moment (or month). I gave him a pdf document that outlined my thoughts. I wish I could effortlessly translate this to $\LaTeX$. Well nothing is effortless. Let's remember that Bill's algorithm is about doing low-latency convolution reverb, using fast-convolution (like overlap-save or ...


2

The task is to compute the DFT of a sequence from the DFTs of its two halves: $$X[k]=\text{DFT}_N\{x[n]\}=\sum_{n=0}^{N-1}x[n]e^{-j2\pi nk/N}$$ $$\begin{align}x_1[n]&=x[n],\quad n=0,\ldots,N/2-1\\x_2[n]&=x[n],\quad n=N/2,\ldots,N-1\end{align}$$ $$X_1[k]=\text{DFT}_{N/2}\{x_1[n]\},\quad X_2[k]=\text{DFT}_{N/2}\{x_2[n]\}$$ i.e., compute $X[k]$ from $...


2

And as it is well known, the computational complexity is $\mathcal{O}(N^2)$ and $\mathcal{O}(N \log N)$ for them respectively. $\mathcal{O}$ notation ignores any constants that determine exactly how fast those functions run. Depending on the constants out front, it may be faster to compute the convolution (or correlation) directly. For example, the ...


2

This is an insightful question, one that I remember pondering in the 1980s when I first learned of the Overlap-Add (OLA) and Overlap-Save (OLS, sometimes called Overlap-Scrap) methods of "fast convolution". It turns out that for strict LTI filtering, that you need not window with a Hann, but you could if you wanted to, and for a general frequency-domain ...


2

I figured out my problem. The kernel needs to be shifted so the 'center' is on the corner of the image (which acts as the origin in an FFT). The built-in ifftshift function works just fine for this. (Note, there are some subtleties here depending on whether you have even or odd shapes or differences in shape that can result in one row or column shifts. I ...


2

The variable NI in the book is just a typo, it should be N instead (not N*L as in your code). Apart from that, remember that book was written about $25$ years ago, and the code was run on a $33$ MHz $486$ PC. So in order to see some effects on today's computers, you should crank up the value of L. I've modified the code a bit (see below). Now the figure ...


2

The direct convolution approach has a complexity proportional to $n^2$ The FFT based approach has complexity $n \log(n)$. Since there are unknown pre-factors and the complexity only holds asymptotically, the only thing one can infer from the complexities is that only for large enough $n$ the FFT approach becomes more efficient. The $n=500$ threshold is thus ...


2

what role if any does windowing (e.g. Blackman, Hanning etc.) play None. If you do apply a window (other than rectangular) for a regular overlap add/save algorithm, your results will be wrong. Time domain windowing can be helpful if your frequency domain processing is time variant, but that requires more complicated algorithm with partially overlapping and ...


2

It pretty much doesn’t. One could say a boxcar window is used, but you most likely won’t hear any mention it. The trick with doing FFT convolution is making sure your FFT length is at least equal to the number of signal samples plus the impulse response length minus one. Both your input signal and impulse response need to be padded with zeros appended to the ...


2

You should read the documentation for the function you’re using: n: int, optional If n is negative (default), then the input is assumed to be the result of a complex fft. If n is larger than or equal to zero, the input is assumed to be the result of a real fft, and n gives the length of the array before transformation along the real transform direction. ...


1

This is typically done using a segmented overlap add method or sometimes also refered to as a block convolver. Let's assume your block size if 512 (makes the numbers a little easier). Chop up your impulse response into 32 blocks of 512 samples each. Zero pad each block to 1024 samples and FFT. You know have 32 filters $H_0(z) ... H_{31}(z)$ On each new ...


1

You have a bunch of options here You can zero pad both impulse response and signal to 16k, FFT and multiply. That's very inefficient though. Keep in mind that the sum of length of filter and signal need to be equal or smaller then the FFT size, hence an 8k FFT doesn't work. This gets a little better if you can truncate the 8k impulse response down to 7.5k. ...


Only top voted, non community-wiki answers of a minimum length are eligible