Elsevier

Neurocomputing

Volume 69, Issues 13–15, August 2006, Pages 1458-1466
Neurocomputing

Sparse ICA via cluster-wise PCA

https://doi.org/10.1016/j.neucom.2005.12.022Get rights and content

Abstract

In this paper, it is shown that independent component analysis (ICA) of sparse signals (sparse ICA) can be seen as a cluster-wise principal component analysis (PCA). Consequently, Sparse ICA may be done by a combination of a clustering algorithm and PCA. For the clustering part, we use, in this paper, an algorithm inspired from K-means. The final algorithm is easy to implement for any number of sources. Experimental results points out the good performance of the method, whose the main restriction is to request an exponential growing of the sample number as the number of sources increases.

Introduction

Blind Source Separation (BSS) consists in retrieving unknown statistically independent signals from their mixtures, assuming there is no information either about the original source signals, or about the mixing system (hence the term Blind). Let s(t)(s1(t),,sN(t))T be the vector of unknown source signals (assumed to be zero-mean and statistically independent), and x(t)(x1(t),,xN(t))T be the vector of observed signals (in this paper, the number of observations and sources are assumed to be equal). Then, for linear instantaneous mixtures x(t)=As(t), where A is the N×N (unknown) ‘mixing matrix’. The problem is then to estimate the source vector s(t) only by knowing the observation vector x(t).

Since the only information about the source signals is their statistical independence, an idea for retrieving them is to find a ‘separating matrix’ B that transforms again the observations into independent signals. In other words, B is calculated in such a way that the output vector yBx has independent components. This approach, which is usually called Independent Component Analysis (ICA), has been shown [2] to retrieve the source signals up to a scale and a permutation indeterminacy (i.e. the energies of the sources and their order cannot be restored).

On the other hand, Principal Component Analysis (PCA) is a technique to transform a random vector to another random vector with decorrelated components. Let RxE{xxT} be the correlation matrix of the zero-mean random vector x. Moreover, let λi,i=1,,N be the eigenvalues of Rx corresponding to (orthonormal) eigenvectors ei,i=1,,N. Now, ifB=ET,where E[e1,,eN], then it can be easily verified that the covariance matrix of y=Bx is diagonal. More precisely, Ry=Λ, where Ry is the correlation matrix of y and Λdiag(λ1,,λN). In other words, the components of y (called the principal components of x) are decorrelated, and their variances are λi,i=1,,N. Fig. 1 shows the plot of the samples of a random vector x and its principal components.

It is well known that for BSS (or ICA) output independence cannot be simplified as output decorrelation (PCA) [1]. Consequently, PCA cannot be used for solving the ICA problem. However, the goal of this paper is to show that for sparse signals, ICA can be achieved by a cluster-wise PCA.

To state the idea more precisely, note first that from (1), each row of B in PCA is composed of the direction of one of the principal components. We are going to show in this paper that for sparse signals, the ICA matrix can be obtained by a clustering of observation samples, and then by taking the direction of the smallest principal component (i.e. the principal component with the smallest variance) of each cluster as the rows of B. Developing a clustering algorithm inspired from K-means, we will also obtain an ICA algorithm for sparse signals.

To obtain the above result, we start with the geometrical ICA algorithm [7], and then modify and extend it to sparse signals. Although the development of our approach is started form geometrical interpretations, the final algorithm (see Fig. 7) is completely algebraic. Moreover, contrary to geometrical ICA algorithm, our result and approach are easy to extend for more than two sources.

The paper is organized as follows. Section 2 reviews the geometrical source separation algorithm, and its modification for using it in separating sparse signals. Then, we will see, in Section 3, how hyper-plane fitting can be used for sparse ICA. After reviewing, in Section 4, the Principal Component Regression (PCR) method for hyper-plane fitting, an approach for fitting N hyper-planes onto a set of data points is proposed in Section 5. Putting all together, the final algorithm is presented in Section 6. Finally, some experimental results are given in Section 7.

Section snippets

Classical geometric algorithm

