Convex Optimization approach to signals with fast varying instantaneous frequency

Matthieu Kowalski, Adrien Meynard, Hau‐Tieng Wu

TL;DR

This paper introduces Tycoon (Time-frequency bY COnvex OptimizatioN), a new framework for analyzing signals with rapidly changing frequencies. By reframing time-frequency analysis as a convex optimization problem rather than a standard transform, the authors successfully extract clear features from complex, "chirpy" signals that traditional methods like the Fourier Transform or Synchrosqueezing often blur.

What Problem Does This Paper Address?

In signal processing, we often want to know how the frequency of a signal changes over time (think of a bird's song or a fluctuating heartbeat). Traditional tools like the Short-Time Fourier Transform (STFT) are limited by the Heisenberg uncertainty principle: you can have good time resolution or good frequency resolution, but not both.

While newer techniques like Synchrosqueezing (SST) help "sharpen" these representations, they struggle when the frequency changes very quickly—a phenomenon known as having a high "chirp factor." Existing methods often produce blurred results or artificial "ghost" components when faced with these fast-varying signals. This paper seeks to bridge that gap by creating a mathematical model that explicitly accounts for these rapid changes.

Methods

The authors propose a novel algorithm called Tycoon. Instead of applying a fixed mathematical transform, Tycoon finds the "ideal" time-frequency representation (TFR) by solving an optimization problem.

  1. The Adaptive Harmonic Model: They define a new class of signals called "Generalized Intrinsic Mode type Functions" (gIMT), which allows for more aggressive fluctuations in both amplitude and frequency than previous models.
  2. The Functional: They design a cost function (a functional) to minimize. This function balances three things:
  3. Data Fidelity: The TFR must be able to reconstruct the original signal.
  4. Continuity/Flow: It uses an auxiliary function ($G$) to capture the "chirp factor," ensuring the frequency tracks smoothly even when it's changing fast.
  5. Sparsity: It applies an $L_1$ penalty to ensure the resulting time-frequency map is "sharp" and not a blurry mess.
  6. The Solver: To solve this complex minimization problem efficiently, they use the Fast Iterative Shrinkage-Thresholding Algorithm (FISTA), a popular tool in convex optimization known for its balance of speed and accuracy.

Datasets

The paper evaluates Tycoon using a mix of synthetic and "semi-real" data:

  • Semi-real Atrial Fibrillation (Af) Data: The authors took real heart rate intervals from a patient with Atrial Fibrillation (where heartbeats are "irregularly irregular") and used that timing to generate a synthetic oscillatory signal. This provides a realistic test case for fast-varying frequencies.
  • Synthetic Multi-component Signals: They created signals with two distinct components—one slow-varying and one fast-varying—to test the algorithm's ability to decompose overlapping features.
  • Noisy Benchmarks: They added Gaussian white noise to these signals to test the algorithm's robustness.

Key Insights and Ideas

  • Optimization over Transformation: The biggest "aha" moment is treating time-frequency analysis as a search for the best representation that fits specific physical constraints, rather than just running a pre-defined formula.
  • Capturing the "Chirp": By introducing an auxiliary variable to represent the local "chirp factor," the algorithm can "lean into" the frequency changes rather than being confused by them.
  • Preserving Causality: Unlike some reassignment methods that move data points around in ways that break the time-flow, Tycoon’s formulation can be adapted for real-time applications because it respects the relationship between time and frequency derivatives.

Key Results

  • Visual Clarity: In head-to-head visual comparisons, Tycoon produced much sharper "ridges" for fast-varying signals compared to STFT, SST, and Empirical Mode Decomposition (EMD).
  • Statistical Superiority: The authors used the Optimal Transport (OT) distance (also known as Earth Mover's Distance) to quantify how close their results were to the "ground truth" ideal representation. Tycoon consistently achieved lower error scores than competing methods.
  • Robustness: Even at a Signal-to-Noise Ratio (SNR) of 7.25, Tycoon successfully extracted the underlying frequency patterns where other methods began to fail or produce significant artifacts.

Limitations and Future Work

Despite its accuracy, Tycoon has one major drawback: Computational Cost.

  • Speed: The authors note that it takes about 3 minutes to analyze a signal with only 512 data points on a standard laptop. For modern datasets with millions of points, this is currently impractical.
  • Parameter Tuning: The algorithm relies on several hyperparameters ($\mu, \lambda, \gamma$). While the results aren't overly sensitive to them, there isn't yet a "set-it-and-forget-it" way to choose the optimal values for a brand-new signal.

Future Directions: The authors suggest moving toward a "sliding window" optimization approach to handle longer signals and investigating automated ways to select the best parameters.

Summary updated

Abstract

Motivated by the limitation of analyzing oscillatory signals composed of multiple components with fast-varying instantaneous frequency, we approach the time-frequency analysis problem by optimization. Based on the proposed adaptive harmonic model, the time-frequency representation of a signal is obtained by directly minimizing a functional, which involves few properties an "ideal time-frequency representation" should satisfy, for example, the signal reconstruction and concentrative time frequency representation. FISTA (Fast Iterative Shrinkage-Thresholding Algorithm) is applied to achieve an efficient numerical approximation of the functional. We coin the algorithm as {\it Time-frequency bY COnvex OptimizatioN} (Tycoon). The numerical results confirm the potential of the Tycoon algorithm.
BibTeX
@inproceedings{kowalski2016convex,
  author = {Matthieu Kowalski and Adrien Meynard and Hau‐Tieng Wu},
  title = {{Convex Optimization approach to signals with fast varying instantaneous frequency}},
  booktitle = {Applied and Computational Harmonic Analysis},
  year = {2016},
  doi = {10.1016/j.acha.2016.03.008},
}
Figure