PaperlayerView exact revision on arXiv

Source-linked AI summary

Data-Driven Time-Frequency Analysis

Thomas Y. hou, Zuoqiang Shi

arXiv:1202.5621v1math.NA

TL;DR

Nonlinear and nonstationary signals challenge methods built on predetermined bases, motivating adaptive sparse representations in unknown multiscale bases. The paper introduces a nonlinear matching pursuit over an intrinsic-mode-function dictionary, showing efficient, noise-stable decomposition and extensions to difficult sampling and modulation settings. Under scale separation, its iterative algorithm converges to an approximate decomposition with accuracy determined by the scale-separation factor.

  • Problem

    Nonlinear and nonstationary data require adaptive analysis because useful sparse multiscale representations use bases that are unknown a priori.

  • Method

    The method searches for the sparsest representation in a large intrinsic-mode-function dictionary and solves the resulting nonlinear L0 problem with nonlinear matching pursuit.

  • Results

    Under certain scale-separation conditions, the iterative algorithm converges to an approximate decomposition whose accuracy is determined by the signal’s scale-separation factor.

  • Takeaways & Limitations

    The method provides efficient, noise-stable analysis and extends to data without scale separation, intra-wave modulation, missing intervals, and under-sampling.

  • Takeaways & Limitations

    Theoretical convergence results are established under scale-separation conditions, while further theoretical study is planned for incomplete or sparse samples.

Abstract

from arXiv · show

In this paper, we introduce a new adaptive data analysis method to study trend and instantaneous frequency of nonlinear and non-stationary data. This method is inspired by the Empirical Mode Decomposition method (EMD) and the recently developed compressed (compressive) sensing theory. The main idea is to look for the sparsest representation of multiscale data within the largest possible dictionary consisting of intrinsic mode functions of the form $\{a(t) \cos(θ(t))\}$, where $a \in V(θ)$, $V(θ)$ consists of the functions smoother than $\cos(θ(t))$ and $θ'\ge 0$. This problem can be formulated as a nonlinear $L^0$ optimization problem. In order to solve this optimization problem, we propose a nonlinear matching pursuit method by generalizing the classical matching pursuit for the $L^0$ optimization problem. One important advantage of this nonlinear matching pursuit method is it can be implemented very efficiently and is very stable to noise. Further, we provide a convergence analysis of our nonlinear matching pursuit method under certain scale separation assumptions. Extensive numerical examples will be given to demonstrate the robustness of our method and comparison will be made with the EMD/EEMD method. We also apply our method to study data without scale separation, data with intra-wave frequency modulation, and data with incomplete or under-sampled data.

1 Introduction

The paper develops an adaptive time-frequency method for nonlinear and nonstationary data by seeking sparse representations in a data-adapted dictionary of intrinsic mode functions. A nonlinear matching pursuit makes this optimization practical, robust to noise, and applicable across several challenging signal settings.

  • Traditional Fourier methods use predetermined bases suited to linear and stationary data, limiting their application to nonlinear and nonstationary signals.
  • The method seeks the sparsest decomposition over a large, data-driven dictionary of intrinsic mode functions to reveal trend and instantaneous frequency.
  • The nonlinear optimization is solved with a nonlinear matching pursuit inspired by classical matching pursuit and compressed sensing.
  • The method is stable to noise and efficiently implemented, with O(N log N) complexity when γ = 0 using the Fast Fourier Transform.
  • Experiments show comparable noise-free performance to EMD and better performance than EMD/EEMD under significant noise, while reducing sensitivity to end effects under scale separation.
  • Extensions address data without scale separation, strong intra-wave modulation, missing intervals, and under-sampling.

2 Brief review of the existing sparse decomposition methods

The review introduces standard sparse-decomposition dictionaries and methods, then motivates an adaptive EMD-based dictionary for selecting sparse signal representations. It contrasts matching pursuit, basis pursuit, and related approaches in computational cost, uniqueness, and noise sensitivity.

  • Sparse representation methods decompose signals using a dictionary and select a sparse combination of its atoms.
  • Fourier, wavelet, Gabor, and EMD dictionaries encode different waveform structures, including sinusoidal, localized, time-frequency, and intrinsic-mode-function atoms.
  • A more redundant dictionary can improve adaptivity and sparsity, but highly redundant dictionaries may produce nonunique decompositions requiring a selection criterion.
  • Matching pursuit iteratively selects the atom that best matches the residual and builds an approximate sparse representation from a few atoms.
  • Basis pursuit seeks a sparse representation by minimizing the l1 norm of its coefficient vector, with exact l0 recovery possible under some conditions.
  • The reviewed EMD-related method shares important EMD properties and avoids dependence on numerical parameters such as sifting count and stopping criteria.
  • Compared with the reviewed TV-based approach, nonlinear matching pursuit is described as less sensitive to noise and less computationally costly.

