Blind Source Separation (BSS) - Seminar Report

INTRODUCTION

In the field of digital signal processing there is a problem known as Cocktail Party, which try to separate signals (voice or music) mixed simultaneously based only on their mixtures.Blind Source Separation (BSS) is a powerful technique capable of solving this problem.BSS have applications in mobile telephony, multiuser communication systems, eliminating redundancy and sparse coding in noise cancellation, voice reinforcement in noisy environments, as well as in other important environments such as urban ecology specifically on pollution caused by high sound levels.  This technique is based on the following principle: assuming that the original signals are mixed linearly and it is possible to collect these mixtures with appropriate sensors, the BSS is able to estimate the coefficients that characterize this linear combination, and therefore can estimate the original signals.

Blind Source Separation is used for the separation of the individual source signals from a mixture of signals, whose mixing process is unknown. It also does not have any knowledge about the characteristics of source signals and the source from which the signals have originated. The only information available is the received signals or the observed signals whose mixing process remains unknown. The BSS technique is used to achieve source separation in such circumstances using some statistical properties of original source. 

The aim is to recover the independent source signals given only the sensor readings composed of unknown linear combinations of the independent sources and separate the signals from the background noise.BSS can be applied to a variety of situations such as, the separation of simultaneous speakers, analysis of biomedical signals obtained by EEG or in wireless telecommunications to separate several received signals. The basic block diagram of signal separation using BSS techniques .Consider two source signals S1 and S2.These are captured by two microphones. The outputs of the microphones will be the combination of the two signals .

         

 Basic Block Diagram

To separate out the original source signals from the microphone outputs different algorithms are there namely: 

1) Independent Component Analysis (ICA). 

2) Principal Component Analysis (PCA). 

3) Beamforming

4) Degenerate Unmixing Estimation Technique (DUET). 

INDEPENDENT COMPONENT ANALYSIS (ICA) 

The Independent Components Analysis algorithm allows two source signals to be separated from two linear mixtures of the source signals using statistical principles of independence and nongaussianity.ICA assumes that the value of each source at any given time is a random variable.It also assumes that each source is statistically independent. This implies that the values of one source cannot be correlated to values in any of the other sources.With these assumptions, ICA allows us to separate source signals from mixtures of these source signals.The algorithm requires that there be as many sensors as input signals.It is based on higher order statistics like Kurtosis, Negentropy etc where complete statistical independence of the signals is the primary concern.

PRINCIPAL COMPONENT ANALYSIS (PCA) 

Principal component analysis is a technique that is useful for the compression and classification of data.It involves a mathematical procedure that transforms a number of possibly correlated variables into a smaller number of uncorrelated variables called principal components.The main purpose is to reduce the dimensionality of a data by finding a new set of variables retaining most of the information.PCA requires the calculation of the eigen value decomposition of a data covariance matrix or singular value decomposition of a data matrix, usually after mean centering the data.Analysis is done in the time domain.

BEAMFORMING 

Beamforming is the process of trying to concentrate the array to sounds coming from only one particular direction.Beamformer is a spatial filter that process data obtained from an array and tries to extract the desired signal from the background noise and interferences. Sensor array collects spatial samples of propagating signal source.Parameters in beamforming are adjusted to form a spatial pattern with a dominant response for the direction of interest while the response for the position of interfering signals is minimized.

DEGENERATE UNMIXING ESTIMATION TECHNIQUE (DUET) 

DUET algorithm is an approach that assumes that the signals are non-overlapping in the frequency domain. DFT of a block of recordings given by ‘G’ matrix is taken. By taking DFT ‘G’ matrix is transformed from the time domain to frequency domain.The amplitude and phase characteristics of the respective frequency component thus becomes known and using this a histogram is plotted.The frequency with maximum number of occurrence gives the separated sources.Then IFT of the source is taken which enables to identify the extracted signals.

Out of this Blind source separation by Independent Component Analysis(ICA) is discussed in detail here.

INDEPENDENT COMPONENT ANALYSIS

MOTIVATION

ICA or Independent Component Analysis is a hugely researched technique for blind source separation.ICA has developed a lot over the years and several algorithms and methods have been researched till date.The problem is to separate two or more signals which have been linearly combined to generate mixed signals which are available to us but we have no prior knowledge about the source signals.A possible real life situation where ICA can be used is to separate the voice from the noise while using a mobile phone when the noise is too high. 

