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

Question

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?

Answer 1

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.

Answer 2

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.