Randomized Continuous Frames in Time-Frequency Analysis

Ron Levie, Haim Avron

Abstract

Recently, a Monte Carlo approach was proposed for processing highly redundant continuous frames. This paper presents and analyzes applications of this theory, focusing on the computational complexity which relies on the "linear volume discretizable" (LVD) property. We demonstrate that the continuous wavelet transform (CWT) and the localizing time-frequency transform (LTFT)—a 3D representation—are both LVD. Our analysis proves that signal processing with the LTFT maintains the same asymptotic complexity as the 2D short-time Fourier transform (STFT), effectively bypassing the curse of dimensionality.

Introduction

In signal processing, continuous frames such as the Short-Time Fourier Transform (STFT) or the Continuous Wavelet Transform (CWT) provide highly redundant representations that are invaluable for analysis. However, this redundancy often leads to significant computational overhead. Traditionally, these frames are discretized using a rigid grid in the time-frequency plane. As researchers seek more sophisticated representations—such as 3D spaces tracking time, frequency, and wave shape—the number of grid points required grows exponentially. This "curse of dimensionality" has historically limited the practical application of high-dimensional transforms.

This paper explores a randomized Monte Carlo-based approach to discretization. By utilizing the concept of Linear Volume Discretizable (LVD) frames, we show that it is possible to achieve efficient signal synthesis without the exponential cost typically associated with higher dimensions.

The Linear Volume Discretizable (LVD) Property

The core theoretical contribution of this work is the formalization of LVD frames. A frame is considered LVD if the volume of the phase space required to represent a signal with a specific accuracy is directly proportional to the signal's resolution ($M$).

In a Monte Carlo cubature approach, instead of a fixed grid, independent random samples are drawn from the phase space to approximate the integral required for signal synthesis. If a frame is LVD, the number of samples needed does not explode as the dimensionality of the transform increases. Instead, the complexity remains tied to the information content of the signal itself.

The Localizing Time-Frequency Transform (LTFT)

To demonstrate the power of the LVD framework, we introduce the Localizing Time-Frequency Transform (LTFT). The LTFT is a hybrid 3D representation that combines the strengths of the STFT and CWT:

  • STFT-like atoms are used for low and high frequencies.
  • CWT-like atoms are used for middle frequencies.
  • A third dimension is added to control the number of oscillations within the atoms.

This 3D structure allows the LTFT to better represent both transient events (like percussive hits) and sustained harmonic components simultaneously. In audio processing, this significantly reduces "phasiness"—the metallic artifacts often introduced during time-stretching or pitch-shifting.

Complexity and Performance

A primary result of our analysis is the proof that the LTFT, despite its 3D coefficient space, satisfies the LVD property. Consequently, performing signal processing with the LTFT has an asymptotic complexity of $O(M \log M)$, where $M$ is the signal length. This matches the efficiency of standard 2D transforms implemented via the Fast Fourier Transform (FFT).

Furthermore, we establish rigorous error bounds for the Monte Carlo approximation. The expected error relative to the signal energy is shown to be $O(Z^{-1}) + O(\epsilon^2)$, where $Z$ represents the number of samples and $\epsilon$ is the discretization error. We also derive a closed-form formula for the LTFT frame operator, confirming it as a stable and invertible filter.

Conclusion and Future Work

By proving that high-dimensional transforms like the LTFT are LVD, we provide a mathematical foundation for efficient, randomized signal processing. This approach allows for richer signal representations without the traditional computational penalties.

While this work focuses on the theoretical proofs for STFT, CWT, and LTFT, the framework is extensible. Future research may apply these Monte Carlo methods to other high-dimensional systems, such as Curvelets or Shearlets, which are critical in fields like seismic analysis and image processing. While the current study is primarily mathematical, the availability of the LTFT phase vocoder implementation demonstrates the practical viability of these theoretical insights.

Summary updated

Abstract

Recently, a Monte Carlo approach was proposed for processing highly redundant continuous frames. In this paper we present and analyze applications of this new theory. The computational complexity of the Monte Carlo method relies on the continuous frame being so called linear volume discretizable (LVD). The LVD property means that the number of samples in the coefficient space required by the Monte Carlo method is proportional to the resolution of the discrete signal. We show in this paper that the continuous wavelet transform (CWT) and the localizing time-frequency transform (LTFT) are LVD. The LTFT is a time-frequency representation based on a 3D time-frequency space with a richer class of time-frequency atoms than classical time-frequency transforms like the short time Fourier transform (STFT) and the CWT. Our analysis proves that performing signal processing with the LTFT has the same asymptotic complexity as signal processing with the STFT and CWT (based on FFT), even though the coefficient space of the LTFT is higher dimensional.
BibTeX
@inproceedings{levie2022randomized,
  author = {Ron Levie and Haim Avron},
  title = {{Randomized Continuous Frames in Time-Frequency Analysis}},
  booktitle = {Adv. Comput. Math},
  year = {2022},
  url = {https://openreview.net/forum?id=4LPGbY7LOZ},
}
Figure