3
$\begingroup$

there are many situations when one has to carry some operations on spectra, like splitting a spectrum Z wide in two Z/2 spectra, or vice versa merging two Z sized spectra in a 2Z sized one. The only solution without having to go back to time domain and then to freq domain again (which is stupid imho) is operating convolution in frequency domain.

One example: I have two Z sized spectra representing, respectively, a STFT signal frame and an impulse response, which were NOT zero padded to start from; I want to convolve them non-circularly so I have to transform both spectra to double size spectra, zero padded and left justified; I have therefore to expand both spectra to 2Z sized ones by simply doubling the bin positions leaving the odd ones empty (resulting in a 2Z spectrum representing a repeating copy of the signal in the 2nd half); convolve with a Dirichlet kernel representing a binay square wave of unitary frequency (here is the point), so to zero the second half; then I can multiply the two 2Z sized spectra to obtain linear convolution; then carry the inverse operations to split the result in two spectra of size Z for subsequent overlap-save. This is a total of four convolutions in frequency domain.

I anticipate the answers: why not simply acquire zero padded frames of proper size at the origin? Well let's assume that I can't for many reasons. One is that I am working in a STFT context already adopting a standard frame format, like non-zero padded frames, where I get frames of a given format and am expected to return frames of the same size and format as result of my processing.

OTOH, if I avoided the frequency domain convolutions I would have to do IFFT on both spectra, zero pad in time domain, FFT again for multiplying the spectra, IFFT for splitting the result and then FFT again, for a total of seven fourier transforms, which is perhaps even more stupid...

So I am asking whether some math tricks exist to carry such operations with spectra as zero padding and splitting or any trick to speedup convolution in frequency domain without having to go back to time domain. Thanks

Improve this question
$\endgroup$
6
  • $\begingroup$ Your question is very unclear to me. Why not formulate? use math to explain yourself. fro example, you have an STFT matrix $x\in\mathbb{C}^{F\times T}$ ($F$ frequency bins and $T$ time frames) $\endgroup$
    – havakok
    Jan 14, 2020 at 19:59
  • 1
    $\begingroup$ I agree with havokok—- could you possibly show an example step by step with each process you are describing - what the final result is and how your approach gets you there? I think that will make it clearer to see if there is anything simpler. With just text as you describe it, it is very hard to follow. I get that you are upsampling the frequency domain and interpolating prior to doing multiplication in order to represent convolution in the time domain; it’s possible all your steps are not necessary and would be easier to see that if you show your example and math. $\endgroup$
    – Dan Boschen
    Jan 14, 2020 at 21:24
  • $\begingroup$ @elena Not sure yet if this is less processing without seeing the example, but your your approach in the OTOH paragraph-- did you consider IFFT of both spectra, zero pad, convolve in time, split the result and then FFT? $\endgroup$
    – Dan Boschen
    Jan 14, 2020 at 23:34
  • $\begingroup$ Unfortunately I am a coder and quite skilled one but not a mathematic guru, so I really lack the basis to explain in a more formal way, I apologize for that, even if I hoped that my explanation of the problem was clear enough without resorting to complex formulas. My point in short was that I wanted to know whethere there were any math shortcuts to operate zero padding in frequency domain without either using cpu intensive convolutions in frequency domains or switching to time domain and back to frequency domain, which seems stupid to me... $\endgroup$
    – elena
    Jan 15, 2020 at 14:16
  • $\begingroup$ @elena got it. Could you at least put the example showing what you are doing step by step with actual samples and the result you are getting that is the result you want? Even though switching domains seems “stupid” to you, the point is that processing overall is often simpler by doing that specially- so that may be the case here. With the actual data and a step by step showing your results that will be easier for others to see and to help you. $\endgroup$
    – Dan Boschen
    Jan 15, 2020 at 14:56

1 Answer 1

Reset to default
2
$\begingroup$

It looks like your choice is based on whether (approx) 5*NLogN (IFFTs+FFTs) is greater or lesser than N^2 (linear convolution).

You could use coarser interpolation methods (cubic, spline, etc.) to upsample the spectra but the error would likely be audible as a clear loss in quality.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.