Linear Time Complexity Deep Fourier Scattering Network and Extension to Nonlinear Invariants

Randall Balestriero, Hervé GlotinarXiv 2017 · arXiv

Abstract

This paper introduces a highly scalable, Fourier-domain version of the Scattering Network that achieves linear time complexity. By replacing the standard complex modulus with a quadratic nonlinearity and introducing new "Invariant Dispersion Coefficients" (variance-based features), the authors create a deterministic feature extractor that is both significantly faster and more discriminative than traditional implementations for large-scale audio tasks.

Introduction

Scattering Networks are powerful tools in signal processing, providing a deterministic, multi-layer framework for extracting features invariant to translations and stable against small deformations—similar to the representations learned by Convolutional Neural Networks (CNNs), but without the need for massive labeled datasets.

However, traditional scattering transforms face two major hurdles:

  1. Computational Overhead: Standard implementations often oscillate between the time and frequency domains to apply filters and nonlinearities, leading to $O(N \log N)$ complexity and high memory usage.
  2. Information Loss: The standard complex modulus nonlinearity ($|c|$) is contractive. While beneficial for stability, it can lead to a rapid decay of energy in deeper layers, potentially losing signal-to-noise ratio (SNR) and discriminative detail.

This research aims to make these networks "production-ready" for large-scale audio tasks by optimizing their speed and descriptive capacity.

Methods

The authors propose three primary innovations to the standard scattering architecture:

Pure Fourier Domain Processing

Instead of jumping between domains, the entire network is derived in the Fourier domain. Because wavelets have a known, localized "support" (they are only non-zero in specific frequency ranges), the authors can use sparse matrix operations. By knowing a priori where the zero coefficients will be, they achieve a true linear time complexity ($O(N)$) for inputs already in the Fourier domain.

The Morlet Filter-Bank in the Fourier domain demonstrates the localized support and high sparsity (0.87%) that enables linear time complexity.

Quadratic Nonlinearity

The standard complex modulus is swapped for a second-order quadratic nonlinearity ($|c|^2$). This operator is continuously differentiable and adaptive; it strongly contracts low-amplitude noise while efficiently representing high-amplitude signal events, improving the SNR of the resulting features.

Invariant Dispersion Coefficients

Standard scattering coefficients are essentially "order-one statistics" (the arithmetic mean of the signal over time). The authors introduce a second-order statistic: the variance, or "dispersion." This captures how the signal energy is spread out, providing a more nuanced "fingerprint" of the signal while maintaining translation invariance. These dispersion coefficients ensure that energy not captured by the first layer is accounted for in the invariants, effectively "recycling" signal information.

Experimental Validation

The model was validated using a supervised audio classification task on a subset of the BirdCLEF / Xeno-Canto dataset. This dataset features bird song recordings from 50 different species. Bird songs present a significant challenge due to varying durations, ambient noise, and the presence of multiple species in single recordings.

Key Results

Computational Efficiency

The Python-based implementation was 16 times faster than the well-known "Scatnet" toolbox (implemented in C) for Fourier domain inputs. Empirical testing confirmed the theoretical $O(N)$ complexity, as the execution time scaled linearly with signal size.

Empirical execution times demonstrate the linear scalability of the network as signal size increases.

Classification Performance

Using only these deterministic features and a simple Random Forest classifier, the system achieved a Mean Average Precision (MAP) of 52.4%. This performance is remarkably close to the state-of-the-art (53%), which typically relies on more complex and computationally expensive supervised deep learning models.

Conclusion and Future Work

This work demonstrates that sparsity in the Fourier domain is a powerful feature that allows for a jump to linear complexity. While the current results are impressive, the authors note that a C or GPU implementation would likely yield even more dramatic performance gains. Future research will explore deeper architectures (3+ layers) and the integration of these Fourier networks as fixed front-ends for deep neural networks to further enhance discriminative performance.

Summary updated

Abstract

In this paper we propose a scalable version of a state-of-the-art deterministic time-invariant feature extraction approach based on consecutive changes of basis and nonlinearities, namely, the scattering network. The first focus of the paper is to extend the scattering network to allow the use of higher order nonlinearities as well as extracting nonlinear and Fourier based statistics leading to the required invariants of any inherently structured input. In order to reach fast convolutions and to leverage the intrinsic structure of wavelets, we derive our complete model in the Fourier domain. In addition of providing fast computations, we are now able to exploit sparse matrices due to extremely high sparsity well localized in the Fourier domain. As a result, we are able to reach a true linear time complexity with inputs in the Fourier domain allowing fast and energy efficient solutions to machine learning tasks. Validation of the features and computational results will be presented through the use of these invariant coefficients to perform classification on audio recordings of bird songs captured in multiple different soundscapes. In the end, the applicability of the presented solutions to deep artificial neural networks is discussed.
BibTeX
@misc{balestriero2017linear,
  author = {Randall Balestriero and Hervé Glotin},
  title = {{Linear Time Complexity Deep Fourier Scattering Network and Extension to Nonlinear Invariants}},
  year = {2017},
  eprint = {1707.05841},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1707.05841},
}
Figure