A Very Short Introduction to Blind Source Separation

1 A Very Short Introduction to Blind How You Will Definitively Enjoy Differently a Cocktail PartyMatthieu PuigtFoundation for Research and Technology HellasInstitute of Computer 12 / May 3, 2011M. PuigtA very Short Introduction to BSSA pril/May 20111 Let s talk about linear systemsAll of you know how to solve this kind of systems:{2 s1+3 s2=53 s1 2 s2=1(1)If we resp. defineA,s, andxthe matrix and the vectors:A=[233 2],s= [s1,s2]T, andx= [5,1]TEq. (1) beginsx=A sand the solution reads:s=A 1 x= [1,1]THow can we solve this kind of problem???This problem is calledBlind Source PuigtA very Short Introduction to BSSA pril/May 20112 Let s talk about linear systemsAll of you know how to solve this kind of systems:{? s1+? s2=5? s1+? s2=1(1)If we resp. defineA,s, andxthe matrix and the vectors:A=[? ?? ?],s= [s1,s2]T, andx= [5,1]TEq. (1) beginsx=A sand the solution reads:s=A 1 x=?How can we solve this kind of problem?}}

2 ??This problem is calledBlind Source PuigtA very Short Introduction to BSSA pril/May 20112 Let s talk about linear systemsAll of you know how to solve this kind of systems:{a11 s1+a12 s2=5a21 s1+a22 s2=1(1)If we resp. defineA,s, andxthe matrix and the vectors:A=[a11a12a21a22],s= [s1,s2]T, andx= [5,1]TEq. (1) beginsx=A sand the solution reads:s=A 1 x=?How can we solve this kind of problem???This problem is calledBlind Source PuigtA very Short Introduction to BSSA pril/May 20112 Blind Source Separation problemNunknown unknown signalsxiwith the global relationx=A(s).Goal:Estimating the vectors, up to some indeterminacies."blibla""blabli"Observat ionsxi(n)"blabla""blibli"Sourcessj(n)Sep arationOutputsyk(n)"blabla""blibli"M. PuigtA very Short Introduction to BSSA pril/May 20113 Blind Source Separation problemNunknown unknown signalsxiwith the global relationx=A(s).Goal:Estimating the vectors, up to some indeterminacies.}

3 "blibla""blabli"Observationsxi(n)"blabla ""blibli"Sourcessj(n)SeparationOutputsyk (n)Permutation"blibli""blabla"M. PuigtA very Short Introduction to BSSA pril/May 20113 Blind Source Separation problemNunknown unknown signalsxiwith the global relationx=A(s).Goal:Estimating the vectors, up to some indeterminacies."blibla""blabli"Observat ionsxi(n)"blabla""blibli"Sourcessj(n)Sep arationOutputsyk(n)Scale or filter factor"blabla""blibli"M. PuigtA very Short Introduction to BSSA pril/May 20113 Most of the approaches process linear mixtures which are divided in threecategories:1 Linear instantaneous (LI) mixtures:xi(n) = Nj=1aijsj(n)(Purpose ofthis lecture)2 Attenuated and delayed (AD) mixtures:xi(n) = Nj=1aijsj(n nij)3 Convolutive mixtures:xi(n) = Nj=1 + k= aijksj(n nijk) = Nj=1aij(n) sj(n)M. PuigtA very Short Introduction to BSSA pril/May 20114 Most of the approaches process linear mixtures which are divided in threecategories:1 Linear instantaneous (LI) mixtures:xi(n) = Nj=1aijsj(n)(Purpose ofthis lecture)2 Attenuated and delayed (AD) mixtures:xi(n) = Nj=1aijsj(n nij)3 Convolutive mixtures:xi(n) = Nj=1 + k= aijksj(n nijk) = Nj=1aij(n) sj(n)x1(n)x2(n)s1(n)s2(n)M.

