Regarding e.q 4.5 it is easy to satisfy the left hand side of that equation exactly (which is all that is needed) -- any COLA window will do it.
Steffan's point is critically important. The FFT has to be appropriately zero-padded so the convolution is linear rather than circular. But the end result is that we can perform filtering using STFT filterbanks just fine, there are no artifacts. On Wed, Jun 24, 2020 at 12:30 PM STEFFAN DIEDRICHSEN <sdiedrich...@me.com> wrote: > Here’s the beef from that paper: > > > (The reader should realize that an appropriate change > > must be made to the analysis-i.e., padding the windowed > in- put signal with a sufficient number of zero valued samples-to prevent > time aliasing when implementing the analysis and syn- thesis operations > with FFT's, which have length L . If a modification P(eJWk) has a time > response which is effectively No points long, the analysis length L must be > at least N +No - 1 where the window length is N.) > > That’s more or less describing the limits of that approach by using the > identity of spectral multiplication and time-domain convolution. For a > convolution of N input samples with M filter samples, the result is L= > N+M-1. So, if you use an FFT with size L, you can use M-1-L input samples. > So you need to zero-pad to avoid artefacts. > > Best, > > Steffan > > On 24.06.2020|KW26, at 16:10, Corey K <corey...@gmail.com> wrote: > > I think you're mistaken, unfortunately. Block FFT convolution has been > around for 30+ years. In 1977 (43 years ago now), Jont Allen showed in his > paper "A Unified Approach to Short-Time Fourier Analysis" how you can > perform FIR filtering perfectly with the FFT, of COLA windows are used. See > equation 5.2.5 in that paper, and the analysis that precedes it. > > > > > > On Wed, Jun 24, 2020 at 11:16 AM Zhiguang Eric Zhang <zez...@nyu.edu> > wrote: > >> that's not true. with FFT/COLA you will necessarily have the Gibbs >> phenomenon / ringing / ripple artifacts. certain window types will >> minimize this but you will get this phenomenon nonetheless. >> >> On Wed, Jun 24, 2020 at 9:44 AM Corey K <corey...@gmail.com> wrote: >> >>> I see what you're getting at, I suppose. However, in the context of FIR >>> filtering I wouldn't refer to this as an artifact. Let's say you gave me an >>> FIR filter with N-taps and asked me to write a program to implement that >>> filter. I could implement this using a direct form structure (in the >>> time-domain), or with the FFT using OLA. Both would give the exact same >>> results down to numerical precision, with no "artifacts". That's why it >>> intrigued me when you said "of course it won't have the ripple artifacts >>> associated with FFT overlap windowing" when referring to software that does >>> filtering. >>> >>> >>> On Wed, Jun 24, 2020 at 10:59 AM Zhiguang Eric Zhang <zez...@nyu.edu> >>> wrote: >>> >>>> ripple is just a known artifactual component of a windowing operation. >>>> it's also known as the Gibbs phenomenon >>>> >>>> http://matlab.izmiran.ru/help/toolbox/signal/filterd8.html >>>> <https://urldefense.proofpoint.com/v2/url?u=http-3A__matlab.izmiran.ru_help_toolbox_signal_filterd8.html&d=DwMFaQ&c=slrrB7dE8n7gBJbeO0g-IQ&r=w_CiiFx8eb9uUtrPcg7_DA&m=LVW8eOM2POVbM1MauwqppWYiBwmnAs5_i7qiMOEK0-o&s=XefFmTg_gx0qQrZnZTOJDTlaqMl3xt5WBzqxYAkoMKA&e=> >>>> >>>> i'm not referring to any equivalency between time/freq domain filtering >>>> >>>> >>>> On Wed, Jun 24, 2020 at 9:21 AM Corey K <corey...@gmail.com> wrote: >>>> >>>>> Not totally understanding you, unfortunately. But if what you are >>>>> describing is part of the normal filter response/ringing I guess I >>>>> wouldn't >>>>> refer to it as "artifacts"? FIR filtering can be performed equivalently in >>>>> the time or frequency domain. Do you disagree with that statement? >>>>> >>>>> On Wed, Jun 24, 2020 at 10:02 AM Zhiguang Eric Zhang <zez...@nyu.edu> >>>>> wrote: >>>>> >>>>>> yes but any windowing operation is akin to taking a dirac delta >>>>>> function on X number of samples and thus you will get ringing/ripple >>>>>> artifacts as a necessary part of the filter response >>>>>> >>>>>> On Wed, Jun 24, 2020 at 6:30 AM Corey K <corey...@gmail.com> wrote: >>>>>> >>>>>>> >>>>>>> of course it won't have the ripple artifacts associated with FFT >>>>>>>> overlap windowing >>>>>>>> >>>>>>> >>>>>>> What is the ripple artifact you are talking about? When using >>>>>>> constant overlap add (COLA) windows the STFT is a perfect reconstruction >>>>>>> filterbank. Likewise block FFT convolution can be used to implement any >>>>>>> FIR >>>>>>> filtering operation. >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>>> cheers, >>>>>>>> -ez >>>>>>>> >>>>>>>> On Mon, Apr 13, 2020 at 4:55 PM Andreas Gustafsson < >>>>>>>> g...@waxingwave.com> wrote: >>>>>>>> >>>>>>>>> Hello Spencer, >>>>>>>>> >>>>>>>>> You wrote: >>>>>>>>> > A while ago I read through some the literature [1] on >>>>>>>>> implementing >>>>>>>>> > an invertible CQT as a special case of the Nonstationary Gabor >>>>>>>>> > Transform. It's implemented by the essentia library [2] among >>>>>>>>> other >>>>>>>>> > places probably. >>>>>>>>> > >>>>>>>>> > The main idea is that you take the FFT of your whole signal, then >>>>>>>>> > apply the filter bank in the frequency domain (just >>>>>>>>> > multiplication). Then you IFFT each filtered signal, which gives >>>>>>>>> you >>>>>>>>> > the time-domain samples for each band of the filter bank. Each >>>>>>>>> > frequency-domain filter has a different bandwidth, so your IFFT >>>>>>>>> is a >>>>>>>>> > different length for each one, which gives you the different >>>>>>>>> sample >>>>>>>>> > rates for each one. >>>>>>>>> >>>>>>>>> That's the basic idea, but the Gaborator rounds up each of the >>>>>>>>> per-band sample rates to the original sample rate divided by some >>>>>>>>> power of two. This means all the FFT sizes can be powers of two, >>>>>>>>> which tend to be faster than arbitrary sizes. It also results in a >>>>>>>>> nicely regular time-frequency sampling grid where many of the >>>>>>>>> samples >>>>>>>>> coincide in time, as shown in the second plot on this page: >>>>>>>>> >>>>>>>>> >>>>>>>>> https://urldefense.proofpoint.com/v2/url?u=https-3A__www.gaborator.com_gaborator-2D1.4_doc_overview.html&d=DwICAg&c=slrrB7dE8n7gBJbeO0g-IQ&r=w_CiiFx8eb9uUtrPcg7_DA&m=4rIFY1X4fS1G8-882xM72jF9DvsY6-Z2ckeHxjPPfTY&s=FG-ZGfFa09T-Y7nLajB8evbCy9WIADFrUqPwjz-LHow&e= >>>>>>>>> >>>>>>>>> >>>>>>>>> Also, the Gaborator makes use of multirate processing where the >>>>>>>>> signal >>>>>>>>> is repeatedly decimated by 2 and the calculations for the lower >>>>>>>>> octaves run at successively lower sample rates. These >>>>>>>>> optimizations >>>>>>>>> help the Gaborator achieve a performance of millions of samples per >>>>>>>>> second per CPU core. >>>>>>>>> >>>>>>>>> > They also give an "online" version where you do >>>>>>>>> > the processing in chunks, but really for this to work I think >>>>>>>>> you'd >>>>>>>>> > need large-ish chunks so the latency would be pretty bad. >>>>>>>>> >>>>>>>>> The Gaborator also works in chunks. A typical chunk size might be >>>>>>>>> 8192 samples, but thanks to the multirate processing, in the lowest >>>>>>>>> frequency bands, each of those 8192 samples may represent the >>>>>>>>> low-frequency content of something like 1024 samples of the >>>>>>>>> original >>>>>>>>> signal. This gives an effective chunk size of some 8 million >>>>>>>>> samples >>>>>>>>> without actually having to perform any FFTs that large. >>>>>>>>> >>>>>>>>> Latency is certainly high, but I would not say it is a consequence >>>>>>>>> of >>>>>>>>> the chunk size as such. Rather, both the high latency and the need >>>>>>>>> for a large (effective) chunk size are consequences of the lengths >>>>>>>>> of >>>>>>>>> the band filter impulse responses, which get exponentially larger >>>>>>>>> as >>>>>>>>> the constant-Q bands get narrower towards lower frequencies. >>>>>>>>> >>>>>>>>> Latency in the Gaborator is discussed in more detail here: >>>>>>>>> >>>>>>>>> >>>>>>>>> https://urldefense.proofpoint.com/v2/url?u=https-3A__www.gaborator.com_gaborator-2D1.4_doc_realtime.html&d=DwICAg&c=slrrB7dE8n7gBJbeO0g-IQ&r=w_CiiFx8eb9uUtrPcg7_DA&m=4rIFY1X4fS1G8-882xM72jF9DvsY6-Z2ckeHxjPPfTY&s=uuRzi0taGcXI9Sq63G_xTTrCjaz9cu3ewu8jfzIUcVc&e= >>>>>>>>> >>>>>>>>> >>>>>>>>> > The whole process is in some ways dual to the usual STFT process, >>>>>>>>> > where we first window and then FFT. in the NSGT you first FFT and >>>>>>>>> > then window, and then IFFT each band to get a Time-Frequency >>>>>>>>> > representation. >>>>>>>>> >>>>>>>>> Yes. >>>>>>>>> >>>>>>>>> > For resynthesis you end up with a similar window overlap >>>>>>>>> constraint >>>>>>>>> > as in STFT, except now the windows are in the frequency domain. >>>>>>>>> It's >>>>>>>>> > a little more complicated because the window centers aren't >>>>>>>>> > evenly-spaced, so creating COLA windows is complicated. There are >>>>>>>>> > some fancier approaches to designing a set of synthesis windows >>>>>>>>> that >>>>>>>>> > are complementary (inverse) of the analysis windows, which is >>>>>>>>> what >>>>>>>>> > the frame-theory folks like that Austrian group seem to like to >>>>>>>>> use. >>>>>>>>> >>>>>>>>> The Gaborator was inspired by the papers from that Austrian group >>>>>>>>> and >>>>>>>>> uses complementary resynthesis windows, or "duals" as frame >>>>>>>>> theorists >>>>>>>>> like to call them. The analysis windows are Gaussian, and the dual >>>>>>>>> windows used for resynthesis end up being slightly distorted >>>>>>>>> Gaussians. >>>>>>>>> >>>>>>>>> > One of the nice things about the NSGT is it lets you be really >>>>>>>>> > flexible in your filterbank design while still giving you >>>>>>>>> > invertibility. >>>>>>>>> >>>>>>>>> Agreed. >>>>>>>>> >>>>>>>>> In a later message, you wrote: >>>>>>>>> > Whoops, just clicked through to the documentation and it looks >>>>>>>>> like >>>>>>>>> > this is the track you're on also. I'm curious if you have any >>>>>>>>> > insight into the window-selection for the analysis and synthesis >>>>>>>>> > process. It seems like the NSGT framework forces you to be a bit >>>>>>>>> > smarter with windows than just sticking to COLA, but the dual >>>>>>>>> frame >>>>>>>>> > techniques should apply for regular STFT processing, right? >>>>>>>>> >>>>>>>>> I'm actually not that familiar with traditional STFTs and COLA, >>>>>>>>> but as >>>>>>>>> far as I can tell, the STFT is a special case of the NSGT and the >>>>>>>>> same >>>>>>>>> dual frame techniques should apply. >>>>>>>>> -- >>>>>>>>> Andreas Gustafsson, g...@waxingwave.com >>>>>>>>> _______________________________________________ >>>>>>>>> dupswapdrop: music-dsp mailing list >>>>>>>>> music-dsp@music.columbia.edu >>>>>>>>> >>>>>>>>> https://urldefense.proofpoint.com/v2/url?u=https-3A__lists.columbia.edu_mailman_listinfo_music-2Ddsp&d=DwICAg&c=slrrB7dE8n7gBJbeO0g-IQ&r=w_CiiFx8eb9uUtrPcg7_DA&m=4rIFY1X4fS1G8-882xM72jF9DvsY6-Z2ckeHxjPPfTY&s=br6gIADk3PB9_kF8YoA7aZdcf5McFvCCOlyYso5D2BI&e= >>>>>>>>> >>>>>>>>> >>>>>>>> _______________________________________________ >>>>>>>> dupswapdrop: music-dsp mailing list >>>>>>>> music-dsp@music.columbia.edu >>>>>>>> https://lists.columbia.edu/mailman/listinfo/music-dsp >>>>>>>> <https://urldefense.proofpoint.com/v2/url?u=https-3A__lists.columbia.edu_mailman_listinfo_music-2Ddsp&d=DwMFaQ&c=slrrB7dE8n7gBJbeO0g-IQ&r=w_CiiFx8eb9uUtrPcg7_DA&m=0Zfr9NX2z_qbqorZ4mvWlKWdhvCOnws4tZKFE3J0lxI&s=_0-DUAEnNzJ0nyrUgGHozY0ob4n_-0OWpipEf-p2Bps&e=> >>>>>>> >>>>>>> _______________________________________________ >>>>>>> dupswapdrop: music-dsp mailing list >>>>>>> music-dsp@music.columbia.edu >>>>>>> >>>>>>> https://urldefense.proofpoint.com/v2/url?u=https-3A__lists.columbia.edu_mailman_listinfo_music-2Ddsp&d=DwICAg&c=slrrB7dE8n7gBJbeO0g-IQ&r=w_CiiFx8eb9uUtrPcg7_DA&m=0Zfr9NX2z_qbqorZ4mvWlKWdhvCOnws4tZKFE3J0lxI&s=_0-DUAEnNzJ0nyrUgGHozY0ob4n_-0OWpipEf-p2Bps&e= >>>>>> >>>>>> _______________________________________________ >>>>>> dupswapdrop: music-dsp mailing list >>>>>> music-dsp@music.columbia.edu >>>>>> https://lists.columbia.edu/mailman/listinfo/music-dsp >>>>>> <https://urldefense.proofpoint.com/v2/url?u=https-3A__lists.columbia.edu_mailman_listinfo_music-2Ddsp&d=DwMFaQ&c=slrrB7dE8n7gBJbeO0g-IQ&r=w_CiiFx8eb9uUtrPcg7_DA&m=ggIGGD37NXAIrRak00WIRysmpvCxdGGCHkoma2TGgxc&s=2aCxaadCSRm8GtUxELE7DhnWmqkKUkkAymUl19tD-v4&e=> >>>>> >>>>> _______________________________________________ >>>>> dupswapdrop: music-dsp mailing list >>>>> music-dsp@music.columbia.edu >>>>> >>>>> https://urldefense.proofpoint.com/v2/url?u=https-3A__lists.columbia.edu_mailman_listinfo_music-2Ddsp&d=DwICAg&c=slrrB7dE8n7gBJbeO0g-IQ&r=w_CiiFx8eb9uUtrPcg7_DA&m=ggIGGD37NXAIrRak00WIRysmpvCxdGGCHkoma2TGgxc&s=2aCxaadCSRm8GtUxELE7DhnWmqkKUkkAymUl19tD-v4&e= >>>> >>>> _______________________________________________ >>>> dupswapdrop: music-dsp mailing list >>>> music-dsp@music.columbia.edu >>>> https://lists.columbia.edu/mailman/listinfo/music-dsp >>>> <https://urldefense.proofpoint.com/v2/url?u=https-3A__lists.columbia.edu_mailman_listinfo_music-2Ddsp&d=DwMFaQ&c=slrrB7dE8n7gBJbeO0g-IQ&r=w_CiiFx8eb9uUtrPcg7_DA&m=LVW8eOM2POVbM1MauwqppWYiBwmnAs5_i7qiMOEK0-o&s=Wiyf_pAPkjR4_Ox3pi0vTvCNZDjINUsf0bfxVKpiGW8&e=> >>> >>> _______________________________________________ >>> dupswapdrop: music-dsp mailing list >>> music-dsp@music.columbia.edu >>> >>> https://urldefense.proofpoint.com/v2/url?u=https-3A__lists.columbia.edu_mailman_listinfo_music-2Ddsp&d=DwICAg&c=slrrB7dE8n7gBJbeO0g-IQ&r=w_CiiFx8eb9uUtrPcg7_DA&m=LVW8eOM2POVbM1MauwqppWYiBwmnAs5_i7qiMOEK0-o&s=Wiyf_pAPkjR4_Ox3pi0vTvCNZDjINUsf0bfxVKpiGW8&e= >> >> _______________________________________________ >> dupswapdrop: music-dsp mailing list >> music-dsp@music.columbia.edu >> https://lists.columbia.edu/mailman/listinfo/music-dsp > > > > _______________________________________________ > dupswapdrop: music-dsp mailing list > music-dsp@music.columbia.edu > https://lists.columbia.edu/mailman/listinfo/music-dsp
_______________________________________________ dupswapdrop: music-dsp mailing list music-dsp@music.columbia.edu https://lists.columbia.edu/mailman/listinfo/music-dsp
