# Other time-frequency-plane tiling than STFT, DWT, ConstantQ-Transform: multiresolution STFT?

It is known that

• a) the STFT gives a rectangular tiling of the time-frequency plane

• b) the Wavelet transform gives a non-linear tiling (better frequency resolution for low-frequencies, and better time-domain resolution for higher-frequencies)

• c) Constant-Q transform (such as NonStationaryGaborTransform) have a logarithmic scale for frequency bins (instead of linear with STFT) and have a time-frequency tiling like this (y-axis logarithmic):

## Question:

Is there an transform like this:

i.e. like a normal STFT, but for which the FFT-size would change for successive time frames.

Example: if there is a transient, the FFT-size is small (512) to keep good time-domain resolution, then a few time-frames later the signal is rather stationary, so the FFT-size is higher (8192) to have good frequency resolution.

It's like an adaptative / multiresolution STFT.

Last but not least: of course it's always possible to perform FFT with different window-length on successive time-frames, so the forward transform I'm describing is probably easy to do.

What I'm asking here is a transform which is invertible, i.e. in which we can compute an inverse transform to recover the initial signal.

Does this exist in Matlab or Python?

• This might be part of a solution: ars.els-cdn.com/content/image/… : (d) a time-varying window (T-VW) STFT. But I don't have full access to this article: Non-Stationary Signal Analysis Time-Frequency Approach, and also I don't know if this T-VW-STFT is invertible... Sep 27 '18 at 10:14
• The transform is invertible given $N_{DFT}, b[k]$ where $b[k]$ are a set of harmonics that still covers the range $0..\frac{Fs}{2}$ but with varying density than keeping $b[k+1]-b[k]$ constant. So, you can "cut" that frequency domain in any way you like. The key problem is to generate the signal that decides on a given sampling strategy versus time. Do you have that signal?
– A_A
Sep 27 '18 at 14:41
• @A_A What is $N_{DFT},b[k]$? (maybe could you post an answer with these details?). I'm ok for a linear $b[k]$, i.e. in my picture example: in the first time-frame, there would be 1024 frequency bins. In the second time-frame, there would be 2048 bins, in the 3rd time-frame, 4096 bins, in the 4th time-frame 2048 again, etc. (time-varying window) Sep 27 '18 at 17:11
• @A_A Yes I do have such a signal to decide for on a given sampling strategy. For example, let's take a single note of glockenspiel. We would like a short window during the attack transient, a medium size window during the rest of the attack, and a long window (thus better freq resolution) during the sustain of the note, etc. Sep 27 '18 at 17:14
• I don't mean whether or not you have a signal to work with :) What I am talking about is having a(nother) signal to drive your choice of $N_{DFT}$.
– A_A
Sep 28 '18 at 10:22

## 2 Answers

Your time-frequency grid is Mondrian-shaped: essentially, rectangles supported on dyadic splits of the time or the frequency axes. Hence, you can easily start for any reversible time-frequency tiling, and further slit any of its rectangle onto another invertible tiling. Some call that hierarchical, or nested time-scale/time-frequency decompositions. As long as each is invertible, the combination remains revertible.

Furthermore, dyadic and power-of-two uniform decompositions can be turned into the other, only by grouping coefficients. This was used for instance in A DCT-based embedded image coder, 1996: an eight (or $$2^3$$) multiband filter-bank DCT was turned into a 3-level dyadic structure.

So, combining dyadic wavelets and $$2^K$$ windowed filter-bank, you can get invertible schemes as wished.

One issue though: how does one choose how to nest those different embedded decompositions? Seen as wavelet or local cosine, lapped-transform packets, entropy concepts could be used, but the diversity can be huge.

In a typical Discrete Fourier Transform (DFT):

$$X[k] = \sum_{n=0}^{N-1} x[n] \cdot e^{\frac{-j 2 \pi k n}{N}}, k \in [0 .. N_{DFT}-1]$$

