<figure><img src="image_1.png" /></figure>

HAL
open science

# Sparse BSS in the presence of outliers

Cécile Chenot, Jérôme Bobin, Jérémy Rapin

► To cite this version:

Cécile Chenot, Jérôme Bobin, Jérémy Rapin. Sparse BSS in the presence of outliers. 2015. hal-01103813

HAL Id: hal-01103813

https://hal.science/hal-01103813

Preprint submitted on 15 Jan 2015

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Open licence - etalab
Sparse BSS in the presence of outliers

Cécile Chenot

CEA Saclay

DSM/Irfu/SEDI/LCS

91191 Gif-sur-Yvette, France

Email: cecile.chenot@cea.fr

Jérôme Bobin

CEA Saclay

DSM/Irfu/SEDI/LCS

91191 Gif-sur-Yvette, France

Email: jerome.bobin@cea.fr

Jérémy Rapin

CEA Saclay

DSM/Irfu/SAP/LCS

DSM/LIST/LOAD

91191 Gif-sur-Yvette, France

*Abstract*—While real-world data are often grossly corrupted, most techniques of blind source separation (BSS) give erroneous results in the presence of outliers. We propose a robust algorithm that jointly estimates the sparse sources and outliers without requiring any prior knowledge on the outliers. More precisely, it uses an alternative weighted scheme to weaken the influence of the estimated outliers. A preliminary experiment is presented and demonstrates the advantage of the proposed algorithm in comparison with state-of-the-art BSS methods.

## I. PROBLEM FORMULATION

Suppose we are given $m$ noisy observations $\{\mathbf{X}_i\}_{i=1..m}$ of unknown linear mixtures of $n \le m$ sparse sources $\{\mathbf{S}_j\}_{j=1..n}$ with $t > m$ samples. It is generally assumed that these data are corrupted by a Gaussian noise, accounting for instrumental or model imperfections. However in many applications, some entries are additionally corrupted by outliers, leading to the following model: $\mathbf{X} = \mathbf{A}\mathbf{S} + \mathbf{O} + \mathbf{N}$, with $\mathbf{X}$ the observations, $\mathbf{A}$ the mixing matrix, $\mathbf{S}$ the sources, $\mathbf{O}$ the outliers, and $\mathbf{N}$ the Gaussian noise.

In the presence of outliers, the key difficulty lies in separating the components $\mathbf{O}$ and $\mathbf{A}\mathbf{S}$. To this end, assuming that the term $\mathbf{A}\mathbf{S}$ has low-rank, some strategies [4] suggest to pre-process the data to estimate and remove the outliers with RPCA [3]. However, besides the fact that low-rankness is generally restrictive for most BSS problems, the source separation is severely hampered if the outliers are not well estimated. Therefore, we introduce a method that estimates the sources in the presence of the outliers without pre-processing. For the best of our knowledge, it has only been studied in [5] by using the $\beta$-divergence. Unlike [5], we propose to estimate jointly the outliers and the sources by exploiting their sparsity.

## II. ALGORITHM

Building upon the GMCA algorithm which has been shown to be an efficient BSS method for sparse sources [1], our approach estimates iteratively $\mathbf{O}$, $\mathbf{S}$ and $\mathbf{A}$. However, the straightforward extension of the GMCA algorithm struggles to distinguish between the sources and the outliers. Indeed, we can face important leakages from the outliers towards the estimated sources, misleading the estimation of $\mathbf{A}$. In the spirit of [2], we propose to further penalize the columns with detected outliers according to their amplitudes to limit their influence. Accordingly, the proposed robust-GMCA (rGMCA) algorithm aims at solving:

$$ \underset{\mathbf{O},\mathbf{A},\mathbf{S}}{\text{minimize}} \frac{1}{2} \|(\mathbf{X} - \mathbf{A}\mathbf{S} - \mathbf{O})\mathbf{W}\|_2^2 + \lambda \|\mathbf{S}\|_1 + \alpha \|\mathbf{O}\|_1, $$

