(when I say satisfy the left hand side, I mean make the sum of shifted windows add up to a constant)
On Wed, Jun 24, 2020 at 12:37 PM Corey K <corey...@gmail.com> wrote: > 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