4 PuigtA very Short Introduction to BSSA pril/May 20114 Most of the approaches process linear mixtures which are divided in threecategories:1 Linear instantaneous (LI) mixtures:xi(n) = Nj=1aijsj(n)(Purpose ofthis lecture)2 Attenuated and delayed (AD) mixtures:xi(n) = Nj=1aijsj(n nij)3 Convolutive mixtures:xi(n) = Nj=1 + k= aijksj(n nijk) = Nj=1aij(n) sj(n)x1(n)x2(n)s1(n)s2(n)M. PuigtA very Short Introduction to BSSA pril/May 20114 Most of the approaches process linear mixtures which are divided in threecategories:1 Linear instantaneous (LI) mixtures:xi(n) = Nj=1aijsj(n)(Purpose ofthis lecture)2 Attenuated and delayed (AD) mixtures:xi(n) = Nj=1aijsj(n nij)3 Convolutive mixtures:xi(n) = Nj=1 + k= aijksj(n nijk) = Nj=1aij(n) sj(n)x1(n)x2(n)s1(n)s2(n)M. PuigtA very Short Introduction to BSSA pril/May 20114 Let s go back to our previous problemA kind of magic?Here, the operator is a simple matrix whose coefficients are unknown.

5 {a11 s1+a12 s2=5a21 s1+a22 s2=1In Signal Processing, we do not have the unique above system ofequation but aseriesof such systems (due tosamples)We thus use the intrinsic properties of Source signals to achieve theseparation (assumptions)M. PuigtA very Short Introduction to BSSA pril/May 20115 Let s go back to our previous problemA kind of magic?Here, the operator is a simple matrix whose coefficients are unknown.{a11 s1+a12 s2=0a21 s1+a22 s2=.24In Signal Processing, we do not have the unique above system ofequation but aseriesof such systems (due tosamples)We thus use the intrinsic properties of Source signals to achieve theseparation (assumptions)M. PuigtA very Short Introduction to BSSA pril/May 20115 Let s go back to our previous problemA kind of magic?Here, the operator is a simple matrix whose coefficients are unknown.{a11 s1+a12 s2=4a21 s1+a22 s2= 2In Signal Processing, we do not have the unique above system ofequation but aseriesof such systems (due tosamples)We thus use the intrinsic properties of Source signals to achieve theseparation (assumptions)M.}}}

6 PuigtA very Short Introduction to BSSA pril/May 20115 Let s go back to our previous problemA kind of magic?Here, the operator is a simple matrix whose coefficients are unknown.{a11 s1(n)+a12 s2(n) =x1(n)a21 s1(n)+a22 s2(n) =x2(n)In Signal Processing, we do not have the unique above system ofequation but aseriesof such systems (due tosamples)We thus use the intrinsic properties of Source signals to achieve theseparation (assumptions)M. PuigtA very Short Introduction to BSSA pril/May 20115 Three main families of methods:1 Independent Component Analysis (ICA):Sources are statisticallyindependent, stationary and at most one of them is Gaussian (in theirbasic versions).2 Sparse Component Analysis (SCA):Sparse sources ( most of thesamples are null (or close to zero)).3 Non-negative Matrix Factorization (NMF):Both sources et mixturesare positive, with possibly sparsity PuigtA very Short Introduction to BSSA pril/May 20116A bit of history (1)BSS problem formulated around 1982, by Hans, H rault, and Jutten fora biomedical problem and first papers in the mid of the 80 sGreat interest from the community, mainly in France and later inEurope and in Japan, and then in the USAS everal special sessions in international conferences ( GRETSI 93,NOLTA 95, etc)First workshop in 1999, in Aussois, France.}

7 One conference each 18months ( ) and nextone in 2012 in Tel Aviv, Israel In June 2009, 22000 scientific papers are recorded by Google Scholar (Comon and Jutten, 2010)People with different backgrounds: signal processing, statistics, neuralnetworks, and later machine learningInitially, BSS addressed for LI mixtures butconvolutive mixtures in the mid of the 90 snonlinear mixtures at the end of the 90 sUntil the end of the 90 s, BSS'ICAF irst NMF methods in the mid of the 90 s but famous contribution in 1999 First SCA approaches around 2000 but massive interest sinceM. PuigtA very Short Introduction to BSSA pril/May 20117A bit of history (2)BSS on the web:Mailing list in ICA Central: softwares available in ICA Central, ICALab( ), NMFLab( ), challenges:12006 Speech Separation Challenge ( )22007 MLSP Separation Evaluation Campaigns in 2007, 2008, 2010, and 2011( )42011 Pascal CHIME Speech Separation and recognition ( )A generic problemMany applications: biomedical, audio processing and audio coding,telecommunications, astrophysics, image classification, underwateracoustics, finance, PuigtA very Short Introduction to BSSA pril/May 20118 Content of the lecture1 Sparse Component Analysis2 Independent Component Analysis3 Non-negative Matrix Factorization?