Where $$N$$ is the length of $$x$$ and $$N_{DFT}$$ is the number of points of evaluation of the DFT sum. $$X[k]$$ is complex and represents the $$k^{th}$$ bin of the DFT. The natural frequency that is associated with $$k$$ is $$f(k) = k \frac{Fs}{N_{DFT}}$$. In that case every two successive values of $$f(k), f(k+1)$$ will have a constant "step" (this is what I refer to as $$b[k]$$ earlier as the $$k^{th}$$ bin).

When you apply this in the STFT way, all that you do is "re-indexing" the $$x[n]$$. The transform remains the same. All that changes is the "slice" of signal that you apply the transform to and the method by which you recombine these intermediate DFTs (I am referring here to overlap-add and overlap-save).

Now, there is nothing stopping you from using some $$N_{DFT}[u]$$ which would represent a different number of DFT points for each frame $$u$$ of the STFT.

You can transform some frame $$u$$ at $$N_{DFT}[u]=256$$ points and the next one at $$N_{DFT}[u+1]=1024$$.

The real question is what signal are you using to drive your choice of $$N_{DFT}[u]$$?.

Seen from a different point of view, this would be equivalent to varying the sampling frequency $$Fs$$ depending on "how interesting" the signal is at a given instance in time. For example, you may have a signal that is fairly constant for some time until suddenly it gets more complex and bendy. You don't need many sinusoids to describe a fairly constant signal but you do need lots of sinusoids to describe a more complex signal.

In computer graphics, sometimes you do this to describe complex objects (curves, surfaces). Have a look at this for example, where you can vary the space subdivision based on the sparsity of a dataset or when you go the other way, in curve simplification, where, you remove points from the curve as long as they don't distort it too much.

So, yes, there is nothing stopping you from doing what you describe but the real difficulty is in coming up with a metric that when applied locally, it tells you that the signal at that region is "more interesting" and (as Laurent Duval says) the choices there are too many and with different interpretations.

Hope this helps.

• the problem i have @A_A is exactly the 'overlap add' for reconstitution of the signal. with normal stft, you work on overlapping time-frames (usually 50% or 75%), you multiply each bit of signal by a window, typically hamming or another, and you do the fft, etc. and at the end, for the reconstitution of the signal, you sum all the small parts via 'overlap add'. the big question is: "how to do an overlapp-add when consecutive time frames have different lengths?". Example: 256 points, the next time-frame has 1024, the next has 512 points, etc. How to overlapp add this? Sep 28 '18 at 20:56
• @g6kxjv1ozn What is the problem with overlap add exactly? Why doesn't it work as expected? Can you write what is perceived as the problem? You can still work with fixed frame length but variable $N_{DFT}$. So what if consecutive frames have different lengths? You still "splice" together waveforms in the time domain. Is it the difference in overlap percentage? Do you get "switching" artifacts (flutter)?
– A_A
Sep 29 '18 at 8:28
• We don't work with fixed frame length, see last image in the question. That's why it's called a time-varying window (T-VW) STFT. If I want 2048 freq bins in the second time-frame, I need 2048 input samples for this time-frame, for the FFT. ($N$ samples in => FFT has $N$ frequency bins). What makes overlap-add work is that summing overlapping Hamming (or other) windows gives a constant function. So now if the windows don't have the same width, summing them won't give a constant... Sep 29 '18 at 17:38
• ... of course I could zero pad all time frames to have the required FFT size, but, as it's well known, this won't add resolution to the FFT. Sep 29 '18 at 17:39
• @g6kxjv1ozn The window's effect can be counteracted by applying an anti-window function. If $w[n]$ is the window, then multiplying by $\frac{1}{w[n]}$, brings the waveform levels back to 1 after processing and ready for the "add" part. This does not hold exactly for windows that drop their amplitude to zero but you lose those two samples anyway. What do you use to decide the $N_{DFT}$ for a given frame by the way?
– A_A
Sep 30 '18 at 23:18