In ICA each signal at any given time can be considered as a random variable.It is  assumed that each source signal is statistically independent at least in the weak sense i.e.no source can be correlated to any of the other sources.With these assumptions,ICA allows us to separate source signals from linear mixtures of these source signals. The algorithm requires that there be as many sensors as input signals.It is based on higher order statistics like Kurtosis,Negentropy etc where complete statistical independence of the signals is the primary concern.For example,with two independent sources and two sensors giving two mixed signals, the problem could be modelled as as shown in figure 2.1: 

ICA APPROACH

The starting point for ICA is the very simple assumption that the components the sources   are statistically independent.A “source” means here an original signal i.e. independent component,like the speaker in a cocktail party problem. “Blind” means that we have no or very little prior knowledge about the mixing matrix, and make very few assumptions about the source signals. 

PRE-PROCESSING FOR ICA 

Pre-processing step in ICA is to make the sure that the observed mixed signals have zero mean, unit variance and are de-correlated. The de-correlation removes the second-order dependencies between the observed signals. The following methods are used to pre-process the ICA data. 

CENTERING:

  The most basic and necessary pre-processing is to centre x, i.e. subtract its mean vector m = E{x} so as to make x a zero-mean variable.

x = x – E{x}          (2.4)

  This pre-processing is made solely to simplify the ICA algorithms: It does not mean that the mean could not be estimated. After estimating the mixing matrix A with centred data, we can complete the estimation by adding the mean vector of s back to the centred estimates of s.The mean vector of s is given by  m,where m is the mean that was subtracted in the preprocessing.

WHITENING: 

Another useful preprocessing strategy in ICA is to first whiten the observed variables. This means that before the application of the ICA algorithm (and after centering), we transform the observed vector   linearly so that we obtain a new vector   which is white, i.e. its components are uncorrelated and their variances equal unity. In other words, the covariance matrix of    equals the identity matrix.

E{  } = I          

One popular method for whitening is to use the eigen-value decomposition (EVD) of the covariance matrix E{ x }=ED , where E is the orthogonal matrix of eigenvectors of E{ x  } and D is the diagonal matrix of its eigen-values,D= diag(d1, ...,dn). Whitening can now be done by 

 x = E x.                                                       

Whitening means the removal of any correlations in the data. A geometrical interpretation is that it restores the initial "shape" of the data and that then ICA must only rotate the resulting matrix (see below). Once more, let's mix two random sources A and B. At each time, in the following graph, the value of A is the abscissa of the data point and the value of B is their ordinates. Let us take two linear mixtures of A and B and plot these two new variables (Fig 4.2 and Fig 4.3)      

Whitening reduces the number of parameters to be estimated. Because whitening is a very simple and standard procedure, much simpler than any ICA algorithms, it is a good idea to reduce the complexity of the problem this way.

WHY GAUSSIAN VARIABLES ARE FORBIDDEN?

The fundamental restriction in ICA is that the independent components must be non-Gaussian for ICA algorithms to work. Gaussian variables make ICA impossible. The figure below shows the joint distribution of two uncorrelated Gaussian variables of unit variance. Clearly, it does not contain any information on the directions of the columns of the mixing matrix A. This is why A cannot be estimated from the above data.

PRINCIPLES OF ICA ESTIMATION 

The key to estimating the ICA model is non-Gaussianity.Actually, without non-Gaussianity the estimation is not possible at all, as mentioned in above section. The Central Limit Theorem tells us that the distribution of a sum of independent random variables tends toward a Gaussian distribution, under certain conditions. 

Let us denote this by y =   x = Σwixi, where w is a vector to be determined. Let us make a change of variables, defining z =  w. Then we have 

y =  x =  As =  s.                                               

y is thus a linear combination of si, with weights given by zi. Since a sum of even two independent random variables is more Gaussian than the original variables, zT s is more Gaussian than any of the si and becomes least Gaussian when it in fact equals one of the si. In this case, obviously only one of the elements zi of z is nonzero. (Note that we assumed that the si here have identical distributions). Therefore, we could take as w a vector that maximizes the non-Gaussianity of wT x. Such a vector would necessarily correspond to a z which has only one nonzero component. This means that wTx = zT s equals one of the independent components.

ICA ALGORITHM 

ICA rotates the whitened matrix back to the original (A,B) space. It performs the rotation by minimizing the Gaussianity of the data projected on both axes (fixed point ICA). 

The projection on both axis is quite Gaussian (i.e., it looks like a bell shape curve). By contrast the projection in the original A, B space is far from Gaussian.

By rotating the axis and minimizing Gaussianity of the projection in the first scatter plot, ICA is able to recover the original sources which are statistically independent (this property comes from the central limit theorem which states that any linear mixture of 2 independent random variables is more Gaussian than the original variables). 

STEPS IN ICA 

