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 ...


4

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 ...


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

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

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

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

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

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

The traditional overlap-add technique cannot be used as is in musical applications (reverberation) where latency is critical. It is a common practice to break down the impulse response into non-uniform chunks, and to run in parallel different convolvers for each segment of the impulse response - some of them being naive FIR implementations (for the short ...


2

The main alternative that I can think of is the hybrid method proposed by Bill Gardner and patented by Lake DSP (now part of Dolby). There appears to be a copy of Gardner's paper here.


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

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

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 ...


1

Knowing the order of magnitude of the data you are dealing with is a good start to troubleshooting your problem because it might be something to do with other things around your implementation of overlap add or save (OA,OS). OA, OS will work for even the weakest of CPUs. It might appear to take ages but it will not fail in a "hard way". By "hard way" here, ...


1

Quadratic time convolution to get a DFT result is usually less accurate (can incur more finite quantization numerical noise, due to a deeper layering of arithmetic steps) than the typical FFT algorithm when using the same arithmetic types and operation units. You might want to try higher precision data types (quad precision or bignum arithmetic).


1

You seem to be aware of the Fourier Transform pair that relates a sinc function in the time domain to a rectangle function in the frequency domain, but you don't seem to be able to correctly apply this to your situation. I am going to take one more stab at answering you. Let me know if you have questions. A sinc filter can be designed using the relationship ...


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