3 Sparse time-frequency decomposition method based on nonlinear matching pursuit

The method constructs a large, data-adaptive dictionary of intrinsic mode functions and seeks the sparsest signal decomposition through nonlinear matching pursuit. It combines l1-regularized fitting, residual updates, and specialized FFT-based procedures for periodic data, with safeguards for initialization, noise, and nonperiodic signals.

  • Dictionary and sparse decomposition: The method builds a large dictionary of intrinsic mode functions and seeks the sparsest decomposition by solving a nonlinear optimization problem.The dictionary contains functions a(t) cos θ(t), with θ′(t) ≥ 0 and amplitudes drawn from spaces smoother than cos θ(t).
  • Dictionary and sparse decomposition: For noisy signals, the residual constraint is relaxed using the noise level, yielding a nonlinear L0 minimization problem.The optimization minimizes the number of dictionary elements while constraining reconstruction error by δ.
  • Nonlinear matching pursuit: Nonlinear matching pursuit repeatedly fits one intrinsic mode function, subtracts it from the residual, and continues until the residual norm is below a stopping threshold.Each iteration solves an l1-regularized nonlinear least-square problem, updates the residual, and tests ∥r_k∥_l2 against ε0.
  • Nonlinear matching pursuit: The l1 regularization stabilizes least-square fitting with an overcomplete Fourier basis and favors sparse decompositions.The standard Fourier basis is orthogonal, so the l1 term is unnecessary in that special case.
  • FFT-based periodic algorithm: For periodic data, an FFT-based solver replaces the more expensive l1-regularized least-square step by filtering in the phase coordinate.The algorithm interpolates the residual in θ-coordinates, applies a low-pass filter to its Fourier transform, maps the estimates back to t, and updates instantaneous frequency.
  • Stabilization and scope: The algorithm uses continuation from restricted phase-update spaces and thresholded interpolation to reduce sensitivity to initialization and prevent instability when update denominators are small.The authors report convergence from rough initial guesses in computations, although they state that this behavior cannot be proved.

4 Numerical results

Numerical experiments assess the method’s accuracy, noise robustness, computational practicality, and performance on real, non-periodic, incomplete, and under-sampled data. Results are generally comparable to EMD/EEMD without noise, while the proposed variants retain useful accuracy under challenging conditions.

  • The experiments evaluate FFT-based and l1-regularized nonlinear matching pursuit on periodic, non-periodic, noisy, incomplete, and under-sampled signals.The study also compares results with EMD/EEMD and examines computational performance on Length-of-Day data.
  • For clean signals, the method produces instantaneous frequencies and IMFs comparable to EMD/EEMD, while noisy cases show more accurate phase and frequency recovery.For a single-IMF example, EEMD can fail to capture the exact IMF phase in some regions, whereas the proposed method retains reasonable accuracy.
  • At SNR = −3.01 dB and −12.55 dB, the method still extracts instantaneous frequency and corresponding IMFs with reasonable accuracy.The experiments compare noise-free, moderate-noise, and large-noise versions of the signal.
  • The l1-regularized method reduces boundary error for non-periodic signals and supports incomplete or sparse samples, including reconstruction across missing intervals.With 20% missing data, recovery is almost perfect; with 40% missing data, reconstruction remains reasonable and frequency estimates are best away from the missing region.
  • With sparse under-sampled data and added noise 0.2X(t), both recovered signals and instantaneous frequencies retain reasonable accuracy.The authors interpret this as stability to noise perturbation even for sparse under-sampled data, while noting that further theory and experiments remain future work.

5 Generalizations for the l1 regularized nonlinear matching pursuit

