Sparse and Non-Negative BSS for Noisy Data

Jérémy Rapin, Jérôme Bobin, Anthony Larue, Jean-Luc Starck

Abstract

This paper presents nGMCA (non-negative Generalized Morphological Component Analysis), a robust algorithm for sparse and non-negative Blind Source Separation (BSS) designed for noisy datasets. By integrating proximal calculus with the Fast Iterative Shrinkage-Thresholding Algorithm (FISTA), the proposed method provides a mathematically stable framework for enforcing sparsity and non-negativity constraints. Experimental results on synthetic and real NMR spectroscopy data demonstrate that nGMCA significantly outperforms traditional Non-negative Matrix Factorization (NMF) and naive thresholding methods, particularly in high-noise and ill-conditioned scenarios.

Introduction

Blind Source Separation (BSS) is a fundamental problem in signal processing, often described as the "cocktail party problem": recovering individual signals (sources) from mixed observations without prior knowledge of the mixing process. In domains such as NMR spectroscopy or mass spectrometry, two physical constraints are paramount: non-negativity (concentrations and intensities cannot be negative) and sparsity (spectra typically consist of distinct peaks).

While Non-negative Matrix Factorization (NMF) is a standard approach, it frequently fails when faced with significant noise or ill-conditioned mixtures where sources are highly correlated. Previous attempts to incorporate sparsity into NMF often relied on "naive" thresholding or projections that lack mathematical stability, leading to poor convergence in noisy environments.

Methodology

The core innovation of nGMCA lies in its rigorous optimization framework. Unlike heuristic methods that simply "clip" negative values, nGMCA utilizes proximal calculus to solve sub-problems for the mixing matrix ($A$) and sources ($S$) exactly. This ensures that constraints like non-negativity and $\ell_1$ or $\ell_0$ sparsity are satisfied through a formal mathematical process.

To ensure computational efficiency, the algorithm incorporates the Fast Iterative Shrinkage-Thresholding Algorithm (FISTA). Furthermore, it employs a decreasing threshold strategy—akin to simulated annealing—starting with high sparsity thresholds to identify dominant peaks and gradually lowering them. This prevents noise from corrupting the initial estimates of the mixing matrix and helps the algorithm avoid local minima.

Figure 3: Convergence behavior of nGMCA variants compared to a naive extension, illustrating the stability gap.

As shown in Figure 3, the "naive" extension of BSS algorithms is highly unstable, whereas nGMCA variants achieve rapid and stable convergence. The authors compare two versions: $nGMCA^S$ (using soft-thresholding/$\ell_1$ norm) and $nGMCA^H$ (using hard-thresholding/$\ell_0$ pseudo-norm).

Key Results and Discussion

The researchers evaluated nGMCA using synthetic Bernoulli-Gaussian data and real-world NMR spectra of chemical compounds (Menthone, Cholesterol, Lactose, and Saccharose).

Robustness to Source Count and Noise

A significant finding is nGMCA's ability to maintain high performance as the complexity of the problem increases. While standard NMF performance typically degrades rapidly with more sources, nGMCA maintains a high Source Distortion Ratio (SDR) even when separating up to 40 sources from noisy mixtures.

Figure 1: Source Distortion Ratio (SDR) as a function of the number of sources (r), showing nGMCA's superior performance over traditional methods.

Performance on Real Data

On the NMR dataset, nGMCA successfully separated 15 sources even when the mixing matrix was poorly conditioned ($cond(A) \approx 10^4$). In these challenging conditions, traditional methods like ALS and Multiplicative updates failed to produce usable results. Interestingly, while hard-thresholding ($nGMCA^H$) is unbiased, soft-thresholding ($nGMCA^S$) performed better on ill-conditioned mixtures by effectively disambiguating highly similar sources.

Conclusion

nGMCA provides a powerful and stable framework for sparse, non-negative BSS in noisy environments. Its primary advantages include mathematical stability through proximal operators, robustness to ill-conditioned data, and minimal need for manual parameter tuning. Future work may extend this framework to handle "morphological diversity," where sources are sparse in different transform domains (e.g., wavelets), broadening its applicability to natural images and complex audio signals.

Summary updated

Abstract

Non-negative blind source separation (BSS) has raised interest in various fields of research, as testified by the wide literature on the topic of non-negative matrix factorization (NMF). In this context, it is fundamental that the sources to be estimated present some diversity in order to be efficiently retrieved. Sparsity is known to enhance such contrast between the sources while producing very robust approaches, especially to noise. In this paper we introduce a new algorithm in order to tackle the blind separation of non-negative sparse sources from noisy measurements. We first show that sparsity and non-negativity constraints have to be carefully applied on the sought-after solution. In fact, improperly constrained solutions are unlikely to be stable and are therefore sub-optimal. The proposed algorithm, named nGMCA (non-negative Generalized Morphological Component Analysis), makes use of proximal calculus techniques to provide properly constrained solutions. The performance of nGMCA compared to other state-of-the-art algorithms is demonstrated by numerical experiments encompassing a wide variety of settings, with negligible parameter tuning. In particular, nGMCA is shown to provide robustness to noise and performs well on synthetic mixtures of real NMR spectra.
BibTeX
@article{rapin2013sparse,
  author = {Jérémy Rapin and Jérôme Bobin and Anthony Larue and Jean-Luc Starck},
  title = {{Sparse and Non-Negative BSS for Noisy Data}},
  journal = {IEEE Trans. Signal Process.},
  year = {2013},
  url = {https://openreview.net/forum?id=cb5Nr7bx4B},
}
Figure