Blind extraction of chaotic sources from mixtures

DigitalSignalProcessing???(????)???–

???

ContentslistsavailableatScienceDirect

DigitalSignalProcessing

http://wendang.chazidian.com/locate/dsp

Blindextractionofchaoticsourcesfrommixtureswithstochasticsignalsbasedonrecurrencequanti?cationanalysis

DiogoC.Sorianoa,c,?,RicardoSuyamab,RomisAttuxa,c

DepartmentofComputerEngineeringandIndustrialAutomation(DCA),SchoolofElectricalandComputerEngineering(FEEC),UniversityofCampinas(UNICAMP),C.P.6101,ZIPCODE13083-970,Campinas,SP,Brazilb

CentrodeEngenharia,ModelagemeCiênciasSociaisAplicadas,UniversidadeFederaldoABC(UFABC),SantoAndré,SP,Brazilc

LaboratoryofSignalProcessingforCommunications,SchoolofElectricalandComputerEngineering(FEEC),UniversityofCampinas(UNICAMP),C.P.6101,ZIPCODE13083-970,Campinas,SP,Brazil

a

article

Articlehistory:

Availableonlinexxxx

infoabstract

Thisworkaimstopresentanewmethodtoperformblindextractionofchaoticdeterministicsourcesmixedwithstochasticsignals.Thistechniqueemploystherecurrencequanti?cationanalysis(RQA),atoolcommonlyusedtostudydynamicalsystems,toobtaintheseparatingsystemthatrecoversthedeterministicsource.ThemethodisappliedtoinvertibleandunderdeterminedmixturemodelsconsideringdifferentstochasticsourcesanddifferentRQAmeasures.Abriefdiscussionaboutthein?uenceofrecurrenceplotparametersontherobustnessoftheproposalisalsoprovidedandillustratedbyasetofrepresentativesimulations.

©2011ElsevierInc.Allrightsreserved.

Keywords:

ChaoticsignalsBlindextraction

Blindsourceseparation

Recurrencequanti?cationanalysis

1.Introduction

Dynamicalsystemscanbedescribedintermsofastatemap-pingcommonlyde?nedbyasetofdifferentialequations.Whenthismappingiscomposedofnonlinearfunctions,averyrichdy-namicalscenariocanoccur,whichincludesconvergenceto?xedpoints,existenceoflimit-cycles,quasi-periodicityandchaos.In-deed,chaoticoscillationsarepresentinmanyphysicalsystems(e.g.biological,mechanicalandelectronic),whichisjusti?edbytherelevancetothestudyofnaturalphenomenaofnonlinearpro-cesseslikecooperation,competition,saturationandhysteresis,justtociteafew.Chaoticbehaviorisassociatedwithfeaturesasape-riodicity,broadbandspectrumandsensitivitytoinitialconditions,aspectsthatcanbeeasilyconfusedwithcharacteristicsofrandomprocesses[1,2].

Infact,distinguishingchaoticfromrandomsignalsisafarfromtrivialtask,especiallywhenexperimentaltimeseriesimmersedinnoiseareconsidered[2–5].Themostcommonapproachistoeval-uatetheKolmogorov–Sinai(KS)entropybycalculatingitslowerboundgivenbythecorrelationentropy(K2)[6].Ingeneral,thisquantityiszeroforperiodicsignals,?niteandpositiveforchaoticprocessesandtendstoin?niteforrandomsignals[2,7],althoughsomestochasticprocessescharacterizedbyapowerlawspectrumcanbecitedasexceptions,providinga?niteandpositivevaluefortheK2entropy[2].Moreover,invariantmeasuresthatchar-

Correspondingauthorat:DepartmentofComputerEngineeringandIndustrialAutomation(DCA),SchoolofElectricalandComputerEngineering(FEEC),UniversityofCampinas(UNICAMP),C.P.6101,ZIPCODE13083-970,Campinas,SP,Brazil.

E-mailaddress:soriano@dca.fee.unicamp.br(D.C.Soriano).1051-2004/$–seefrontmatterdoi:10.1016/j.dsp.2010.12.003

*

