Blind Source Separation: PCA & ICA - mit.edu

1 D. Clifford gari [at] mit . ~gari G. D. Clifford 2005-2009 Blind Source Separation: PCA & ICAWhat is BSS?Assume an observation (signal) is a linear mix of >1 unknown independentsource signalsThe mixing (not the signals) is stationaryWe have as manyobservations as unknown sources To find sources in observations- need to define a suitable measure of For example - the cocktail party problem(sources are speakers and background noise):The cocktail party problem - find ZAz1z2zNXTZTXT=AZTx1x2xN2 Formal statement of problem N independentsources.

2 Zmn( MxN) linear square mixing ..Ann( NxN) (#sources=#sensors) produces a set of observations ..Xmn( MxN).. XT= AZTF ormal statement of solution demix observations ..XT( NxM)into YT= WXTYT(NxM) ZTW(NxN) A-1 How do we recover the independent sources? (We are trying to estimate W A-1).. We require a measure of independence! Signal Source Noise sourcesObserved mixturesZTXT=AZTYT=WXT3XT = A ZTYT = W XTTTTTThe Fourier Transform(Independence between components is assumed) Recap: Non-causal Wiener filteringx[n] - observationy[n] - ideal signald[n] - noise componentIdeal Signal Sy(f)Noise Power Sd(f)Observation Sx(f)Filtered signal: Sfilt(f ) = Sx(f).

3 H(f )f4 BSS is a transform? Like Fourier, we decompose into components by transforming the observations into another vector space which maximises the separationbetween interesting (signal) and unwanted (noise). Unlike Fourier, separation is not based on frequency-It s based on independence Sources can have the same frequency content No assumptionsabout the signals (other than they are independentand linearlymixed) So you can filter/separate in-bandnoise/signals with BSSP rincipal Component Analysis Second orderdecorrelation= independence Find a set of orthogonalaxes in the data (independence metric = variance)

4 Project data onto these axes to decorrelate Independenceis forced onto the data through the orthogonalityof axes Conventional noise / signal separation techniqueSingular Value DecompositionDecompose observation X= X=USVT Sis a diagonal matrix of singular values with elements arranged in descending order of magnitude (the singular spectrum) The columns of Vare the eigenvectors of C=XTX(the orthogonal subspace ..dot(vi,vj)=0 ) .. they demix or rotate the data Uis the matrix of projections of Xonto the eigenvectors of C.

5 The Source estimates5 Singular Value DecompositionDecompose observation X= X=USVTE igenspectrum of decomposition S= singularmatrix .. zeros except on the leading diagonal Sij(i=j) are the eigenvalues Placed in order of descending magnitude Correspond to the magnitude of projected data along each eigenvector Eigenvectors are the axes of maximal variation in the dataVariance = power (analogous to Fourier components in power spectra)[stem(diag(S).^2)]Eigenspectrum= Plot of eigenvaluesSVD: Method for PCA6 SVD noise/signal separationTo perform SVD filtering of a signal, use a truncated SVD decomposition (using the first peigenvectors)

6 Y=USpVT[Reduce the dimensionality of the data by discarding noise projections Snoise=0 Then reconstruct the data with just the signal subsapce] Most of the signal is contained in the first few principal these and projecting back into the original observation space effects a noise-filtering or a noise/signal separationReal dataXXp= dimensional example7 IndependentComponent AnalysisAs in PCA, we are looking for Ndifferent vectors onto which we can project our observations to give a set of N maximally independent signals(sources) output data (discovered sources)

7 Dimensionality = dimensionality of observations Instead of using varianceas our independence measure ( decorrelating) as we do in PCA, we use a measure of how statistically independentthe sources : The basic idea ..Assume underlying Source signals (Z) are a linear mixing matrix (A)..XT=AZTin order to find Y( Z), find W, ( A-1) ..YT=WXTHow?Initialise W& iteratively update Wto minimise or maximise a cost function that measures the (statistical) independencebetween the columns of the statistical independence?From the Central Limit Theorem, - add enough independent signals together, Gaussian PDF Sources,ZP(Z) (subGaussian)Mixtures (XT=AZT)P(X) (Gaussian) Recap: Moments of a distribution9 Higher order moments (3rd -skewness) xHigher order moments (4th-kurtosis) xSuperGaussianSubGaussianGaussians are mesokurticwith =3 Non-Gaussianity statistical independence?

8 Central Limit Theorem: add enough independent signals together, Gaussian PDF make data components non-Gaussian to find independent sourcesSources,ZP(Z) ( <3 ( ) )Mixtures (XT=AZT)P(X) ( = ) ( =3)10 Recall trying to estimate WAssume underlying Source signals (Z) are a linear mixing matrix (A)..XT=AZTin order to find Y( Z), find W, ( A-1) ..YT=WXTI nitialise W& iteratively update Wwith gradient descent to maximise descent to find W Given a cost function, , we update each element of W ( ) at each step.

9 And recalculate cost function ( is the learning rate (~ ), and speeds up convergence.)wijW=[1 3; -2 -1]Iterationswij 105 Weight updates to find:(Gradient ascent)11 Gradient descentmin (1/| 1|, 1/| 2|) | = maxGradient Descent = min (1/| 1|, 1/| 2|) | = max Cost function, , can be maximum or minimum 1/ Gradient descent example Imagine a 2-channel ECG, comprised of two sources; Cardiac and SNR=1 X1X212 Iteratively update W and measure Y1Y2 Iteratively update W and measure Y1Y2 Iteratively update W and measure Y1Y214 Iteratively update W and measure Y1Y2 Iteratively update W and measure Y1Y2 Maximized for non-Gaussian signalY1Y215 Outlier insensitive ICA cost functionsIn general we require a measure of statistical independence which we maximise betweeneach of the is one approximation, but sensitive to small changes in the distribution tail.

10 Other measures include:Measures of statistical independence Mutual Information II, Entropy (Negentropy, JJ).. and Maximum (Log) Likelihood (Note: all are related to )Entropy-based cost functionKurtosis is highly sensitive to small changes in distribution tails. A more robust measures of Gaussianity is based on differential entropy H(y), ..negentropy:where ygaussis a Gaussian variable with the same covariance matrix as y. J(y) can be estimated from kurtosis ..Entropy: measure of randomness- Gaussians are maximally random16 Minimising Mutual InformationMutual information (MI) between two vectors xand y :always non-negative and zero if variables are independent.