8 Some good documentsP. Comon and C. Jutten:Handbook of Blind Source component analysis and applications. Academic Press(2010)A. Hyv rinen, J. Karhunen, and E. Oja:Independent ComponentAnalysis. Wiley-Interscience, New York (2001)S. Makino, Lee, and H. Sawada: Blind Speech Separation . Signalsand Communication Technology, Springer (2007)Wikipedia: online PuigtA very Short Introduction to BSSA pril/May 20119 Part ISparse Component Analysis3 Sparse Component Analysis4 Increasing sparsity of Source signals5 Underdetermined case6 ConclusionM. PuigtA very Short Introduction to BSSA pril/May 201110 Let s go back to our previous problemWe said we have a series of systems of equations. Let s denotexi(n)andsj(n)(1 i j 2) the values that take both Source and observation signals.{a11 s1(n0)+a12 s2(n)=x1(n0)a21 s1(n0)+a22 s2(n)=x2(n0)SCA methods main ideaSources are sparse, often assume thata116=0 and thata126=0We thus have a lot of chances that for one given indexn0, one Source (says1(n0)) is the onlyactivesource.}

9 In this case, the system is we compute the ratiox2(n0)x1(n0), we obtain:x2(n0)x1(n0)=a21 s1(n0)a11 s1(n0)=a21a11 Instead of[a11,a21]T, we thus can estimate[1,a21a11]TLet us see why!M. PuigtA very Short Introduction to BSSA pril/May 201111 Let s go back to our previous problemWe said we have a series of systems of equations. Let s denotexi(n)andsj(n)(1 i j 2) the values that take both Source and observation signals.{a11 s1(n0)+a12 s2(n)=x1(n0)a21 s1(n0)+a22 s2(n)=x2(n0)SCA methods main ideaSources are sparse, often assume thata116=0 and thata126=0We thus have a lot of chances that for one given indexn0, one Source (says1(n0)) is the onlyactivesource. In this case, the system is we compute the ratiox2(n0)x1(n0), we obtain:x2(n0)x1(n0)=a21 s1(n0)a11 s1(n0)=a21a11 Instead of[a11,a21]T, we thus can estimate[1,a21a11]TLet us see why!M. PuigtA very Short Introduction to BSSA pril/May 201111 Let s go back to our previous problemWe said we have a series of systems of equations.}

10 Let s denotexi(n)andsj(n)(1 i j 2) the values that take both Source and observation signals.{a11 s1(n0)+a12 s2(n)=x1(n0)a21 s1(n0)+a22 s2(n)=x2(n0)SCA methods main ideaSources are sparse, often assume thata116=0 and thata126=0We thus have a lot of chances that for one given indexn0, one Source (says1(n0)) is the onlyactivesource. In this case, the system is we compute the ratiox2(n0)x1(n0), we obtain:x2(n0)x1(n0)=a21 s1(n0)a11 s1(n0)=a21a11 Instead of[a11,a21]T, we thus can estimate[1,a21a11]TLet us see why!M. PuigtA very Short Introduction to BSSA pril/May 201111 Imagine now that, for each Source , we have (at least) one sample(single-sourcesamples) for which only one Source is active:{a11 s1(n0)+a12 s2(n1)=x1(n)a21 s1(n0)+a22 s2(n1)=x2(n)(2)Ratiox2(n)x1(n)for samplesn0andn1 scaled version ofA, denotedB:B=[11a21a11a22a12]orB=[11a22a12 a21a11]If we express Eq. (2) in matrix form with respect toB, we read:x(n) =B [a11 s1(n)a12 s2(n)]orx(n) =B [a12 s2(n)a11 s1(n)]and by left-multiplying byB 1:y(n) =B 1 x(n) =B 1 B [a11 s1(n)a12 s2(n)]=[a11 s1(n)a12 s2(n)]ory(n) =B 1 x(n) =B 1 B [a12 s2(n)a11 s1(n)]=[a12 s2(n)a11 s1(n)]M.}}