acterizechaoticdynamicalsystems(astheK2entropy,Lyapunovexponents,correlationdimensions,amongothers)arestronglyaf-fectedbynoiseinpractice,whichmakestheircalculationfromexperimentaltimeseriesunstableorunreliable[1].Inthiscase,itiscertainlyofgreatusetoemployapreprocessingstageinordertoenhance,forinstance,thedeterministicfeaturesofthesignal.Unfortunately,the?lteringprocessbasedontheclassicalFourierapproachcancausethelossofrelevantinformation[1,8–10],sincebothsignals(chaoticandrandom)haveabroadbandspectrum.Inthiscontext,thechallengingproblemofdenoisingchaotictimese-rieshasbeenaddressedinseveralworks[11–15].Generally,thesemethodsconstrainthereconstructedstatevectortofallontogeo-metricalobjectsthatarelocallylinear(orhigher-orderpolynomialmaps)[1,10],assumingthatthedeterministiccomponentliesonasmoothsubmanifold(see[9,10]forinterestingreviews),whichmakespossibletoachievethetrajectorygeneratedbythedynam-ics,reducingnoisebyaniterativeprocess.

Fromatheoreticalstandpoint,ifmoreinformationisavailable(which,inthiswork,meansthatmorethanonemixtureofthechaoticandnoisesourcescanbeavailable),denoisingchaotictimeseriescanbetreatedwithintheframeworkoftheblindsourceex-traction(BSE)problem,asitisconcernedwithrecoveringaspeci?csetofsignalsofinterest–usuallythedeterministicsignals–fromversionsinwhichtheyaremixedwithstochasticsources.Anatu-ralpossibilitytosolvethisproblemwouldbetoemployaclassicalblindseparationapproachsuchasthewell-establishedindepen-dentcomponentanalysis(ICA)[16,17],althoughitwouldnotbecapableofexploringthepeculiarfeaturesoftheproblem,partic-ularlythefactthatsomesignalsaregeneratedbyadeterministicdynamicalsystem.Asamatteroffact,thisisaninstanceinwhich

©

2011ElsevierInc.Allrightsreserved.

2

D.C.Sorianoetal./DigitalSignalProcessing???(????)???–

???

Fig.1.Panels(a),(b),(c),(d),show,respectively,therecurrenceplots(N=1000samples,de=3,τ=3,ε=0.5)fromaperiodicoscillation(sin(10t)),achaoticLorenztimeseries,agaussianrandomsource(zeromeanandunitaryvariance)andamixtureofrandomandchaoticsources.

aprioriinformationaboutthesourcesisavailable,whichisalwayssomethingthatwidenstheapplicabilityofblindsignalprocess-ing(researchareassuchassparsecomponentanalysisattestthisfact[18]).

Inthiswork,amethodforsolvingtheBSEproblemwhenchaoticandstochasticprocessesaremixedispresented.Thetech-niqueexploresthedynamicfeaturesunderlyingthegenerationofthechaoticsourcestorecoverasignalthatis“asdeterministicaspossible”.Thesolutionemploysarecurrenceplot,aclassicaltoolfornonlinearanalysisofdynamicalsystems[19,20],tobuildscorefunctionsbasedonclassicalestimatorsgivenbyrecurrencequan-ti?cationanalysis(RQA)[21].Thesescorefunctionsareusedtoadaptlinearseparatingsystemsunderdifferentsignalandmixturemodels(invertibleandunderdetermined),andacomparisonwithaclassicalICAmethodologyisestablished.

Thisworkisorganizedasitfollows:inSection2,abriefintro-ductiontochaoticsignalsandRQAisgiven.Section3presentstheBSEproblemanditsrelationtotheproposedapproachtoextractdeterministicsources.Section4isdedicatedtoshowingtheresultsobtainedforaperfectinvertiblescenario(inwhichafullrankmix-ingmatrixisconsidered),toanalyzingtheroleofrecurrenceplotparametersintheextractionprocedure,and?nally,topresentingtheperformanceofthemethodintheunderdeterminedcase(inwhichtherearemoresourcesthanmixtures).Section5presentsadiscussionaboutthecontributionsandperspectivesofapplica-tionoftheproposedmethodinviewofwhathasalreadybeenexposedintheliterature.TheideaofextractionofchaoticsourcesusingRQAwasintroducedbythepresentauthorsinapreviouswork([22])andtestedforalimitedsetofsimulations.ThepresentworkextendstheproposalbytakinginaccountdifferentstochasticsourcesandmixingmodelsconsideringthreeclassicalRQAmea-