The geometrical interpretation of ICA, which results in the geometrical source separation algorithm, has been first introduced in [7]. In this approach (for two-dimensional case), using source independence i.e. ps1,s2(s1,s2)=ps1(s1)ps2(s2), where p stands for the probability density function (PDF), one easily sees that, for bounded sources in which there exist A1 and A2 such that ps1(s1)=0 for |s1|>A1 and ps2(s2)=0 for |s2|>A2, the support of ps1,s2(s1,s2) is the rectangular region {(s1,s2)||s1|

Two-dimensional case

As it is explained in the previous section, our main idea is to estimate the slopes of two axes of the scatter plot of observations (Fig. 3b). These axes correspond to the lines s1=0 and s2=0 in the scatter plot of sources. The existence of these lines is a result of the sparsity of the source signals. For example, the points with small s1 and different values for s2 will form the axis s1=0.

However, we do not use (2) as a model for mixing matrix, because it has two restrictions. Firstly, in

Fitting a straight line (a hyper-plane) onto a set of points

To use the idea of the previous section in separating two (N) sparse sources, we need a method for fitting two lines (N hyper-planes) onto the scatter plot of observations. In this section, we consider the problem of fitting one line (one hyper-plane) onto a set of points. Then, in the following section, a method for fitting two lines (N hyper-planes) will be stated based on the method of this section for fitting one line (one hyper-plane).

The approach presented in this section for line

Fitting 2 straight lines (N hyper-planes)

In the previous section, an approach for fitting one hyper-plane onto a set of points was presented. However, as stated in Section 3, for separating N sparse signals (by having N mixtures of them), we need to fit N hyper-planes onto observation points, not to fit just one hyper-plane.

For example, as it is seen in Fig. 3 for the two-dimensional case, we need to fit two lines onto the scatter plot of observations for finding the two axes. For doing this, we can first divide the points into two

Final sparse ICA algorithm

The final separation algorithm is now evident. First, run the algorithm FITLIN. After convergence, there are N lines (hyper-planes) li:αi1x1++αiNxN=0, i=1N. Then, the ith row of the separating matrix is (αi1,,αiN).

Fig. 7 shows the final algorithm of this paper for blind separating sparse sources. Note that, as explained in Section 5.3, to reduce the probability of getting trapped in a local minimum, this algorithm must be run with several random initializations, and the answer which results

Experimental results

Many simulations have been conducted to separate 2, 3 or 4 sparse sources. In all these simulations, typically less than 30 iterations are needed to achieve separation. The experimental study shows that local minima depends on the initialization of the algorithm and on the number of sources (in our simulations local minima have been never encountered in separating two sources).

Here, the simulation results of 4 typical speech signals as an example of sparse signals are presented. The sparsity of

Conclusion

In this paper, we showed that sparse ICA can be seen as a cluster-wise PCA (more precisely cluster-wise MCA), and hence it can be done by a combination of a clustering algorithm and PCA. Proposing a clustering algorithm inspired from k-means, we obtained an algorithm for sparse ICA.

Although using a clustering algorithm we proposed a sparse ICA algorithm, it must be noted that the main point of the paper is not the final sparse ICA algorithm, but it is the fact that sparse ICA can be done

Massoud Babaie-Zadeh received the B.S. degree in electrical engineering from Isfahan University of Technology, Isfahan, Iran in 1994, and the M.S degree in electrical engineering from Sharif University of Technology, Tehran, Iran, in 1996, and the Ph.D. degree in Signal Processing from Institute National Polytechnique of Grenoble (INPG), Grenoble, France, in 2002 (for which, he received the best Ph.D. thesis award of INPG). Since 2003, he has been an Assistant Professor of the Department of

References (7)

There are more references available in the full text version of this article.

Cited by (0)

Massoud Babaie-Zadeh received the B.S. degree in electrical engineering from Isfahan University of Technology, Isfahan, Iran in 1994, and the M.S degree in electrical engineering from Sharif University of Technology, Tehran, Iran, in 1996, and the Ph.D. degree in Signal Processing from Institute National Polytechnique of Grenoble (INPG), Grenoble, France, in 2002 (for which, he received the best Ph.D. thesis award of INPG). Since 2003, he has been an Assistant Professor of the Department of Electrical Engineering at Sharif University of Technology, Tehran, Iran. His main research areas are Statistical Signal Processing, Blind Source Separation (BSS) and Independent Component Analysis (ICA).

Christian Jutten received the Ph.D. degree in 1981 and the Docteur ès Sciences degree in 1987 from the Institut National Polytechnique of Grenoble (France). He taught as associate professor in Ecole Nationale Supérieure d’Electronique et de Radioélectricité of Grenoble from 1982 to 1989. He was visiting professor in Swiss Federal Polytechnic Institute in Lausanne in 1989, before to become full professor in Université Joseph Fourier of Grenoble, more precisely in Polytech’Grenoble institute. He is currently associate director of the images and signals laboratory (100 peoples). For 25 years, his research interests are blind source separation, independent component analysis and learning in neural networks, including theoretical aspects (separability, source separation in nonlinear mixtures) applications in signal processing (biomedical, seismic, speech) and data analysis. He is author or co-author of more than 40 papers in international journals, 16 invited papers and 100 communications in international conferences. He has been associate editor of IEEE Trans. on Circuits and Systems (1994–95), and co-organizer with Dr. J.-F. Cardoso and Prof. Ph. Loubaton of the 1st International Conference on Blind Signal Separation and Independent Component Analysis (Aussois, France, January 1999). He is currently member of a technical committee of IEEE Circuits and Systems society on blind signal processing. He is a reviewer of main international journals (IEEE Trans. on Signal Processing, IEEE Signal Processing Letters, IEEE Trans. on Neural Networks, Signal Processing, Neural Computation, Neurocomputing, etc.) and conferences in signal processing and neural networks (ICASSP, ISCASS, EUSIPCO, IJCNN, ICA, ESANN, IWANN, etc.).

Ali Mansour received his Electronic-Electrical Engineering Diploma in 1992 from the Lebanese University (Tripoli, Lebanon), and his M.Sc. and the Ph.D. degrees in Signal, Image and Speech Processing from INPG (Grenoble, France) in August 1993 and January 1997, respectively. From January 1997 to July 1997, he held a post-doc position at LTIRF–INPG, Grenoble, France. From August 1997 to September 2001, he was a Research Scientist at the Bio-Mimetic Control Research Center of RIKEN, Nagoya, Japan. Since October 2001, he has been a Teacher-researcher at ENSIETA—Brest, France. His research interests are in the areas of blind separation of sources, high-order statistics, signal processing, COMINT, radar, sonar and robotics.

1

This work has been partially funded by Sharif University of Technology, by French Embassy inTehran, and by Center for International Research and Collaboration (ISMO).

View full text