Overcomplete Frame Thresholding for Acoustic Scene Analysis

Romain Cosentino, Randall Balestriero, Richard Baraniuk, Ankit PatelarXiv 2017 · arXiv

TL;DR

This paper introduces a novel, computationally efficient thresholding technique for overcomplete frames based on empirical risk minimization. By overcoming the mathematical intractability of denoising in redundant dictionaries, the authors develop a Sparse Deep Scattering Network (SDSN) that significantly improves audio classification performance in highly noisy, real-world environments.

What Problem Does This Paper Address?

In signal processing and machine learning, real-world data is frequently corrupted by noise. A standard remedy is the analysis-synthesis framework: transform the data into a new basis, denoise it via thresholding, and either classify the clean coefficients or reconstruct the signal.

While orthogonal bases (like standard discrete wavelets) are mathematically convenient for this, they suffer from poor time-frequency resolution and instability. Overcomplete frames (redundant dictionaries) offer a much more robust, precise, and stable alternative—akin to a person with a vast vocabulary who can express ideas with high precision.

However, thresholding in overcomplete frames is historically notorious. Because the dictionary atoms are highly correlated, calculating the "ideal risk" for denoising turns into an intractable factorial optimization problem. Consequently, thresholding methods for overcomplete frames have previously only been solved for highly specific, restricted cases.

Methods

The authors tackle this intractability by deriving a generic, analytical thresholding scheme based on Empirical Risk Minimization (ERM). Their core contributions include:

  1. Min-Max Risk Bounding: To bypass the factorial optimization problem, they develop a min-max formulation that establishes an upper bound on the ideal risk. This decouples the correlated terms into a tractable, analytical expression.
  2. Empirical Risk Formulation: Since real-world applications lack an "oracle" to provide the true noise-free signal, they substitute the observed noisy signal into the upper-bound equation to create an empirical risk estimator.
  3. Sparse Deep Scattering Network (SDSN): They integrate this non-linear thresholding technique into a Deep Scattering Network (DSN). In a standard DSN, layers consist of a wavelet transform followed by a complex modulus and a low-pass filter. The SDSN introduces their thresholding operator directly onto the latent representations at each layer before computing the scattering coefficients, effectively stripping away noise at multiple scales.

The resulting algorithm is computationally efficient: it scales linearly with the number of signals and quadratically with the number of filters (which can be precomputed once for all signals, enabling easy parallelization).

Datasets

The method was validated on a large-scale audio classification task using the Freefield1010 dataset from the Bird Audio Detection Challenge.

  • Composition: 7,000 field recording signals (10 seconds each, sampled at 44.1 kHz).
  • Diversity: Contains a wide variety of environmental audio scenes, including birdsong, city noise, rain, people talking, and trains.
  • Scale: The dataset represents nearly 20 hours of audio, making it roughly 20 times larger than the CIFAR-10 dataset in terms of raw scalar values.

Key Insights and Ideas

  • Breaking the Redundancy Curse: The most significant mathematical achievement is showing that an upper bound can accurately approximate ideal risk in non-orthogonal settings. Proposition 1 proves that if the filter matrix happens to be orthogonal, their upper bound perfectly collapses back to the classical orthogonal ideal risk defined by Donoho et al.
  • Drastic Sparsity Gains: Continuous wavelet transforms of noisy field recordings are typically not sparse at all (sparsity ratio $\alpha \approx 0$). Applying the proposed thresholding technique dramatically clears out background noise, driving the sparsity ratio up to $\alpha \approx 0.92$ while perfectly preserving the foreground transient signals, such as bird chirps.
Visualizing the impact of denoising on the scalogram: noisy vs. denoised representations across different audio scenes.
  • Multi-Layer Denoising: In deep architectures like the SDSN, noise propagates and compounds across layers. Denoising the latent representation at the first layer still leaves residual noise in the second layer's representation, which the SDSN successfully eliminates at the subsequent stage.
Architecture and feature visualization of the Sparse Deep Scattering Network using Gammatone wavelets.

Key Results

The authors evaluated their approach using the Area Under Curve (AUC) metric on a bird activity detection task, comparing the SDSN against a standard DSN using both Gammatone and Morlet wavelets:

  • Gammatone Wavelets: The SDSN achieved a mean AUC of 74.23% (compared to 72.77% for the standard DSN).
  • Morlet Wavelets: The SDSN achieved a mean AUC of 73.49% (compared to 72.37% for the standard DSN).

The true power of the method emerged during controlled denoising experiments with mismatched noise proportions between the training and testing sets (simulating unpredictable real-world deployments). In highly volatile regimes—such as training on 100% clean data but testing on 100% noisy data—the SDSN provided an extraordinary performance boost, yielding an AUC improvement of +23.9% over the standard DSN.

Limitations and Future Work

The primary theoretical limitation acknowledged by the authors is that the tightness of their risk bound depends on the dictionary's redundancy. As shown in Proposition 3, the more redundant the overcomplete dictionary is, the less tight the upper bound becomes.

Additionally, while the algorithm's quadratic complexity relative to the number of filters can be mitigated via precomputation and parallelization, scaling to extremely massive filter banks could still pose a computational bottleneck for real-time applications on edge devices.

Summary updated

Abstract

In this work, we derive a generic overcomplete frame thresholding scheme based on risk minimization. Overcomplete frames being favored for analysis tasks such as classification, regression or anomaly detection, we provide a way to leverage those optimal representations in real-world applications through the use of thresholding. We validate the method on a large scale bird activity detection task via the scattering network architecture performed by means of continuous wavelets, known for being an adequate dictionary in audio environments.
BibTeX
@misc{cosentino2017overcomplete,
  author = {Romain Cosentino and Randall Balestriero and Richard Baraniuk and Ankit Patel},
  title = {{Overcomplete Frame Thresholding for Acoustic Scene Analysis}},
  year = {2017},
  eprint = {1712.09117},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1712.09117},
}
Figure