sures,andalsobyanalyzingtheroleofrecurrenceplotparametersontheextractionprocedure.

2.Chaoticsignalsandgenerationofrecurrenceplots

Informalterms,achaoticsignalisde?nedasacontinuous-valuedsignalwith?niteandpositiveentropyrateandin?niteredundancyrate[7].Forourpurposes,achaoticsignalshouldbesimplyunderstoodasonegeneratedbyachaoticsystem,whichmeansthatitspropertiesarede?nedbythedynamicsthatgener-atesitandthebehaviorofitstrajectoriesinthephasespace.Inordertoreconstructtheunderlyingattractor(thesolutionofthedynamicalequationsinthephasespace)fromasingleobservedsignal(thatis,fromasinglestatevariable)onecanapplytheTak-ens’embeddingtheorem[1],de?ningastatevectorx(k)suchthat:

x(k)=x(k)

??

x(k?τ)...

xk?(de?1)τ

??????

(1)

wherederepresentstheembeddingdimension–de?nedasthenumberofcoordinatesthatunfoldstheattractor–andτrepre-sentsthedelaybetweensamples.Eventhoughthistrajectorymaynotbeexactlythesameasthatgeneratedbythesystem,itwillbetopologicallyequivalentthereto[1].

Afterthereconstruction,itispossibletocharacterizetheat-tractorwiththeaidofitsrevisitedstates,whichcanbedonewitharecurrenceplot,ausefulgraphicaltoolfornonlinearanalysisofdynamicalsystems?rstproposedin[http://wendang.chazidian.comingthereconstructedstatex(k),therecurrencemapwillberepresentedbyanN×Nmatrix,wheretheelement(i,j)willbeablackdotwheneverx(i)issu?cientlyclosetox(j),i.e.,whenever??x(i)?x(j)??<ε.

Thecharacterizationandapplicabilityofrecurrenceplotsbe-comesclearbycomparingmapsobtainedfromsignalsofdifferent

D.C.Sorianoetal./DigitalSignalProcessing???(????)???–???

3

natures.InFig.1,mapsgeneratedfromaperiodicsignal(Fig.1(a)),achaoticsignal(Fig.1(b)),arandomsignal(Fig.1(c))andamix-tureofchaoticandrandomsignals(Fig.1(d))arepresented.Thepatternsclearlydifferintheirstructureandtheirregularity.Infact,theseaspectsproviderelevantinformationaboutthedynam-icalbehavior.Forinstance,segmentsparalleltothemaindiagonalconsistinpointscloseintime,capturingacorrelationcharacteris-ticthatisinherenttoadeterministicprocessandisnotnecessarilyvalidforstochasticprocesses.Verticalorhorizontallinesrevealstatesthatdonotchangeintime[20],whilefadingtothecor-nerscanbeusedtoidentifynonstationarysignals.

Acrucialpointisthatchaotictimeseriestendtogenerateshorterdiagonalsthanthoseassociatedwithperiodicsignals,butlongerthanthoseassociatedwitharandomprocess,ascanbeob-servedinFig.1.Thissuggeststhatstatisticsbasedinthestructureofdiagonalsinarecurrenceplotcanbeusedtode?necontrastfunctionstoseparatedeterministicfromrandomsignals.Thesecontrastscanbebuiltfromclassicalrecurrencemeasures[21,4,20]likethepercentageofdeterminism(?td),theentropyofdiagonals(?te)andthelongestdiagonal(?tl)foundinthemap.Formally,ifP(ε,l)isde?nedasthefrequencydistributionoflinelengthslforamapwithresolutionε,thescorefunctionassociatedwiththedeterministiccontentinawindowofdiagonallengthsatobcanbemathematicallydescribedas:

Fig.2.Schemeforblindextractionproblem,sc(n)isthechaoticsource,ss(n)isthestochasticsource,x1(n)andx1(n)aretheobservedmixtures,Aisthemixingmatrix,wistheseparatingvectorandy1(n)therecoveredchaoticsignaluptoscalingfactorG.

ICAapproacheslookforsolutionsinθthatensure,forinstance,maximalnongaussianity,whichcanbeevaluatedwiththeaidofthekurtosisoftheoutputcomponents,or,alternatively,max-imizationofindependencebetweentheelementsoftheoutputvectory(n)=[y1(n)y2(n)]T=Wx(n)(e.g.byminimizingamu-tualinformationmeasure),beingWtheseparatingmatrixgiven

??cosθsinθ??by.Wehaveconsideredheretheclassicalkurtosis

?sinθcosθ

(?tk)andmutualinformation(?tm)scorefunctions,asde?nedin[16,17]:

????2

?3Ey1(n)2

????????

?tm=Hy1(n)?Hy1(n)|y2(n)

?tk=Ey1(n)

????4

(5)(6)

?td=

l=b??l=a

l=N????lP(l)lP(l)

l=1

(2)

Thescorefunctionrelatedtothelongestdiagonalline(exclud-ingthemaindiagonal)foundinthemapcanbede?nedas:

l

?tl=max{li}i=1

??

N

??

(3)

whereNlisthetotalnumberofdiagonallines(excludingthemainone).Finally,toourpurpose,thescorefunctionassociatedwiththeShannonentropyassociatedwiththeprobabilityp(l)=P(l)/Nlof?ndingadiagonaloflengthlisde?nedby:

?te=?

Nl??l=lmin

p(l)lnp(l)

????

(4)

andisrelatedtoameasureofcomplexityoftherecurrenceplot(e.g.uncorrelatednoisehasasmall?te,re?ectinglowcomplexity).Thethresholdlminexcludesthediagonallineswhichareformedbytangentialmotionofphasespacetrajectories[20].

3.Theblindsourceextractionproblem(BSE)inthecontextofdeterministicsignals

Letusconsiderthattwosources–onebeingachaoticsignalsc(n)andtheotherbeingastochasticsignalss(n)–arelinearlymixed,givingrisetox(n)=As(n),wherex(n)=[x1(n)x2(n)]Tisthemixturevector,Aisthe2×2mixingmatrix(whichisas-sumedtohavefullrank)ands(n)=[s1(n)s2(n)]Tisthesourcevector.Theaimofblindsourceextraction(BSE)istoextractasourcefromthemixtureswithouttheneedforareferencesig-nalorknowledgeofcoe?cientsofthemixingmatrix.Thistaskcanbeachievedbymultiplyingthemixturevectorbyanade-quatelychosenseparatingvectorw,sothattheoutputvectoryield,forinstance,y(n)=wTx(n)=Gsc(n),whereGisascalingfactor.Fig.2showsaschemethatrepresentsthedescribedblindextrac-tionproblem.

Letusalsoassume,withoutlossofgenerality,thatthemix-ingmatrixisorthogonal(thiscanbeachievedviaawhiteningprocedure),and,asaconsequence,wcanbeparameterizedintermsofasinglevariableθ,i.e.,w=[cosθsinθ]T.

Classical

wheretheoperatorE{α}isthestatisticalexpectationoftheran-domvariableαandH{α}istheShannondifferentialentropy[23]ofα.Inparticular,toevaluate(6)wehaveusedthemutualin-formationestimatorprovidedby[24],sinceitise?cientandfast.Finally,itisalsoimportanttoremarkthatICAallowstherecoveryoftheoriginalsourcesuptoscaleandpermutationambiguities[16,17].

However,whenitisknownthatoneofthesourcesis,forexam-ple,adeterministicchaoticsignal,itispossibletoobtainthesepa-ratingvectorbasedonthemaximizationofthedeterministicchar-acteroftheoutputvector,inconsonancewithwhatwaspresentedinSection2,withtheaidofthescorefunctionsprovidedbyRQA.Animmediateconsequenceisthatthepermutationambiguityshouldnotexist,atleastinitsoriginalform,sincethemeasurewillestablishadifferencebetweendeterministicandstochasticsources.

Inverysimpleterms,wewillusethefactthat“longandor-ganizeddiagonals”tendtocharacterizedeterministicbehaviortobuildcostfunctionscapableofdiscriminatingbetweensignalsofdifferentnatures.Therationaleisthatstructured“longdiagonals”,inacertainsense,areindicativeoftemporalandspatialcorrela-tioncausedbythedeterministicgenerativelawunderlyingsc(n),whereasthesamedoesnothold,byde?nition,forarandomsignal.Thereaderinterestedinamoreformalpresentationofrecurrenceplotsandoftheirrelationshipwithinformation-theoreticmeasuresisreferredto[20].

Intheexposedmethodology,weaimto?ndthevalueofθthatprovidestheseparatingvectorwthatmaximizesthescorefunc-tionsshowninEqs.(2),(3)and(4),basedontherecurrenceplotofy(n),whichshouldyieldthe“mostdeterministic”output.4.Results

4.1.BlindextractionofchaoticsourcesinainvertiblemixturescenarioInordertoanalyzethevalidityoftheproposedmethodology,weshallturnourattentiontodistinctrepresentativesimulationscenarios.Inallcases,wewillconsidersc(n)tobethe?rststatevariableoftheemblematicLorenzsystem[1](preprocessedtohavezeromeanandunitvariance)anddifferentstochasticss(n)sources(whitegaussian,whiteuniformandcoloredgaussianpro-cesseswithzeromean).Thesechoicesweremadeafterasequenceofinitialtests,althoughtheyarebynomeansmandatory:testswithotherchaoticsystems(e.g.theRösslerdynamicalsystemandthelogisticmap)ledtosimilarresults.

4

D.C.Sorianoetal./DigitalSignalProcessing???(????)???–

???

Fig.3.Upperpanel–deterministiccontent(?td)ofy1(n),longestdiagonal(?tl)ofy1(n)andentropyofdiagonallines(?te)ofthemapfordifferentθvalues(N=1000,de=3,τ=3,ε=0.1,a=40,b=60,lmin=2).Thestochasticsourceisawhitegaussiansignal10dBbelowthechaoticsourceinpower.Lowerpanel–kurtosisofy1(n)–(?tk)–andmutualinformation

Fig.4.ThesamesimulationperformedinFig.3isrepeatedincreasingthenoisepower(ss(n))toaSNRof2dBbelowthechaoticsource.

Inthe?rstscenario,awhitegaussianprocess(10dBbe-lowthechaoticsourceinpower)andafullrankmixingmatrix??sinθ?cosθ??

,withθ=π/6areconsidered.Inordertorecoverthe

cosθsinθ

chaoticsource,theextractingvectorwshouldbechosensuchthaty1(n)=wTx(n)beasdeterministicaspossible,whichmeansthatθshouldmaximize(2),(3)and(4).InFig.3,wepresentthevaluesoftheproposedscorefunctionsandalsooftwocommonlyusedICAcontrasts:thekurtosisofy1(n)andthemutualinformationbetweeny1(n)andy2(n),asrespectivelyde?nedin(5)and(6).Inthecasestudiedhere,thesolutioninθthatmaximizes(2),(3),(4)and(5)andminimizes(6)canbefoundbyperforminganexhaus-tivesearchinthisparameter(whichimpliesinvaryingθfrom0toπ)forevaluatingtherespectivescorefunctions.Forsituationswherealargenumberofsourcesareconsidered,thenumberofparametersintheseparatingsystemincreases,and,inthiscase,itwouldbebettertoemploymoresophisticatedoptimizationtech-niqueswithlowercomputationalcost.Forreadersinterestedinthisscenariowestronglyrecommend[17]foradiscussionofthesemethods.

Itisalsoimportanttonoticethat,inordertoanalyzeheretheperformanceofthemutualinformationcontrast,itwasnecessarytoleavetheextractionframeworkanddealwithablindsourceseparation(BSS)problem,sinceitrequirestherecoveryofbothsourcesy1(n)andy2(n).

The?rstimportantconclusionisthattheestimatorsbasedontherecurrencestatisticshaveglobaloptimaatthesolutionsthatleadtoperfectinversion(uptoasignambiguity),afeaturesharedbymethodsbasedonkurtosisandmutualinformation.Thesere-sultsrevealthattheproposalful?lledtheessential“soundnessre-quirements”ofaseparationmethodandhadaperformanceequiv-alenttothatobtainedviaclassicalICAmethods.Itisinterestingtoobservethatthescorefunctions(2),(3)and(4)haveabetterper-formancewhenthenoisepowerisincreased(theSNRisreducedfrom10to2dB),whichisnotnecessarilyvalidforclassicalICAmeasures[25].ThissituationisillustratedinFig.4,fromwhichitcanbeinferred,interalia,thattheminimumvalueofthemu-tualinformationestimatedoesnotseemtobeareliablecriterion,sincethereisnotawell-de?nedminimumobtainedbythisscorefunction.

Toillustratethepotentialoftheproposedmethod,Fig.5showsthetimeseriesobtainedwhenthesolutionthatinvertsthemixingprocessisadoptedinthesimulationscenarioofFig.4.TheupperpanelofFig.5showstheoriginalchaoticsource,themiddlepanelshowsoneoftheobservedmixtureswithaSNRof2dBandthelowerpanelsshowstherecoveredchaoticsource.Itispossibletoobservethatafteradaptingtheseparatingsystemwiththesolutionthatmaximizes(2),(3)and(4)therecoveredchaoticsourceisverysimilartotheoriginalone,whichisaconsequenceoftheperfectinversionofthemixingprocess.

Whenthesamesimulationisperformedconsideringthestochasticsourcetobeawhiteuniformly-distributedsignal,itispossibletoverifythattheproposedrecurrence-basedscorefunc-

内容需要下载文档才能查看

5

Fig.5.Theupper

thelowerpanelshowstherecoveredFig.6.Upperpanel–deterministiccontent(?td)ofy1(n),longestdiagonal(?tl)ofy1(n)andentropyofdiagonallines(?te)ofthemapfordifferentθvalues(N=1000,de=3,τ=3,ε=0.1,a=40,b=60,lmin=3).Thestochasticsourceisawhiteuniformsignal2dBbelowthechaoticsourceinpower.Lowerpanel–kurtosisofy1(n)–(?tk)–andmutualinformationbetweeny1(n)andy2(n)–(?tm)–fordifferentθvalues.

tionsarestillcapableofleadingtoinversionofthemixingmatrix(upperpanelinFig.6).Nevertheless,itcanbenotedfromthelowerpanelinFig.6thatthemixtureofachaoticsourcewithauniformnoiseposesamoredi?culttaskforanICAapproach.Inthiscase,maximizingthenongaussianityofy1(n)doesnotleadtorecoveryofthechaoticsource(asitisalsoobservedforthemin-imizationofmutualinformation).Indeed,[25]haspointedthatsub-gaussiannoiseasthatemployedinthiscasecanbeseparatedviaICA(usingFastICAalgorithm)iftheSNRishigherthan5dB,whichdoesnotseemtobearestrictionfortherecurrencefunc-tions.

Thetime-seriesinthissetofsimulationswereomittedhereforsakeofconciseness,sincethemixingmatrix,theoriginalchaoticsourceandtherecoveredchaoticsignal(asshowninFig.5)havenotbeenchangedwhenadaptingtheseparatingsystemusingrecurrence-basedscorefunctions.

SinceRQAisbasedoncorrelationcharacteristicsde?nedbyarecurrencemap,aninterestingandchallengingsituationtotheproposedextractionmethodwouldappearifwetriedtosepa-ratechaoticandstochasticsourceswiththesamesecond-orderautocorrelationcharacteristics.Chaotictimeseriesdisplaysanex-ponentialdecayintheautocorrelationfunctionrelatedtothepres-enceofatleastonepositiveLyapunovexponent[1].Thisautocor-relationbehaviorcanbegeneratedby?lteringawhitegaussianprocessusingtheauto-regressiveYule-Walkerframework[26],inordertoobtainacoloredgaussiannoisewithcorrelationcharac-teristicssimilartothoseofthechaoticsignal(Fig.7(a)).Itisinter-estingtoobservethatthegeneratedstochasticsourceresemblesthechaotictimeseriesinsometimeintervals(Fig.7(b)),which