where $\mathbf{W}$ is the penalizing diagonal matrix of size $t \times t$ such that $w_{i,i} = \frac{1}{1+\|\mathbf{O}^i\|_1}$ with $\mathbf{O}^i$ the $i$th column of $\mathbf{O}$.

The problem is non-convex but can be efficiently tackled using block coordinate descent [7], see Algorithm 1. The parameters $\lambda$ and $\alpha$ are set automatically based on the noise level, similarly to the thresholding strategy in [2].

<figure><img src="image_3.png" /><figcaption>Fig. 1. $\Delta_A$ versus the amplitudes of the outliers (median of 80 simulations).</figcaption></figure>

## III. EXPERIMENT

We compare our algorithm with rGMCA (the unweighted version of our algorithm) and also with standard BSS techniques: GMCA [1], RPCA+ICA [3], $\beta$ Divergence [5] (implementation from [6]). We create 16 measurements of 8 sources of size 1024 generated from a Bernoulli-Gaussian law with parameter of activation 0.12 and standard deviation 100, to which a Gaussian noise is added. The support of the outliers is created such that: 160 are drawn uniformly at random, and 10 columns are entirely corrupted. Their amplitudes are Gaussian, with a standard deviation chosen according to fig.1. The variation of $\Delta_A = \|(\tilde{\mathbf{A}}^T\tilde{\mathbf{A}})^{-1}\tilde{\mathbf{A}}^T\mathbf{A} - \mathbf{I}\|_1$, with $\tilde{\mathbf{A}}$ the estimated matrix, versus the amplitude of the outliers is represented in fig.1. Our weighting procedure outperforms the standard algorithms and is almost not influenced by the amplitude of the outliers, fig.1. In the second experiment, the amplitude of the outliers is set to $10^2$. The total number of outliers is chosen according to fig.2. One half of the outliers is drawn uniformly at random and the other one corresponds to the entirely corrupted columns of $\mathbf{X}$. Our algorithm gets again better results and the estimation of $\mathbf{A}$ is nearly not affected by the increasing number of outliers. Furthermore, whereas the problem is not convex and has no free parameter, only 8 of the 800 simulations return an error larger than $10^{-3}$.
<figure><img src="image_4.png" /><figcaption>Fig. 2. $\Delta_A$ versus the total number of outliers (median of 80 simulations).</figcaption></figure>

IV. CONCLUSION

We propose a new robust BSS algorithm which estimates jointly
outliers and sources and exploits their sparsity. These explicit esti-
mations make any addition of a weighting scheme or of further prior
easy. Numerical experiments show that the estimation of the mixing
matrix is clearly enhanced with our weighting procedure.

REFERENCES

[1] J.Bobin, J.L.Starck, Y.Moudden and M.J.Fadili, “Blind Source Separation: The Sparsity Revolution”, *Advances in Imaging and Electron Physics*, vol.152, 2008.

[2] J.Bobin, J.Rapin, A.Larue, J.L.Starck, “Sparsity and Adaptivity for the Blind Separation of Partially Correlated Sources”, arXiv:1412.4005, in press.

[3] E.J.Candès, X.Li, Y.Ma and J.Wright, “Robust Principal Component Analysis?”, *Journal of ACM*, vol.58, 2011.

[4] Q.Li, H.Li, Z.Lu, Q.Lu and W.Li, “Denoising of Hyperspectral Images Employing Two-Phase Matrix Decomposition”, *IEEE J. Sel. Topics Appl. Earth Observ. Remote Sens.*, vol.7, 2014.

[5] M.Mihoko and S.Eguchi, “Robust blind source separation by beta divergence”, *Neural Computation*, vol.14, 2002.

[6] N.Gadhok and W.Kinsner, “An Implementation of β- Divergence For Blind Source Separation”, *IEEE CCGE/CCGEI*, Ottawa, 2006.

[7] P.Tseng, “Convergence of a Block Coordinate Descent Method for Nondifferentiable Minimization”, *Optimization*, 2001.