Here we used Kurtosis, as a measure of nongaussianity to identify the independent source signals. It begins by guessing a row of the matrix W. This row represents the weighting coefficients for finding one of the original source signals. It then measures the non-gaussianity of the proposed independent source defined by its guess of W, and finds the gradient of non-gaussianity to determine how the coefficients in W should change. It then uses a projection of the gradient to create a new guess of the coefficients in W, and continues in a cycle until the coefficients converge on certain values. Once this occurs, the resulting independent source is as nongaussian as it can be. 

The algorithm repeats this process for finding all the rest of the independent sources, taking care not to find the same source twice.

AMBIGUITIES AND LIMITATIONS

The following significant ambiguities arise in the ICA algorithm. 

INDETERMINATE ENERGY: 

Because a scalar multiplier could be pulled out of s and multiplied to A with no change in the above equations, the ICA algorithm cannot determine the energy contained in any of the independent sources it finds. The amplitudes it gives the output components are arbitrary, and the true source signal could be one the isolated sources multiplied by any scalar multiple. This includes a negative multiple, which means that often, the output signals are also inversions of the original signals. This may not be a problem with speech signals but may be a problem with images where energy will matter. 

ORDER AMBIGUITY: 

Because the algorithm chooses coefficients of “W” at random when it searches for the sources, the isolated sources that the algorithm finds can come out in any order. So, it would take some additional processing to determine which independent sources is the one of interest to us. 

UNDER-DETERMINATION: 

There must be as many sensors as there are sources in order to properly isolate the sources. If there are not enough sensors, the resulting signals will not match any of the sources, but rather will still be mixtures of multiple sources. 

LINEARITY:

 ICA can only handle linear mixtures that can be represented in the form x = As. The algorithm cannot accurately guess the independent sources if the sources are out of phase in the mixtures or if the mixtures have other nonlinear features. 

APPLICATIONS OF ICA

Independent Component Analysis (ICA) is the identification & separation of mixtures of sources with little prior information. Applications include: 

AUDIO PROCESSING :- 

The problem of separation of audio sources recorded in a real world situation is well established in modern literature. A method to solve this problem is Blind Source Separation (BSS) using Independent Component Analysis (ICA). The recording environment is usually modeled as convolutive. Previous research on ICA of instantaneous mixtures provided solid background for the separation of convolved mixtures. The authors revise current approaches on the subject and propose a fast frequency domain ICA framework, providing a solution for the apparent permutation problem encountered in these methods [5]. 

MEDICAL DATA :- 

The analysis of electroencephalographic (EEG) and magnetoencephalographic (MEG) recordings is important both for basic brain research and for medical diagnosis and treatment. Independent component analysis (ICA) is an effective method for removing artifacts and separating sources of the brain signals from these recordings. In this paper, outline the assumptions underlying ICA and demonstrate its application to a variety of electrical and hemodynamic recordings from the human brain. 

FINANCE :-

 In the case in financial time series, the ICA transformation produces useful component signals whose dependence is reduced, and that are nonGaussian with a density allowing sparse coding . The ICA transformation is also related to the temporal structure of the found signals as measured by Kolmogorov complexity or its approximations. The signals are structured and hence may be easier to interpret and predict.

BLIND SOURCE SEPERATION :-

 Blind source separation(BSS) consist of processing a set of observed mixed signals to separate them into unobservable set of original components. Various approaches have been employed to solve BSS problem using the strong assumptions focussing on mutually uncorrelated (or orthogonal) source signals. However in many real life problems signal orthogonality is not guaranteed. 

COMMUNICATION :- 

Examine the impact of channel fading on the bit error rate of a DS-CDMA communication system. The system employs detectors that incorporate neural networks effecting methods of independent component analysis (ICA), subspace estimation of channel noise, and Hopfield type neural networks. The Rayleigh fading channel model is used. When employed in a Rayleigh fading environment, the ICA neural network detectors that give superior performance in a flat fading channel did not retain this superior performance.When the ICA neural network detectors were compensated using the incorporation of priors, they give significantly better performance than the traditional detectors and the uncompensated ICA detectors.

CONCLUSION

The BSS technique is used to achieve signal separation in circumstances where the only information available is the received signals or the observed signals whose mixing process remains unknown. It also does not have any knowledge about the characteristics of signals and the source from which the signals have originated. BSS can be applied to a variety of situations such as, the separation of simultaneous speakers, analysis of biomedical signals obtained by EEG or in wireless telecommunications to separate several received signals.We have to recover the independent source signals given only the sensor readings composed of unknown linear combinations of the independent sources. We can successfully separate the signals or separate the signals from the background noise.