The method is generalized to signals with poor scale separation and intra-wave frequency modulation by modifying the decomposition strategy and dictionary. Numerical examples show accurate, noise-robust recovery in several challenging settings.

  • Generalizations: The iterative l1-regularized nonlinear matching pursuit is extended to data with poor scale separation and intra-wave frequency modulation.The paper presents these extensions through numerical examples, with further methodological details deferred to subsequent work.
  • Poor scale separation: For components with strongly correlated instantaneous frequencies, the method decomposes multiple intrinsic mode functions simultaneously.This modification addresses the difficulty that correlated components may not yield a sparse decomposition when extracted separately.
  • Poor scale separation: Both instantaneous frequencies and intrinsic mode functions match the exact results well for a signal with intersecting instantaneous frequencies, outperforming the previous nonlinear matching pursuit.The comparison is reported for the signal in equation (48).
  • Poor scale separation: For discontinuous instantaneous frequencies, the method remains reasonably accurate with noise, while errors and Gibbs oscillations concentrate near discontinuities.Away from t = 0.3 and t = 0.6, the numerical results match the exact ones well, indicating temporal locality.
  • Intra-wave frequency modulation: An adapted 2π-periodic shape function replaces the cosine dictionary to recover components with intra-wave frequency modulation.The method extracts the shape function using low-rank structure, then updates the phase function; in the Duffing example, it recovers ω = 2 even under Gaussian noise.

6 Some preliminary error analysis for the data with scale separation

The error analysis establishes accuracy under scale-separation assumptions and examines how separation affects temporal locality and iterative refinement. Numerical results indicate that errors are often concentrated where scale separation is poor.

  • Assumptions: The analysis imposes scale-separation conditions to establish uniqueness and accuracy of the decomposition.The well-separated signal definition includes a separation factor ǫ and frequency ratio d > 1.
  • Theoretical error bounds: Under the theorem’s filter and initial-phase conditions, the next-step phase-function accuracy is order ǫ.The result requires a low-pass filter with Fourier support constrained by the frequency ratio and a sufficiently accurate approximate phase.
  • Theoretical error bounds: The instantaneous-frequency error is also order ǫ under the same scale-separation assumption.The paper states this as a consequence of the preliminary error analysis.
  • Numerical validation: Accuracy depends on the scale-separation factor, although the theoretical error estimate is highly overestimated for a signal with ǫ ≈ 1.4.The corresponding numerical instantaneous frequency remains reasonably accurate even with poor scale separation.
  • Temporal locality: When scale separation is poor only in part of a signal, its influence on decomposition accuracy is limited to that region.The analysis attributes this temporal locality to the low-pass filter and reports smaller boundary errors where scales are better separated.
  • Iterative refinement: With a rough initial phase, iterative updates progressively enlarge the interval of accurate instantaneous-frequency approximation.The numerical example shows improvement after successive steps, eventually producing an accurate approximation over the whole interval.

7 Conclusion

The paper presents a data-driven time-frequency method based on nonlinear matching pursuit, combining sparse adaptive decomposition with efficient and noise-stable computation. It establishes convergence under scale separation, identifies remaining challenges, and points toward high-dimensional extensions.

  • Method: The method finds sparse signal representations from a broad intrinsic-mode-function dictionary using nonlinear matching pursuit.The approach generalizes classical matching pursuit to solve the nonlinear optimization problem efficiently and stably under noise.
  • Theory: Under scale separation, the iterative algorithm converges to an approximate decomposition whose accuracy is determined by the signal’s scale separation factor.This is the paper’s preliminary theoretical guarantee for the proposed nonlinear optimization method.
  • Open issues: Several challenges remain, including poor scale separation, intra-wave frequency modulation, end effects, and incomplete or sparse sampling.The paper addresses these issues to some extent but states that substantially more work is needed.
  • Future direction: The method could be generalized to high-dimensional data by adopting a multidimensional phase function.The paper highlights nonlinear ocean-wave propagation as one physical application where a dominant propagation direction may support this extension.

Appendix

The appendix develops estimates used in the theoretical analysis, including bounds for intermediate quantities and the function a(t), and concludes the proof sequence.

  • Proof estimates: The appendix introduces notation and begins estimating the quantity A(γ) as part of the proof.The displayed inequalities specify separate cases for k relative to k0 under the stated assumptions.
  • Proof estimates: The proof applies assumptions and Corollary 6.1 to derive further estimates.The appendix presents these steps as successive components of the bound-estimation argument.
  • Proof conclusion: The appendix obtains estimates for a(t) and b(t) before completing the proof.The supplied passages identify these as concluding estimate steps, followed by the proof’s completion.
Loading 1202.5621v1…