1
$\begingroup$

In the literature on the short-time Fourier transform (STFT) it is often stated or implied that the constant overlap-add (COLA) constraint must be satisfied in order for the STFT to be invertible.

Example: https://ccrma.stanford.edu/~jos/sasp/FBS_Perfect_Reconstruction.html

People seem go to a lot of trouble to choose a window/overlap combination that satisfies COLA.

I'm challenging the community here to "change my view" that the COLA constraint is sufficient but not necessary. I contend that you can achieve perfect invertibility under much weaker conditions and so have access to a very broad range of windows and overlaps.

I've written this blog post to examine this question. I would love to know if I am missing something.

This script provides an example of a window that is not COLA compliant, but which creates an invertible STFT.

| improve this question | |
$\endgroup$
  • 1
    $\begingroup$ Interesting. I'd suggest showing a non-trivial example where COLA is not satisfied but you can still invert the STFT. $\endgroup$ – MBaz May 4 '18 at 22:58
  • $\begingroup$ Was does CMV mean, by the way? $\endgroup$ – Laurent Duval May 4 '18 at 23:23
  • $\begingroup$ @MBaz I've run dozens of examples like that. I'll post some code. $\endgroup$ – gauss256 May 5 '18 at 3:03
  • $\begingroup$ @Laurent Duval CMV = change my view. A reference to a Reddit subreddit that is probably not too helpful in this context! $\endgroup$ – gauss256 May 5 '18 at 3:04
  • 1
    $\begingroup$ You have ripped the original statement out of context. STFT is invertible using FBS exactly if the window is COLA. It's trivially obvious that other windows that do not vanish can be inverted by dividing by the window function explicitly. $\endgroup$ – Jazzmaniac May 5 '18 at 10:13
1
$\begingroup$

You just triggered one old itch, so this is a partial (both meanings) answer only. For discrete-time, uniformly sampled STFT, one often uses the usual fixed-window with $3/4$, $1/2$, $1/4$ overlaps, and somehow uses direct closed form inverses. However, as long as there is redundancy (and completeness), there exists a infinite option for inverses.

In a collaborative work (with Jean-Christophe Pesquet and Jérôme Gauthier), following other works on vector-frames, we used the formalism of complex oversampled multirate filter banks

to model analysis STFT, with the aims of

  • checking conditions under which the STFT were invertible, given a hop between time-frames,
  • building "better" inverses (better localized in time or frequency) with optimization.

Our aim at that time was double:

  • for data in higher dimensions $d$, reduce the STFT redundancy $r^d$ as far as we could, -for 1D data, reduce the number of channels and increase the hop as we could as similar quality for real-time event detection.

All was based on polyphase matices, as we did consider windowed transform only as a special case; so the main outcomes were the following:

  • given any redundant analysis filter bank (complex or not, windowed-DFT like or not), check whether it is invertible
  • in most cases, anything redundant is almost surely inversible,
  • windows with negative values can be used, liked Kaiser windows, see On the Optimization of Oversampled DFT Filter Banks, 2007 enter image description here
  • you can reduce the degrees of freedom in the oversampled synthesis to perform better concentrated inverses after selection/denoising for (close-to) real-time computations,
  • ensure the Hermitian character in the inverse for scalar threshold.

There were remaining issues, among which: the difficulty to go back to the orthogonal setting when the redundancy tends to one. Weirds behaviors were observed, possibly related to Farey sequences, but I have no definitive clue. And References can be found in Optimization of Synthesis Oversampled Complex Filter Banks, 2009. Some related codes is available at SURE-LET Optimal oversampled Complex Filter Banks synthesis toolbox. We do plan a better release, but it has been remaining upcoming for months.

However, we did not investigate the non-COLA effect, and the necessary condition is not stated. My belief is that it is not necessary (due to redundancy), but this should be proven.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ I think that the blog post I linked to in my question proves pretty conclusively that COLA is not necessary, under a wide variety of conditions. $\endgroup$ – gauss256 May 5 '18 at 3:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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