ANOVELAPPROACHTOBLINDSOURCESEPARATIONANDEXTRACTIONIN
AUDIO
By
XunWang
ADISSERTATION
Submittedto
MichiganStateUniversity
inpartialentoftherequirements
forthedegreeof
AppliedMathematics|DoctorofPhilosophy
2015
ABSTRACT
ANOVELAPPROACHTOBLINDSOURCESEPARATIONAND
EXTRACTIONINAUDIO
By
XunWang
Inthisthesis,theblindsourceseparation(BSS)ondigitalaudiosignalsviabackground
learningbyseveraltmethodologiesiscarefullystudied.Inthedailyauditory,acoustic
audiosignalsareusuallymixturesoftsources,includingforegroundandbackground
noises.
Mostofthetime,weonlywanttoreceivetheforegroundsourcesandgetridofthe
backgroundones.Becauseoftherandomnessofvarioussituations,itisveryto
performthisseparationwithoutknowingthedetailedinformation.Evenifthebackground
noisesarenotdominatingtheforegroundsources,orevenmuchweaker,itisstilla
problem,especiallyforthecasethattherearemorethanthreesourcesincludingthenoise.
Thisalsomakesitevenmoretoseparatetsourcesfrommixedsignals.In
thisthesis,anovelapproachtosolvecancellationkernelsisprovidedbyusingamo
sigularvaluedecompositionmethod.Themainfocusistousethisnewtechniquetoestimate
thecacellationkernelswithgoodresultsinshortcomputationaltime.
Inthiswork,somebackgroundinformationforblindsourceseparationofaudiowillbe
introduced.Next,theknowledgeoffourtmethodsforsolvingthistypeof
problemsismentioned.SplitBregmanhasbeenstudiedbyothersinsolvingcancellation
kernelsfortheseparationofspeechsignals.Weapplyproximityoperatormethodtosolvethe
cancellationkernelsforBSSofaudiosignalprocessing.Ithasbeenappliedtostudyimage
processingbyotherresearchers.Quadraticprogrammingmethodhasbeenappliedtosolve
cancellationkernelsbyWangandZhou.Weprovideanewapproachtobringsparsenessto
cancellationkernelsbyusingquadraticprogramming.
Wedevelopedamosingularvaluedecomposition(SVD)algorithmbasedonthe
numericalexperiments.ItisanewtechniquetoestimatecancellationkernelsforBSSof
audiosignals.ThedetailedinformationandschemesarepresentedinChapter3.Then,in
thefouthchapter,therearetnumericalsimulationexamplesaccordingtot
scenarios.WecomparetheresultsofourmoSVDmethodwithothersmethods,and
concludethatourmoSVDisthebestapproach.
ToSihuaandmyparents
iv
ACKNOWLEDGMENTS
Iowemygreatgratitudetomytwoadvisors,Dr.YangWangandDr.ZhengfangZhou,
withoutwhomthisthesiswouldnothavebeenpossible.Theyintroducedmetotheof
mathematicsandsupportedmyworkintimesofchallengeandy.Theyarenotjust
myacademicadvisors,butalsolifementorswhomakemethepersonIamtoday.
Iwouldalsolovetoexpressmygratitudetomyotherthreecommitteemembers.Dr.
AndrewChristlieb,Dr.MarkIwen,andDr.Tien-YienLi.Theyhavesharedtheirgreat
wisdomwithmeandtakentimetogivemefeedbackonthisthesis.Isincerelyappreciate
thehelpfromDr.PeiruWu.Therearemanyfacultyandinthisgreatdepartmentthat
Iamgratefulto,fortheyprovidemerapportandencouragementthroughoutmyyearshere
atMichiganState.
Iwouldalsoliketothankmyfamilyfortheirunquestionableloveandsupport.Thank
youforbelievinginmeallthetime,andthankyoufornotgivingmepressurewhenIwas
atmylowpoint.
Lastbutnottheleast,somanythankstomydeargirlfriendSihuaHuwhoinspiresme
tomythesis.
v
TABLEOFCONTENTS
LISTOFFIGURES
...................................
viii
Chapter1Introduction
...............................
1
1.1BlindSourceSeparation.............................1
1.2MathematicalModelforBackgroundCancellation...............6
Chapter2BackgroundonPreviousWorkandNewApproach
.......
11
2.1ICAforBSS....................................11
2.2DUETforBSS..................................14
2.3CancellationKernels...............................17
2.4OptimizationMethods..............................18
2.4.1QuadraticProgramming.........................20
2.4.1.1TwoSourcesandTwoMixtures................21
2.4.1.2ThreeSourcesandThreeMixtures..............23
2.4.1.3IntroducingSparseness.....................26
2.4.2SplitBregmanMethod..........................28
2.4.2.1BregmanIteration.......................30
2.4.2.2ConstrainedOptimization...................31
2.4.2.3SplitBregman.........................32
2.4.3ProximityOperator............................34
2.4.3.1...........................34
2.4.3.2FixedPointAlgorithmBasedonProximityOperator....36
2.4.3.3Nonexpansivityof
H
......................38
2.4.3.4Algorithm............................40
2.4.4SingularValueDecomposition......................41
Chapter3TechnicalDiscussions
..........................
43
3.1Reviewofotheralgorithms............................43
3.1.1SplitBregmaniteration.........................43
3.1.1.1AlgorithmofSplitBregman..................43
3.1.1.2TwoSourcesandTwoMixtures................45
3.1.1.3ThreeSourcesandThreeMixtures..............47
3.1.1.4
n
sourcesand
n
mixtures...................49
3.1.2ProximityOperator............................50
3.1.2.1Algorithmofproximityoperator...............51
3.1.2.2ApplicationforBSSofAudioSignalProcessing.......52
3.1.2.3TwoSourcesandTwoMixturescase.............53
3.1.2.4ThreeSourcesandThreeMixturescase...........54
3.1.2.5
n
Sourcesand
n
Mixturescase................54
3.2QuadraticProgramming.............................54
vi
3.2.1AlgorithmforSparseness.........................54
3.3SingularValueDecomposition..........................56
3.3.1OurMethodology.............................56
3.3.2TwoSourcesandTwoMixtures.....................61
3.3.3ThreeSourcesandThreeMixtures...................62
3.3.4
n
Sourcesand
n
Mixtures........................62
Chapter4NumericalResults
...........................
63
4.1NumericalExampleofQuadraticProgramming................63
4.1.1NumericalExamplesofTwoSourcesandTwoMixtures........63
4.1.1.1Example1............................63
4.1.1.2Example2............................66
4.1.1.3Example3............................68
4.1.2NumericalExamplesofThreeSourcesandThreeMixtures......70
4.1.2.1Example4............................70
4.2NumericalExamplesofSVDMethod......................72
4.2.1TwoSourcesTwoMixturescase.....................73
4.2.1.1Example5............................73
4.2.1.2Example6............................74
4.2.2ThreeSourcesThreeMixtures......................76
4.2.2.1Example7............................76
4.2.2.2Example8............................77
4.3NumericalExamplesofSplitBregmanIteration................78
4.3.1Twosourcestwomixturescase.....................79
4.3.1.1Example9............................79
4.3.1.2Example10...........................79
4.3.2Threesourcesthreemixtures......................80
4.3.2.1Example11...........................80
4.3.2.2Example12...........................81
4.4NumericalExamplesofProximityOperatorMethod..............82
4.4.1Twosourcestwomixturescase.....................83
4.4.1.1Example13...........................83
4.4.1.2Example14...........................83
4.4.2ThreeSourcesThreeMixtures......................84
4.4.2.1Example15...........................84
4.4.2.2Example16...........................85
4.5Summarization..................................86
BIBLIOGRAPHY
....................................
88
vii
LISTOFFIGURES
Figure1:Plotof
f
1
˙
k
g
................................59
Figure2:Plotof
f
1
˙
k
g
withtangentline......................59
Figure3:Recordedmixturesandresultafterremovalofbackgroundmusic...64
Figure4:Cancelationkernels............................64
Figure5:Spectrogram................................65
Figure6:Recordedmixturesandresultafterremovalofbackgroundmusic...66
Figure7:Cancelationkernels............................67
Figure8:Spectrogram................................68
Figure9:mixturesandresultaftertheremovalofbackgroundsource.69
Figure10:Cancelationkernels............................69
Figure11:3mixturesandresultaftertheremovalofbackgroundsource.71
Figure12:Cancelationkernels............................72
Figure13:Recordedmixturesandresultsaftertheremovalofbackgroundsource.73
Figure14:Spectrogram................................74
Figure15:Recordedmixturesandresultsaftertheremovalofbackgroundsource.75
Figure16:Spectrogram................................75
Figure17:Recordedmixturesandresultsaftertheremovalofbackgroundsources.77
Figure18:Recordedmixturesandresultsaftertheremovalofbackgroundsources.78
Figure19:Recordedmixturesandresultaftertheremovalofbackgroundmusic.79
Figure20:Recordedmixturesandresultaftertheremovalofbackgroundmusic.80
viii
Figure21:Recordedmixturesandresultsaftertheremovalofbackgroundsources.81
Figure22:Recordedmixturesandresultsaftertheremovalofbackgroundsources.82
Figure23:Recordedmixturesandresultsaftertheremovalofbackgroundsource.83
Figure24:Recordedmixturesandresultsaftertheremovalofbackgroundsource.84
Figure25:Recordedmixturesandresultsafterremovalofbackgroundsources.85
Figure26:Recordedmixturesandresultsaftertheremovalofbackgroundsources.86
ix
Chapter1
Introduction
Theacousticsignalprocessingsystemhasbeenstudiedbyresearchersforseveraldecades.
Withintheresearchcommunity,peoplehaveachievedmanyremarkableresults,especially
inthepastdecade.Duringthisprocess,oneofthemajorgoalsistogettheestimationof
oneormoresourcesignalsasaccurateaspossible,oratleasttothelevelthatpeoplecould
toleratethenoise.Especiallynowadays,thehighperformancecomputingtechnologycan
rapidlyimplementalotofpreviouslytime-consumingmethods.
Foraudiorecordingmixtures,itisverytoseparatetsourcesignalsfrom
mixtures.Therearemanycausesfornoise,suchasaudiorecordingprocess,background
noisefromothersources,oraudiopropagation,andsoon.Theserandomoriginsmakeit
toconductnoiseremoval.Blindsourceseparationistheseparationofasetofsignals
fromthesetofmixedsignals,withouttheaidofinformation(orwithverylittleinformation)
aboutthesourcesignalsorthemixingprocess.Therearemanyapplicationsofblindsource
separationtomoderntechnology,suchasbiomedical,telecommunications,astrophysicsand
imageprocessing,etc.
1.1BlindSourceSeparation
Blindsourceseparation(BSS)isamajorareaofresearchinsignalprocessing.Avast
literatureexists,particularlyinaudiosignalprocessing.ThegoalofBSSistoseparatesource
1
signalsfromtheirmixtureswithoutassumingdetailedknowledgeaboutthesourcesandthe
mixingprocess.InthispaperwefocusonaparticularapplicationofBSSinaudio,namely
toextractadesiredaudiosourcefrommixturesinvolvingnoise,backgroundorunwanted
sources.Suchextractionscanbeextremelychallengingwhentheunwantedsourcesaremuch
strongerthanthesourceonewishestoextract,whichcanbethecaseinmanypractical
applicationssuchasmobileandcarphones.StandardBSStechniquesoftendonotworkat
allinsuchsettings.
Wedescribeourmodelinitsmostgeneralform.ThebasicsetupforBSSinaudio
has
n
audiosources
S
1
(
t
)
;:::;S
n
(
t
)and
m
mixtures
X
1
(
t
)
;:::;X
m
(
t
),withthemodel
X
k
(
t
)=
L
X
i
=1
N
k;i
X
j
=1
a
k;i;j
S
i
(
t

d
k;i;j
)
;k
=1
;:::;M
(1.1.1)
where
a
k;i;j
arethemixingcotsand
d
k;i;j
arethedelaysfromthesource
i
tothe
recordingorsensingdevice
k
.Themixingwithmultipledelaysarearesultofboththedirect
signalandthereverberations(echoes)intheambientenvironment.Inaudioapplications
thesensorsaremicrophones,andthesemixturesarerecordedbyplacing
m
microphonesin
variouslocations.InBSSthesecotsareunknown.Withthepresenceofreverberations
weoftenrefertothemixtures
X
k
in(1.1.1)as
convolutivemixtures
.Mathematicallyamore
concisewaytoformulatethemodel(1.1.1)is
X
k
=
L
X
i
=1
A
k;i

S
i
;k
=1
;:::;M
(1.1.2)
2
where

denotesconvolutionand
A
k;i
(
t
)=
N
k;i
X
j
=1
a
k;i;j

(
t

d
k;i;j
)(1.1.3)
arethe
convolutivekernels
or

thatrepresentthemixingofboththedirectsignalsand
theirreverberations.BSStechniquesaimtoestimatetheseconvolutivekernels
A
k;i
.
AmongthemostpopulartechniquesforBSSisthe
independentcomponentanalysis(ICA)
model,wherethesourcesignals
S
k
,modeledasrandomvariables,areassumedtobeinde-
pendent,seethereviews[13,26]andthereferencesthereinformoredetails.Underthis
model,manytechniquessuchasJointApproximateDiagonalizationEigenmatrices(JADE)
[11]andInformationMaximization(Infomax)[6,12],aswellastheirts,havebeen
developed.ItissafetosaythattheICAmodelformstheoverwhelmingbulkoftheresearch
inBSS.Analternativetechnique,whichisgainingpopularity,isthe
DegenerativeUnmixing
andEstimationTechnique(DUET)
,whichusestime-frequencyseparationstoachieveBSS
andhastheadvantagethatitcanworkinthedegenerativecase
M<L
,seee.g.[30,60].All
thesetechniqueshavetheirrespectivestrengthsandweaknesses,whicharewelldocumented
intheliteraturesowewillnotgointodetailshere.Whilethesetechniquescanoftenyield
goodresultsinBSS,theyallhavecertainlimitationsthatposechallengesformanysource
extractionandbackgroundremovalapplications.Amajorchallengeisthattheydonotwork
wellforthecasewefocuson,namelyforsourceextractionwherethedesiredsourcesignals
areveryweakincomparisontotheunwantedsourcesinthemixtures.Computationalcost
canbeanotherissueformanypracticalapplicationssuchasmobileandcarphonewhere
removingbackgroundsourcesmustbedoneinrealtime.Thebatchprocessingtechniques
usedbymanyoftheICAtechniquesdonotadaptwelltodynamicreal-timeprocessing.
3
Analternativeapproachbasedonbackgroundlearningandcancellationkernelsforsource
extractionwasproposedbyWangandZhou[61].Theideaisthatifthedesiredsource
wewishtoextract(wecallitthe
targetsources
)isinactive(silent)forabriefmoment,
thenonemayduringthisbriefmoment\learn"theambientenvironmentinthesenseof
attaininginformationabouttheconvolutivekernelsfortheunwantedsources(wecallthem
the
backgroundsources
).Thiswillallowtheextractionofthetargetsourcethroughcan-
cellationofthebackgroundsources.Typicallyonesecondorevenlessofsilentmomentby
thetargetsourceistfortheextraction.In[61]backgroundlearningwasachieved
throughquadraticprogrammingandregularizationbyimposingcertainnonnegativitycon-
ditionwhichweshalldescribeindetaillater.However,thereareissuesthatneededtobe
addressed.Amajorissuewasthecomputationalspeed,asquadraticprogrammingcanbe
quiteslow.Anothermainissueisthatalthoughtheimpositionofnonnegativityregulariza-
tionseemstoyieldexcellentresult,itisphysicallyunrealisticasinrealworldmixturesthe
convolutivekernelswilloftenhavenegativecots.Amoversionofthismodel
wasproposedinYuetal[63],inwhichan
L
1
regularizationmodelwasusedinplaceofthe
nonnegativity.Notonlyitwouldallownegativecotsinthekernel,butnowasplit
Bregmanalgorithmtocomputethekernelsfortheextraction.Computationally,theuseof
thesplitBregmanalgorithmissubstantiallymoretthanthequadraticprogramming
approachin[61].
Still,evenwiththemuchimprovedcomputationalthereremainsomeissuesthat
needtobeaddressedorunderstood.The
L
1
minimizationmodeloftenleadstosparsity.
Butagain,justlikethenonnegativityassumptionisphysicallyunrealistic,soisthesparsity
assumption,asinatypicalechoicenvironmenttheconvolutivekernelsarefrequently
not
sparse
.Thequalityoftheextractedsourcesusingthenonnegativemodelandthe
L
1
model
4
arefairlycomparable.The
L
1
modeldoesseemtosuppressthebackgroundabitmore,but
theextractedtargetsourceoftenexhibitsubtleartifactsasopposedtotheusuallyartifact-
freeextractionfromthenonnegativitymodel.Anotherissuewetrytounderstandiswhythe
nonnegativitymodelworkseventhoughitisnotarealisticphysicalmodel.Giventhequality
oftheextractedtargetsourcesusingthenonnegativitymodelweareveryinterestedin
analgorithmthatgreatlyimprovesthecomputationalofthenonnegativitymodel.
Inthisthesisweattempttoaddresstheseissues.Wedevelopanewalgorithmsbasedona
regularizedSVDalgorithm.OtherthanourSVDmehtod,wealsoapplyproximityoperator
insolvingcancellationkernelsforBSS.Basedonournumericalresults,proximityoperator
isslightlyfasterthansplitBregmanwhiletheyhavethesamelevelofrelativeerror.Later
weperformextensivecomparisonsofvarioustalgorithms.Asfarasourresultscan
show,theSVDalgorithmyieldsthebestresults,anditisalsothemostcomputationally
t.
Thisthesisfocusesonbackgroundsourceremovalthroughlearningandcancellationker-
nels.Intherestofthisthesis,weshallintroducemoredetailsonourmathematicalmodel
aswellasfurtherbackgroundinformationaboutvarioustechniquesforBSS.Overviewsof
variousalgorithms(splitBregman,Promixityoperatoretc.)willbeprovided.Inthelast
partofthethesis,severalnumericalexampleswillbeshown.
5
1.2MathematicalModelforBackgroundCancellation
Inpracticethetimeisdiscretizedthroughsampling.Itisconvenienttowritetheconvolutive
mixturesinthediscreteform:
X
k
(
t
)=
L
X
i
=1
N
X
j
=0
a
k;i;j
S
i
(
t

j
)
;k
=1
;:::;M;
(1.2.4)
where
t
2
Z
and
T
0
6
t<T
1
.Theinteger
N
denotesthemaximaldelayinthemixture,
whichdependsontheambientenvironmentandthesamplingrate.Weshallviewasignalas
anelementin
l
1
(
Z
).Weshalladoptthenotationsusedin[61]:Foreach
u
2
l
1
(
Z
)weuse
u
(
j
)todenoteits
j
-thentryandsupp(
u
)itssupport,i.e.thesetofindicesofitsnonzero
entries.Forany
u
;X
2
l
1
(
Z
),where
u
issupported,theconvolution
u

X
2
l
1
(
Z
)
isby
u

X
(
t
)=
X
j
2
Z
u
(
j
)
X
(
t

j
)
:
Againwemayrewritethemodel(1.2.4)simplyas
X
k
=
L
X
i
=1
a
k;i

S
i
;k
=1
;:::;M;
(1.2.5)
where
a
k;i
2
l
1
(
Z
)issupportedon[0
;N
]with
a
k;i;j
asits
j
-thelement.
Supposethatthesources
S
1
;:::;S
J
arethebackgroundsourceswewishtoremoveand
S
J
+1
;:::;S
L
arethetargetsourceswewishtopreservefromthemixtures
X
k
,1
6
k
6
M
.
Foranysupported
b
k
2
l
1
(
Z
)wehave
b
k

X
k
=
L
X
i
=1
b
k

a
k;i

S
i
:
(1.2.6)
6
Ifwecan
b
k
suchthat
P
M
k
=1
b
k

a
ki
=0for1
6
i
6
J
,thenby(1.2.5)onecaneasily
verifythat
M
X
k
=1
b
k

X
k
=
L
X
i
=
J
+1

M
X
k
=1
b
k

a
k;i


S
i
:
(1.2.7)
Notethattheunwantedbackgroundsourcesarenowremoved,leavingonlythetargetsources
inplace.Weshallcallthose
b
k
cancellationkernels
.Itwasshownin[61]thatcancellation
kernelsalwaysexist.Thefollowingpropositionwasprovedin[61],andweincludetheproof
hereforself-containment.
Proposition1.2.1([61])
Let
u
k;i
2
l
1
(
Z
)
for
1
6
k
6
M
and
1
6
i
6
J
have
support.Supposethat
M>J
.Thenthereexistssupportedcancellationkernels
b
1
;:::;
b
M
2
l
1
(
Z
)
notallzerosuchthat
M
X
k
=1
b
k

u
k;i
=0
;i
=1
;:::;J:
(1.2.8)
Proof.
TakingtheFouriertransformweneedtoshowtheexistenceofsupported
b
k
suchthat
M
X
k
=1
b
b
k
(
˘
)
b
u
k;i
(
˘
)=0
;i
=1
;:::;J:
Let
F
betheofallrealtrigonometricrationalfunctions,i.e.functionsoftheform
f=g
whereboth
f;g
aretrigonometricpolynomialswithrealcots.Set
A
=[
b
u
k;i
]with
rowsindexedby
i
andcolumnsindexedby
k
,whichis
J

M
.Since
M>J
thereexistsa
Z
=[
f
1
;:::;f
M
]
T
in
F
M
suchthat
A
Z
=0.Nowlet
F
(
˘
)beatrigonometricpolynomial
thatisthecommondenominatorofalltrigonometricrationalfunctions
f
k
,1
6
k
6
M
and
G
k
(
˘
)=
F
(
˘
)
f
k
(
˘
).Each
G
k
isatrigonometricpolynomialwithrealcots.Let
7
b
k
2
l
1
(
Z
)suchthat
b
b
k
=
G
k
.Then
M
X
k
=1
b
k

u
k;i
=0
;i
=1
;:::;J:
Ingeneralcancellationkernelsarenotunique.Practicallythequestionishowcanthey
bereconstructed.Thekeyideain[60]andseveralsubsequentpapers(e.g.,[63])isthat
cancellationkernelscanbeestimatedifthereisaperiodofsilencebythetargetsources
usingvariousoptimizationmethods.
Observethatif
b
1
;:::;
b
M
arecancellationkernelsthensoare
˝
q
b
1
;:::;˝
q
b
M
forany
q
.
Byshiftingwecanthusnormalizethecancellationkernelssothatallsupp
b
k
arenonnegative
andatleastone
b
k
(0)
6
=0.Weshallcallsuchcancellationkernels
normalized
.Thegeneral
frameworkfortargetsourceextractionweproposeinthisthesisistocomputethenormalized
cancellationkernelsviabackgroundlearning.Thiscanbeachievedbyutilizinganinterval
ofsilenceforthetargetsourceswewishtoextract.Oncewehavethecancellationkernels
theextractionoftargetcanbemadethroughbackgroundcancellations.Assumethatthe
targetsources
S
J
+1
(
t
)
;:::;S
L
(
t
)aresilentinthetimeinterval
a
6
t
6
b
,i.e.
S
J
+1
(
t
)=

=
S
L
(
t
)=0.Let
b
1
;:::;
b
M
bethecancellationkernels.Itfollowsfrom(1.2.8)that
M
X
k
=1
b
k

X
k
=0
for
a
+
N
6
t
6
b
.
N
isthemaximumdelayinthemixturewhichdependsontheambienten-
vironmentandthesamplerate.Thuswecanusethisintervaltolearnaboutthebackground
8
andestimatethenormalizedcancellationkernelsbyminimizingthecostfunction
F
(
b
1
;:::;
b
M
;a;b
):=
X
a
+
N
6
t
6
b






M
X
k
=1
b
k

X
k
(
t
)






2
;
(1.2.9)
subjecttotheconstraint
P
M
k
=1
j
b
(0)
j
=1.Inpractice,wereplacethenonlinearconstraint
P
M
k
=1
j
b
(0)
j
=1withtherelaxedlinearconstraint
P
M
k
=1
b
(0)=1,anditseemstowork
equallywell.Oncethecancellationkernelsareobtained,targetsourcescanbeextractedin
realtimeby(1.2.8)throughsimpleconvolutions
M
X
k
=1
b
k

X
k
=
L
X
i
=
J
+1

M
X
k
=1
b
k

u
k;i


S
i
:
Thecostfunction
F
(
b
1
;:::;
b
M
;a;b
)withconstraint
P
M
k
=1
b
(0)=1canbeminimized
easilyasitisaquadraticfunction.Itfallsintothegeneralcategoryof
min
x
k
Au

f
k
2
2
;
(1.2.10)
where
u
2
R
n
and
A
is
m

n
.Ifitisthissimplethenthereclearlyisnotanyneedto
goanyfurther.Unfortunately,ournumericalexperimentshaveshownthatwithoutfurther
constraintsthecancellationkernelsobtainedbyminimizing
F
donotworkatall.Therecould
beseveralproblemsassociatedwithsimplyminimizingthecostfunction.Oneproblemis
thattheconditionnumberinthissetupistypicallyhigh.Anotherproblemisthelackof
uniquenessevenwhenallcancellationkernelsarenormalized.Butsinceanycancellation
kernelscanbeusedtoremovethebackgroundsources,thismaynotbeamajorproblem.
Amoreseriousproblemispotential

.Toovercometheseonemust
9
imposeproperlevelofconstraintsandregularization.
Onepossiblesolutiontoovercometheovproblemandill-posed-nessoftheprob-
lemistoimposeapenaltytermthatservesasboththeregularizerandthesparsityinducer.
Inourexperimentstheminimizersof(1.2.9)arealmostneversparse,particularlyforreal
liferecordedmixtures.Therearemanywaystoachievesparsity,suchasaddingan
l
1
-norm
penaltyterm,seee.g.[33]andthereferencestherein.Thewell-knownROFtotalvariation
modelisthestandardfromwhichmanyothermodelshadoriginated.Thispenaltyhelps
somewhat,andtheresultingbackgroundremovalisoftenadequate.However,theproblem
withthisapproachisthatitaddsapenaltytermthatdoesnotseemnaturaltous.And
Itcanttheperformance.Findingtherightsparsityorotherconditionstoimposeis
themostimportantaspectofthisapproachtosourceextraction,andatthispointisstill
aworkinprogress.ThemaincontributionofthisthesisistointroduceanewSVD-based
regularizationalgorithm,andtoalesserextend,aproximityoperatorbasedalgorithm,to
addresstheproblemsthatareencounteredinbackgroundremoval.
10
Chapter2
BackgroundonPreviousWorkand
NewApproach
2.1ICAforBSS
Independentcomponentanalysis(ICA)
wasbroughtupbyHeraultandJuttenaround
1986[23],becauseitissimilartoanothermethod,principalcomponentanalysis(PCA).
Meanwhile,manypeople,suchasGiannakis[21],Cardoso[10],InouyeandMatsui[27],and
Fety,contributedtothedevelopmentoftheandpropertiesinthisarea.
ICA
was
wellnedbyComonin[17],JuttenandHerault[29]precisely,withdetaileddescriptions
ofotherconceptsaswell.
1
The
ICA
ofarandomvector
y
ofsize
N
withcovariance
V
y
isapair
f
F;

g
ofmatricessuchthat
(
a
)
thecovariancefactorizesinto
V
y
=
F

2
F

;
(2.1.1)
where

isdiagonalrealpositive,
F
isfullcolumnrank
ˆ
,and
F

isthetranspositionof
F
.
(
b
)
theobservationcanbewrittenas
y
=
Fz
,where
z
isa
ˆ

1
randomvectorwith
covariance

2
andwhosecomponentsare'themostindependentpossible',inthesenseof
11
themaximizationofagiven'contrastfunction'thatwillbesubsequentlyd.
Thegoalof
ICA
istoalinearrepresentationofnon-Gaussiandatasothatthe
componentsarestatisticallyindependent,orasindependentaspossible.arinenandOja
providedathoroughreviewofICAalgorithmappliedinBSS[26].
Assumethatweobserved
n
linearmixtures
x
1
;:::;x
n
of
n
independentcomponents
s
1
;:::;s
n
.Asthesimplestcase,ICAmodeliswrittenas
X
j
=
a
j
1
S
1
+
a
j
2
S
2
+

+
a
jn
S
n
;
1
6
j
6
n;
(2.1.2)
wecandropthetimeindex
t
.Itcanbetransferedasmatrixform
X
=
AS;
(2.1.3)
where
X
isthematrixofallmixtures
f
X
j
g
n
j
=1
,
A
isthematrixofthecot
f
a
jk
g
n
j;k
=1
,
and
S
isthematrixof
f
S
j
g
n
j
=1
.
A
isunknown,and
S
isthesolutionwewouldliketo
estimate.ThisishowitisrelatedtoBSS.Sincetheindependenceimpliesuncorrelatedness,
theconstraintofindependencereducesthenumberoffreeparameters,andsimpthe
problem.
Theimmidiatequestioniswhythesourcesarerequiredtobenon-Gaussian.Itcanbe
simplyprovedbythefollowingcounterexample.
Assumethatthemixingmatrix
A
isorthogonalandthesources
f
S
j
g
n
j
=1
areindependent
andGaussianin(2.1.3).Thenmixtures
f
X
j
g
n
j
=1
areuncorrelatedandGaussianwhichinplies
12
theyareofunitvariance.For
x
1
and
x
2
,thejointdensityis
p
(
x
1
;x
2
)=
1
2
ˇ
e

x
2
1
+
x
2
2
2
;
whichisasymmetricfunction.Itdoen'tcontainanyinformationonthedirectionsofthe
columnsofthemixingmatrix
A
.

z
=
A
T
w
,then
y
=
w
T
X
=
w
T
AS
=
z
T
S
.So
y
isalinearconbinationof
s
k
with
weights
z
k
.If
w
isavectormaximizesthenon-Gaussianityof
w
T
X
,
w
wouldcorrespondto
a
z
whichhasonlyonenon-zerocomponentprovedin[26].Thatmeans
w
T
S
=
z
T
S
isone
oftheindependentcomponents.
Inordertomeasurethenon-Gaussianityof
w
T
X
inICAmodel,kurtosisis[26].
If
y
isanon-Gaussianrandomvariablewithzeromeanandunitvariance,thenkurtosisis
by
kurt
(
y
)=
E
f
y
4
g
3(
E
f
y
2
g
)
2
:
Bymaximizingthethenon-Gaussianity,itneedstosolveminimafornegativeormaxima
forpositivekurtosis.Detailedsolutionshavebeenprovidedin[20,26].Negentropyasanother
measurementisintroducedfornon-Gaussianity[26].Minimizationofmutualinformation
isdesignedtominimizethemutualinformation,whichisequivalenttomaimizingthenon-
Gaussianity.Thoroughdisscussionshavebeenprovidedin[19,26]
Asmentionedinprevious1.1,therearemanytechniquesdesignedunder
ICA
model,such
asJADE[11],Infomax[6,12,43].Therearealsomanyextensionsof
ICA
algorithm,such
astopographicICA,multidimensionalICA,kernelICA,tree-dependentcomponentanalysis,
subbanddecompositionICA[13].
Therearetwoambiguitiesof
ICA
providedin[13,26],whicharealsowhatwehavein
13
BSS.Theoneisthatthesources
f
S
j
g
n
j
=1
can'tbeunique,sinceboth
A
and
S
are
unknownin(2.1.3).Thesolutionwouldbeascalarmultipleofthesouces.Thesecondone
isthatthesolutiontomixingmatrix
A
couldbe
AP

1
and
P
isapermutationmatrix,
becausethereisnoorderof
S
andtheordercanbefreelychanged.
ThishelpstounderstandandsolvetheBSSproblem(1.2.4).Inourassumption,all
sourcesareindependentandnon-Gaussian.Becauseweusehumanspeechandmusicas
sources,thefactthatvoicesoftpeopleareindependentandmusicisindependentto
humanvoiceiswidelyaccepted.Thistopicstilldeservesfurtherinvestigation,thoughitis
notthefocusofourstudy.
2.2DUETforBSS
Degenerateunmixingestimationtechnique(DUET)appearedin[30].Jourjine,Rickard
andYilmazstartedworkonBSSwhentherearelessmixturesthansources,whichisdegen-
eratedblindsourceseparation.Thisischallengingbecausethemixingmatrix
A
in(2.1.3)
isnotinvertibleandthetraditionalworkofestimatingtheinversematrixof
A
wouldnot
workanymore.
tfrommodelsunderICAusingthekurtosisortheinformationoptimizationsto
themixingcotsandthedelays,DUETusesthetime-frequencyorthogonality
propertyofthesourcesignals,W-DisjointOrthogonality(WDO)[30,60].DUETallowsfor
thereconstructionofmultiplesourcesfromonlytwomixtures.Furthermore,itisextremely
fast,makingitsuitableforbothbatchanddynamicsourceseparation.
In[60],thedetailedproceduresforthecomputationofsourcesareprovided.Weonlylist
someimportantsteps.Givenawindowingfunction
W
(
t
)andafunction
f
(
t
),thewindowed
14
Fouriertransformof
f
withwindow
W
isby
b
f
W
(
!;˝
):=
Z
R
W
(
t

˝
)
f
(
t
)
e

i!t
dt:
(2.2.4)
Twofunctions
S
1
(
t
)and
S
2
(
t
)arecalled
W-disjointorthogonal
ifthesupportsofthewin-
dowedFouriertransformsof
b
S
W
1
(
!;˝
)and
b
S
W
2
(
!;˝
)aredisjoint,i.e.,
b
S
W
1
(
!;˝
)

b
S
W
2
(
!;˝
)=0
:
(2.2.5)
forall
!
and
˝
.Ifanytwofunctionsin
S
k
(
t
)
n
k
=1
satisfytheWDOpropertythenwesay
S
k
(
t
)
n
k
=1
satisfytheWDOproperty.
Asanexample,ifweconsidertheanechoicmodelasasimpleexampleof1.1.1
X
k
(
t
)=
n
X
i
=1
a
k;i
S
i
(
t

d
k;i
)
;k
=1
;:::;m:
(2.2.6)
When
m
=2andtheconstantwindowfunction
W
(
t
)=1,wehave
X
1
(
t
)=
n
X
k
=1
a
1
;k
S
k
(
t

d
1
;k
)
X
2
(
t
)=
n
X
k
=1
a
2
;k
S
k
(
t

d
2
;k
)
Withoutlossofgenerality,wecanassume
a
1
k
=1,
d
1
k
=0,andchangethenotation
15
a
2
k
=
a
k
and
d
2
k
=
d
k
.Thenwehave
X
1
(
t
)=
n
X
i
=1
S
k
(
t
)
X
2
(
t
)=
n
X
i
=1
a
k
S
k
(
t

d
k
)
With
W
(
t
)=1,wehave
b
X
W
1
(
!;˝
)=
n
X
k
=1
b
S
W
k
(
!;˝
)
b
X
W
2
(
!;˝
)=
n
X
k
=1
a
k
e

id
k
!
b
S
W
k
(
!;˝
)
BytheWDOpropertywithanygiven
!
,thefunction
F
(
!;˝
):=
b
X
W
2
(
!;˝
)
b
X
W
1
(
!;˝
)
canonlytakevaluesintheset
f
a
k
e

id
k
!
:1
6
k
6
n
g
,whichformsthethebasisfor
DUET.theamplitude-phasefunction,

!;˝
):=(
j
F
(
!;˝
)
j
;

!

1

F
(
!;˝
)))
;
where
z
)denotestheangleof
z
,

ˇ
6

6
ˇ
.Ifthereisnowrap-aroundin
F
(
!;˝
)),
thenonlytakesvaluesintheset
f
(
a
k
;d
k
):1
6
k
6
n
g
.Thuseach
b
S
W
k
(
!;˝
)can
16
besolvedviafollowingassignment
b
S
W
k
(
!;˝
)=
8
>
>
>
<
>
>
>
:
b
S
W
k
(
!;˝
)if
!;˝
)=(
a
k
;d
k
)
;
0otherwise.
ThefatalproblemofDUETisthephasewraparoundproblem,whichcausesthefaulty
assignmentof
b
S
W
k
(
!;˝
).Wang,YilmazandZhou[60]introducedanewmethodto
theamplitude-phasefunction

withover-sampledFFT.Ifthewindow
W
sizeis
N
,in
steadofthenormalFFTcomputationofsize
N
data
g
˝
:=
W
(
t

˝
)
X
i
(
t
)thatitcomputes
M
-pointFFTof~
g
˝
bypadding
M

N
zerostoreplace.Thenumericalexperimentsin[60]
provideextremelygoodresultsfor2sourcescase.Moreover,themoDUETimproves
theresultsthannormalDUET,thoughitisstillnotperfectintheseparationofthreeor
moresources.
2.3CancellationKernels
Frompreviousdiscussionandderivation,thereisageneralideaofcancellationkernels.In
thispart,itissummarized.Forthemodel(1.2.5)
X
k
=
L
X
i
=1
a
k;i

S
i
;k
=1
;:::;M;
where
a
k;i
2
l
1
(
Z
)issupportedon[0
;N
]with
a
k;i;j
asits
j
-thelement.Thesequence
f
b
k
g
L
k
=1
2
l
1
(
Z
),whichalsosatisfytheconditionthat
P
M
k
=1
b
k

a
ki
=0for1
6
i
6
J
,is
calledcancellationkernels.
ByProposition1.2.1,ithasbeenprovedthattheexistenceofcancellationkernels.There-
17
fore,(1.2.7)canbevas
M
X
k
=1
b
k

X
k
=(
J
X
i
=1
+
L
X
i
=
J
+1
)(
M
X
k
=1
b
k

a
k;i
)

S
i
(2.3.7)
=
L
X
i
=
J
+1
(
M
X
k
=1
b
k

a
k;i
)

S
i
:
(2.3.8)
Inthisway,backgroundsourcesareeliminated.Researchcanbefurtherconductedfor
separationofsources
f
S
i
g
L
J
+1
,iftherearemorethanoneforegroundsources,i.e.
J
+1
<L
.
ThefocusofourworkistoestimatethecorrespondingcancellationkernelsasBSStech-
nique.Bycomparingvariousoptimizationmethods,includingquadraticprogramming,split
Bregman,proximityoperatorandsigularvaluedecomposition(SVD),andcorrespondingnu-
mericalexperimentsinthenextpart,wecanchoosetheoneswhichprovidegoodresults.At
theend,theresultsofSVDprovideusverygoodsolutionscomparedtootheroptimization
methods.
2.4OptimizationMethods
TheessencialworkofBSSisbasedonusingoptimizationalgarithmstosolvetheapprox-
imationsystem,whichissolvingthecancellationkernelsinthisthesis.Attheearlystage
ofoptimizationstudy,themostcommonlyusedcriteriaarebasedonleastsquaremethod,
however,ithasbeenprovedin[52]thatthetotalvariation(TV)ismoreproperthan
L
2
norm.ROFmodelisintroducedby
L.Rudin
,
S.Osher
and
E.Fatemi
in[54]formulatedas
arg
min
u
f

k
f

u
k
2
L
2
+
j
u
j
TV
:
u
2
R
d
g
;
(2.4.9)
18
where
f
2
R
d
,

istheregularizationparameter,and
j
u
j
TV
isthetotalvariationof
u
.It
hassuccessfullydemonstratedtheadvantageofoptimizingthelocalsolution,andalsois
broadlyacceptedandusedasthegeneralmodelofsignalprocessing,butithasbeenproved
tobeverytominimizebyconventionalmethods.Inordertomakethecomputation
faster,
L
1
hasbeenadoptedtoreplacethetotalvariationterm.Theformulacanbewritten
as
arg
min
u
f

k
f

u
k
2
L
2
+
j
u
j
1
:
u
2
R
d
g
:
(2.4.10)
Forestimatingcancellatoinkernels,theformulacanberewrittenas
arg
min
u
f

k
Au

f
k
2
L
2
+
j
u
j
1
:
u
2
R
d
g
:
(2.4.11)
InBSSofaudiosignals,ROFmodelwith
L
1
regularizationterm(2.4.11)isusedtosolve
thecancellationkernels,aswementionedpreviouslyinSection1.1.
u
isthecombinationof
cancellationkernels,whichistfromthecaseofimageprocessingthatpeopleuse
u
asthetruesignal(2.4.10).Alotofpreviousexistingalgorithmsinimageprocessingcanbe
usedinBSSofaudiosignals.Inthenextpart,wearegoingtointroducesomeimportant
methodsforsolvingBSS.Quadraticprogrammingisspforsolvingcancellationkernels
inaudiosignalprocessing[60].SplitBregamisaniterationmethodoriginallyusedinimage
processing[22].XinandOsherapplieditinBSSofaudiosignalprocess[39,40,41,63,64].
ProximityoperatormethodisanotherinterationmethodusedbyMicchelli,ShenandXu
forBSSofimageprocessing[37,38].Weapplyproximityoperatormethodinsolvingthe
cancellationkernelsforBBSofaudiosignalprocessing.
19
2.4.1QuadraticProgramming
WangandZhoudevelopedtheideaofusingcancellationkernelsandquadraticprogramming
tosolveBSSofaudiosignalprocessingviabackgroundlearning[60].Weapplythemethod
intheworktoachievethesparsenessofcancellationkernelsbyrestrictingthenumberof
nonzeroelementsincancellationkernels,andtheratiobetweennumbersofpositivetoneg-
ativeelements.Yuetalproposedamomodelbyreplacingthenonnegativityofthe
regularizationtermwith
L
1
regularizationandsplitBregmanmethod[63].
Aswehavealreadydisscussedin1.2andabove,thecancellationkernelsexistsothat
M
X
k
=1
b
k

X
k
=0
for
a
+
N
6
t
6
b
.
N
isthemaximumdelayinthemixturewhichdependsontheambient
environmentandthesamplerate.Thereforwecanusethisintervaltolearnthebackground
andestimatethenormalizedcancellationkernelsbyminimizingthecostfunction(1.2.9)
F
(
b
1
;:::;
b
M
;a;b
):=
X
a
+
N
6
t
6
b






M
X
k
=1
b
k

X
k
(
t
)






2
;
subjecttotheconstraint
P
M
k
=1
b
(0)=1.
Innumericalcomputation,weonlyneedtochooseatimeintervalwithlengtharound
1secondfrom[
a
+
N;b
]forlearningthebackground,forsolvingthecancellationkernels
andextractingtheforegroundsources.Inordertotesttheerroroftheresult,wechoosea
20
ttimeinterval[
s
testing
;e
testing
]from[
a
+
N;b
]tocalculatetheerrorby
Err
(
b
1
;:::;b
M
;a;b
):=
X
s
testing
6
t
6
e
testing






M
X
k
=1
b
k

X
k
(
t
)






2
:
(2.4.12)
Inthefollowingpart,theformulaforthecasesoftwosourceandtwomixturesandthree
sourcesandthreemixturesareprovided.
2.4.1.1TwoSourcesandTwoMixtures
Nowletustaketheexampleoftwosourcesandtwomixturescase.Theanalysiscanalsobe
foundin[60].When
L
=
M
=2,
S
1
isthebackgroundand
S
2
istheforeground.Assume
thattheforegroundsource
S
2
=0inthetimeinterval
a
6
t
6
b
.Itsimplyneedstotake
b
1
=
a
2
;
1
and
b
2
=

a
1
;
1
forcancellationkernels,whichsatisfy
b
1

a
1
;
1
+
b
2

a
2
;
1
=0
:
(2.4.13)
Itleadsto
b
1

X
1
+
b
2

X
2
=(
b
1

a
1
;
2
+
b
2

a
2
;
2
)

S
2
=(
a
2
;
1

a
1
;
2

a
1
;
1

a
2
;
2
)

S
2
:
Let
Y
:=
a
2
;
1

X
1

a
1
;
1

X
2
:
(2.4.14)
Then
Y
(
t
)=0,where
a
+
N
6
t
6
b
.
Let
A
n
=
a
2
;
1
(
n
)and
B
n
=
a
1
;
1
(
n
)for0
6
n
6
N
and0otherwise.
21
Denote
A
=[
A
0
;A
1
;:::;A
N
]
T
;
B
=[
B
0
;B
1
;:::;B
N
]
T
;
and
F
(
t
)=[
X
1
(
t
)
;X
1
(
t

1)
;:::;X
1
(
t

N
)
;
]
T
;
G
(
t
)=[
X
2
(
t
)
;X
2
(
t

1)
;:::;X
2
(
t

N
)
;
]
T
:
Wecouldestimate
a
2
;
1
;a
1
;
1
byminimizing
E
(
A;B;a;b
)=
X
a
+
N
6
t
6
b
j
Y
(
t
)
j
2
=
X
a
+
N
6
t
6
b
[
A
T
F
(
t
)

B
T
G
(
t
)]
2
=
X
a
+
N
6
t
6
b
[
A
T
F
(
t
)
F
(
t
)
T
A
+
B
T
G
(
t
)
G
(
t
)
T
B

2
A
T
F
(
t
)
G
(
t
)
T
B
]
=
U
T
DU;
where
U
=
2
6
4
A
B
3
7
5
;D
=
2
6
4
D
FF

D
FG

D
GF
D
GG
3
7
5
;
22
D
FF
=
X
a
+
N
6
t
6
b
F
(
t
)
F
(
t
)
T
;
D
GG
=
X
a
+
N
6
t
6
b
G
(
t
)
G
(
t
)
T
;
D
FG
=
X
a
+
N
6
t
6
b
F
(
t
)
G
(
t
)
T
;
D
GF
=
X
a
+
N
6
t
6
b
G
(
t
)
F
(
t
)
T
=
D
T
FG
;
Itresultsin
min
A;B
A
T
D
FF
A
+
B
T
D
GG
B

2
A
T
D
FG
B
(2.4.15)
subjectto
A
0
+
B
0
=1.
2.4.1.2ThreeSourcesandThreeMixtures
Forthreesourcesandthreemixturescase,weassume
S
1
and
S
2
arebackgrounds,and
S
3
is
foreground.Assumethattheforegroundsource
S
3
=0inthetimeinterval
a
6
t
6
b
.Since
L
=
M
=3,thereexistcancellationkernels
f
b
k
g
3
k
=1
suchthat
3
X
k
=1
b
k

X
k
=
3
X
i
=1
(
3
X
k
=1
b
k

a
k;i
)

S
i
:
(2.4.16)
Soourgoalistoremove
S
1
and
S
2
frommixtures
X
1
,
X
2
,
X
3
.Similarlyasinpreviouscase,
let
Y
:=
b
1

X
1
+
b
2

X
2
+
b
3

X
3
:
(2.4.17)
Then
Y
(
t
)=0,where
a
+
N
6
t
6
b
.
23
Denote
b
1
=[
b
1
(0)
;b
1
(1)
;:::;b
1
(
N
)]
T
;
b
2
=[
b
2
(0)
;b
2
(1)
;:::;b
2
(
N
)]
T
;
b
3
=[
b
3
(0)
;b
3
(1)
;:::;b
3
(
N
)]
T
;
and
F
(
t
)=[
X
1
(
t
)
;X
1
(
t

1)
;:::;X
1
(
t

N
)]
T
;
G
(
t
)=[
X
2
(
t
)
;X
2
(
t

1)
;:::;X
2
(
t

N
)]
T
;
H
(
t
)=[
X
3
(
t
)
;X
3
(
t

1)
;:::;X
3
(
t

N
)]
T
:
Wecanestimate
b
1
;b
2
;b
3
byminimizing
E
(
b
1
;b
2
;b
3
;a;b
)=
X
a
+
N
6
t
6
b
j
Y
(
t
)
j
2
=
X
a
+
N
6
t
6
b
[
b
T
1
F
(
t
)+
b
T
2
G
(
t
)+
b
T
3
H
(
t
)]
2
=
X
a
+
N
6
t
6
b
[
A
T
F
(
t
)
F
(
t
)
T
A
+
B
T
G
(
t
)
G
(
t
)
T
B

2
A
T
F
(
t
)
G
(
t
)
T
B
]
=
U
T
DU;
where
U
=
2
6
6
6
6
6
4
b
1
b
2
b
3
3
7
7
7
7
7
5
;D
=
2
6
6
6
6
6
4
D
FF
D
FG
D
FH
D
GF
D
GG
D
GH
D
HF
D
HG
D
HH
3
7
7
7
7
7
5
;
24
D
FF
=
X
a
+
N
6
t
6
b
F
(
t
)
F
(
t
)
T
;
D
GG
=
X
a
+
N
6
t
6
b
G
(
t
)
G
(
t
)
T
;
D
HH
=
X
a
+
N
6
t
6
b
H
(
t
)
H
(
t
)
T
;
D
FG
=
X
a
+
N
6
t
6
b
F
(
t
)
G
(
t
)
T
;
D
FH
=
X
a
+
N
6
t
6
b
H
(
t
)
H
(
t
)
T
;
D
GF
=
X
a
+
N
6
t
6
b
G
(
t
)
F
(
t
)
T
=
D
T
FG
;
D
GH
=
X
a
+
N
6
t
6
b
G
(
t
)
H
(
t
)
T
;
D
HF
=
X
a
+
N
6
t
6
b
H
(
t
)
F
(
t
)
T
=
D
T
FH
;
D
HG
=
X
a
+
N
6
t
6
b
H
(
t
)
G
(
t
)
T
=
D
T
GH
:
Itleadsto
min
b
1
;b
2
;b
3
U
T
DU;
(2.4.18)
subjectto
b
1
(0)+
b
2
(0)+
b
3
(0)=1.
Ifwecanbringthesparsenesstocancelationkernels
b
k
,weprobablywillhaveabetter
computationaltimethantheoneswithoutsparseness.Herewetrytogettheapproximation
ofthemwiththeminimumnumberofnonzeroelements.Themorezeroswehave,theless
computationsweneedinsolvingconvolutions.Thoughitissupposedtobecomputationally
fasterandmoret,thenumericalexperimentsshowthatthesparsenesscannotreally
25
improvetheresults,anditisevenmoretime-consumingsometimes.Thedetaileddescription
forintroducingsparsenessisprovidedbelow,whilethealgorithmisprovidedinthenext
chapter.
2.4.1.3IntroducingSparseness
Sincethenumericalresultsofthecancelationkernelsarenotuniqueforerentlocalinter-
vals,onebigchallengebecomestheevaluationoftcancelationkernelssolvedfrom
tintervals.Thisisthealsothepartoftheoriginalgoalofconsideringthesparseness
forallcancelationkernelsandpickuptheimportantpositionsofcancellationkernels.
Themainideaofthisalgorithmistoreplaceunimportantelementsincancelationkernels
withzeros.Sotheseunimportantonesdonothavemuchimpactontheresultswhenwe
evaluatetheerrorterm(2.4.12),andkeepallthepositionsofimportantones'thatthosecan
theerrorterm(2.4.12),whilewealsokeeptheoneswithminimumerrortermthrough
theprocessbycomparingwithpreviousstepaswell.
Thisideaisborrowedfromaspmethodcalledsupportvectormachine,frommachine
learning.Itisdescribedin[24]and[42].Thecompuationprocessislistedasbelow.
1
:
Firstofall,wetaketwonon-overlappedsmallerintervals,[
s
1
;e
1
]and[
s
2
;e
2
],from
theinterval[
a
+
N;b
],wheretheforegroundsourcesaresilent.[
s
1
;e
1
]isthetrainingset,
and[
s
2
;e
2
]isthetestingset.
2
:
Choosingsmallintervals[
s
training
;e
training
]
ˆ
[
s
1
;e
1
]and[
s
testing
;e
testing
]
ˆ
[
s
2
;e
2].
3
:
Solvingthecorrespondingcancellationkernels
f
b
k
g
on[
s
training
;e
training
]andtak-
ingtheerrorby(2.4.12)on[
s
testing
;e
testing
].
Inthefollowingsteps,wearegoingtotheminimumerrorwithitscorresponding
26
sparsedcancellationkernels.
4
:
Eliminatingthesmallest
p
elementsof
f
b
k
g
inabsolutevalue.
5
:
Resolvingtheminimizationproblemoninterval[
t
training
;e
training
]tonew
cancelationkernels,withtheconstraintthattheeliminatedpositionsof
f
b
k
g
aszeros.
6
:
Calculatingthenewerrorfromnewcancellationkernelsby(2.4.12)on[
s
testing
;e
testing
].
Werepeattheaboveproceduresfrom4to6untillwegettheminimumerrorwith
minimumnumberofnonzeroelementsof
f
b
k
g
,sinceweatleastcangetridof
p
nonzero
elementseachtime.Then,werecordallthenonzeropositionsof
f
b
k
g
.
Startingoverfromstep1
:
byrandomlychoosinganotherpairoftrainingset[
s
training
;e
training
]
andtestingset[
s
testing
;e
testing
].Followwhatareshownaboverepeatedly
Q
1
iteration
times,tillwegettheminimumerrorduringeachstep.Inournumericalexamples,itturns
out
Q
1
>
40atleasttoprovidegoodresultsforcancellationkernelswhichcanremovethe
background.
7
:
Getingthefrequencyofeachelementincancelationkernels
f
b
k
g
,
V
Freq
,correspond-
ingtotheminimumerrorsineachstepattheend.
Inthesecondstage,westartwithpreviouslycapturednonzeropositionswithminimum
errors,andestimatethecancelationkernelsonthelearninginterval,throughincreasing
thenonzeropositionsatcertainpercentageineachsteptocomparetheerrortermby(2.4.12),
sothatwegetthecancelationkernels
b
k
withminimumerrorattheend.
Detailedstepsarelistedasbelow.
1
:
Startingtoestimate
f
b
k
g
withonly
q
highestfrequencyelementsasnonzeroand
leavetherestelementsaszero,byminimizationfunction(1.2.9)on[
s
1
;e
1
],where
q
isa
positiveinteger.Then,dividing[
s
1
;e
1
]into
Q
2
equalsubintervals,
I
1
;:::;I
Q
2
,where
Q
2
is
apre-selectednumber.Now,wecorrespondingerrorvector
Error
byfunction(2.4.12)
27
andestimatedcancellationkernels,onallof
I
k
,
k
=1
;:::;Q
2
.Meanwhile,takeingthe
meansofalltheseerrors,
Error
mean
.
2
:
Choosingnext
M
q
highestfrequencyelementsincancelationkernels,exceptthe
q
elementsalreadychosen.Thenusingthese
q
+
M
q
nonzeroelementstoestimateasetofnew
f
b
k
g
byminimizationfunction(1.2.9),oninterval[
s
1
;e
1
].Pluswecouldgetanewerror
vector,
Error
q
+
M
q
anditsmean,
Error
mean;q
+
M
q
.
3
:
Runningthesameprocedureasabovestep2iteratively,tillwetakealltheelements
withpositivefrequencyof
f
b
k
g
in
V
Freq
.
4
:
Takingthesetof
f
b
k
g
withtheminimummeanerror.Nowwecangettheforeground
sourcesonthedesiredtimeintervalbyusing
f
b
k
g
.
Ingeneral,thisprocesscanprovidethesparsecancellationkernelswithimportantpo-
sitions,thoughittakesalongtimetogothroughtheinterativequadraticprogramming
procedure.ThealgorithmislistedinSection3.2.1.
2.4.2SplitBregmanMethod
Bregmaniterationisoriginallyusedinfunctionalanalysisforextremaofconvex
functionals[5].Furthermore,OsherusedBregmaniterationinimageprocessing[47].
However,itneedstosolveaoptimizationequationeachiterativestepwhichisveryexpensive
computationally.
In[22,47],authorsprovidedathoroughbackgroundintroductionofBregmaniteration.
Startingwiththeassumptionthat
E
and
H
aretwoconvexenergyfunctionals,
over
R
n
withmin
u
2
R
n
H
(
u
)=0,where
H
istiableforsimplicity.Itleadstothe
28
unconstraintminimizationproblem,
arg
min
u
f
E
(
u
)+

(
u
):
u
2
R
d
g
;
(2.4.19)
whichwasmobyiterativelysolving
u
k
+1
=min
u
f
D
p
E
(
u;u
k
)+

(
u
)
g
(2.4.20)
=min
u
f
E
(
u
)

<p
k
;u

u
k
>
+

(
u
)
g
;
(2.4.21)
where
D
p
E
(
u;v
)=
E
(
u
)

E
(
v
)

<p;u

v>
,with
p
isinthesubgradientof
E
at
v
,and
p
k
+1
=
p
k
r
H
(
u
k
+1
)in[5].
ThenGoldsteinandOsherintroducedtheapplicationofsplitBregmanmethodfor
L
1
regularizedproblemsin[22]withathoroughintroductionofsplitBregmaniterationfor
imageprocessing.Itsplitsthecomputationbyintroducingaintermediateterm,which
thecomputation.In[9],CaietalprovedtheconvergenceofthesplitBregman
iterationundercertainassumptions.Lateron,OsheretalproposedthelinearizedBregman
iterationmethodbytransformingtheminimizationproblemineachinterativesteptoa
linearapproximationforbettercomputationaltime[8,48].
XinandOsher,etalalsocontributedalotinapplyingsplitBregmaniterationinaudio
signalprocessing,[39,40,41,63,64].Theirworkbroughtuptheattentiontotheimportance
offastcomputationinBSS.SplitBregmanmethodwillbenumericallydemonstratedand
comparedwiththeworkwehavedoneinfollowingchapters.
29
2.4.2.1BregmanIteration
Intheliterature[22],itprovidedathoroughbackgroundintroductionofBregmaniteration.
Startingwiththeassumptionthat
E
and
H
aretwoconvexenergyfunctionals,
over
R
n
withmin
u
2
R
n
H
(
u
)=0,where
H
istiableforsimplicity.Itleadstothe
unconstraintminimizationproblem,
arg
min
u
f
E
(
u
)+

(
u
):
u
2
R
d
g
;
(2.4.22)
whichwasmobyiterativelysolving
u
k
+1
=min
u
f
D
p
E
(
u;u
k
)+

(
u
)
g
(2.4.23)
=min
u
f
E
(
u
)

<p
k
;u

u
k
>
+

(
u
)
g
;
(2.4.24)
where
D
p
E
(
u;v
)=
E
(
u
)

E
(
v
)

<p;u

v>
,with
p
isinthesubgradientof
E
at
v
,and
p
k
+1
=
p
k
r
H
(
u
k
+1
)in[5].
In[47],authorsanalyzedtheconvergenceofBregmaniteration,especially,underfairly
weakassumptionson
E
and
H
,that
H
(
u
k
)
!
0as
k
!
0.Thereisaconvergenceresult
restatedin[22].
Theorem2.4.1
Assumethat
E
and
H
areconvexfunctionals,andthat
H
isentiable.
Wealsoassumethatsolutionstothesub-problemsin(2.4.23)exist.Wethenhave
1.
Monotonicdecreasein
H
:
H
(
u
k
+1
)
6
H
(
u
k
)
,
2.
Covergencetoaminimizerof
H
:
H
(
u
k
)
6
H
(
u

)+
E
(
u

)
=k
,
where
u

istheminimizerof
H
(
u
)
.
30
2.4.2.2ConstrainedOptimization
Forproblem
arg
min
u
E
(
u
)
suchthatAu
=
b;
(2.4.25)
where
A
isalinearoperatorand
b
isavector.Byapplyingformula(2.4.22),itcanbe
transformedtounconstrainedproblemusing
kk
2
,
arg
min
u
f
E
(
u
)+

2
k
Au

b
k
2
2
g
;
(2.4.26)
where

isapositiveconstant.
Furthermore,weapplyBregmaniteration(2.4.23)toderive,
u
k
+1
=min
u
f
E
(
u
)

<p
k
;u

u
k
>
+

2
k
Au

b
k
2
2
g
;
(2.4.27)
p
k
+1
=
p
k


T
(
Au
k
+1

b
)
;
(2.4.28)
where
A
T
isthetransposeof
A
,and
<

;

>
isthenormalinnerproduct.When
A
islinear,
itisequivalenttosolve,
u
k
+1
=min
u
f
E
(
u
)+

2
k
Au

b
k
2
2
g
;
(2.4.29)
b
k
+1
=
b
k
+
b

Au
k
:
(2.4.30)
Thefollowingtheoremfrom[22]statesthatthesolution,
u

,throughthisprocess(2.4.29)
-(2.4.30),isthesolutionof(2.4.25).
Theorem2.4.2
Let
H
:
R
d
!
R
beconvex,and
A
:
R
n
!
R
m
belinear.Considerthe
algorithm(2.4.29)-(2.4.30).Supposethat
u

,that
Au

=
b
.Then
u

isasolution
31
totheoriginalconstrainedproblem(2.4.25).
2.4.2.3SplitBregman
Bregmaniterationisagoodtoolforsolvingoptimizationproblems,however,itneedsto
solvetheminimization
D
p
E
(
u;u
k
)+

(
u
)
in(2.4.23)ateachiterativestep,whichcancomputationallyexpensive.ThesplitBregman
iterationmethodintroducesanintermediatevariablewhichmakestheROFmodelseparable
andeasiertosolve.InsteadofconsideringtheoriginalBregmanproblemasaconstraint
problem,accordingto[22],thesplitBregmanmethodaimstosolvetheunconstrainedprob-
lem
arg
min
u;d
fj
d
j
+
H
(
u
)+

2
k

u
)

d
k
2
2
g
:
(2.4.31)
Byintroducing
E
(
u;d
)=
j
d
j
+
H
(
u
),and
A
(
u;d
)=
d


u
),itisclearthat(2.4.31)
issimplyanimplementationof(2.4.26).Correspondingly,weshouldhavethefollowing
iteration,
(
u
k
+1
;d
k
+1
)=
arg
min
u;d
f
E
(
u;d
)

<p
k
u
;u

u
k
>

<p
k
d
;d

d
k
>
+

2
k

u
)

d
k
2
2
g
;
p
k
+1
u
=
p
k
u


(
r

T

u
k
+1
)

d
k
+1
)
;
p
k
+1
d
=
p
k
d


(
d
k
+1


u
k
+1
))
:
Similarly,following(2.4.29)-(2.4.30),byintroducing
b
k
=
p
k
d

,wenoticethat
p
k
d
=

k
,
and
p
k
u
=


(
r

T
b
k
.Thenitleadstotheequivalentalgorithmfrom[41],bysetting
d
0
=0,
32
u
0
=0,and
b
0
=0,
d
k
+1
=
arg
min
d
f
1

J
(
d
)

<b
k
;d

d
k
>
+
1
2
k

u
k
)

d
k
2
2
;
g
(2.4.32)
u
k
+1
=
arg
min
u
f
1

H
(
u
)+
<b
k
;

u

u
k
)
>
+
1
2
k
d
k
+1


u
k
)
k
2
2
g
;
(2.4.33)
b
k
+1
=
b
k

(
d
k
+1


u
k
+1
))
:
(2.4.34)
Convergencetheoremisderivedin[9],forthecaseof
J
(
u
)=

k
u
k
1
,alsorestatedin
[41]asbelow,
Theorem2.4.3
Assumethatthereexistsatleastonesolution
u

of
arg
min
u
f
J

u
))+
H
(
u
)
g
;
(2.4.35)
where
J
isconvexbutnotnecessarilyentiable,
H
isconvexandentiable,and

isalinearoperator.ThenwehavethefollowingpropertiesforthesplitBregmaniteration
(2.4.32)-(2.4.34),
lim
k
!1
f

k

u
k
)
k
1
+
H
(
u
k
)
g
=

k

u

)
k
1
+
H
(
u

)
:
(2.4.36)
Furthermore,
lim
k
!1
k
u
k

u

k
2
=0
;
if
u

istheuniquesolution.
33
2.4.3ProximityOperator
WeapplythismethodinBSSofaudiosignalprocessingtosolvethecancellationkernels.The
majorconclusionsofproximityoperatorarelistedinthischapter.Thedetailedalgorithmis
thethenextchapterandnumericalresultsareprovidedattheend.
ProximityoperatorwasintroducedbyMoreauin[34],andfurtherinvestigatedin
[35][36].Combettesalsocontributedtotheinitiationofusingproximityoperatorin[14].
Micchelli,ShenandXuappliedproximityoperatormethodforBSSinimageprocessing
[37,38].Theyalsoprovidedadetailedanalysisincomparingproximityoperatorwithsplit
BregmaninimageprocessingtoshowthatproximityoperatorisbetterthansplitBregman.
2.4.3.1
2
Let
 
beareal-valuedconvexfunctionon
R
d
.Theproximityoperatorof
 
is
dfor
x
2
R
d
by
prox
 
x
:=
arg
min
f
1
2
k
u

x
k
2
2
+
 
(
u
):
u
2
R
d
g
:
(2.4.37)
InROFmodel(2.4.9),themajoryisinminimizingthetotalvariationterm
jj
TV
.
C.Micchelli,L.Shen,andY.XuproposedarentwayofsolvingtheROFmodelfor
imageprocessing,[37,38],andconcludedthatitisfasterthansplitBregmaninthesp
form,
arg
min
u
f
1
2
k
u

x
k
2
2
+

j
u
j
TV
:
u
2
R
d
g
;
(2.4.38)
where
x
2
R
d
denotesthenoisysignal,

istheregularizationparameter,bynotingthat
thesolutionoftheROFmodelcanbeviewedastheproximityoperatorof
jj
TV
evaluated
34
atthenoisysignal
x
.Sinceitcannotbeeasilycomputed,itistreatedthat
jj
TV
isthe
compositionofconvexfunction,suchasthenorm
kk
1
fortheanisotropictotal-variation
oracertaincombinationofthenorm
kk
2
fortheisotropictotalvariation,withalinear
transformation(theoperator).Thisapproachwillbeadoptedinnext
chapterforsolvingBSSaccousticsignalprocessing.
3
Let
 
beareal-valuedconvexfunctionon
R
d
.Thesubentialof
 
at
x
2
R
d
isdby
@ 
(
x
):=
f
y
:
y
2
R
d
and 
(
z
)
>
 
(
x
)+
<y;z

x>forallz
2
R
d
g
:
(2.4.39)
Elementsin
@ 
(
x
)arecalledsubgradients.
If
>
0and
x
2
R
,thenthewell-knownsoftthresholdingoperatorwith
1

asthe
thresholdis,
prox
1


x
=max
fj
x
j
1

;
0
g
sign
(
x
)
:
(2.4.40)
Furthermore,if
>
0and
x
2
R
m
,wehave
prox
1


1
x
=[
prox
1


x
1
;prox
1


x
2
;:::;prox
1


x
m
]
T
:
(2.4.41)
Itisapparenttodirectlyverifythatif
 
isaconvexfunctionon
R
d
and
x
2
R
d
,then
y
2
@ 
(
x
)
35
ifandonlyif
x
=
prox
 
(
x
+
y
)
:
2.4.3.2FixedPointAlgorithmBasedonProximityOperator
Foraconvexfunction
'
on
R
m
andan
m

d
matrix
B
,authorsin[37]aconvex
function
 
(
x
):=(
'

B
)(
x
)
:
(2.4.42)
Sincetheaimistocomputetheproximityoperator
prox
 
,i.e.,
prox
'

B
,thenconsiderthe
minimizationproblem,
arg
min
u
f
1
2
k
u

x
k
2
2
+(
'

B
)(
u
):
u
2
R
d
g
;
(2.4.43)
where
x
2
R
d
isgiven.ThentheROFmodelcorrespondstospecialcasesofthisminimization
problem.
Byreplacing
 
with
'

B
,wehavefollowingseveralproperties:
prox
'

B
x
2
x

@
(
'

B
)(
prox
'

B
x
)
;
(2.4.44)
@
(
'

B
)=
B
T

(
@'
)

B;
(2.4.45)
prox
'

B
x
2
x

B
T
@'
(
Bprox
'

B
x
)
:
(2.4.46)
Byintroducingthetransformation
A
:
R
m
!
R
m
forall
y
2
R
m
as
Ay
:=
Bx
+(
I

B
T
)
y
(2.4.47)
36
fora
x
2
R
d
,thenonecantheoperator
A
:
R
m
!
R
m
givenby
H
:=(
I

prox
1

'
)

A:
(2.4.48)
Theorem2.4.4
If
'
isaconvexfunctionon
R
m
,
B
isa
m

d
matrix,
x
2
R
d
and

isa
positivenumberthen
prox
'

B
x
=
x


T
v
(2.4.49)
ifandonlyif
v
2
R
m
isad-pointof
H
.
Theorem(2.4.4)showsthattheminimizationproblem(2.4.43)correspondstoa
pointof
H
,whichinvolvestheproximityoperatoroftheconvexfunction
1

'
andalinear
transformation
B
.Asadirectresult,thereisthefollowingproposition.
Proposition2.4.5
If
'
isaconvexfunctionon
R
m
,
B
isa
m

d
matrix,
x
2
R
d
and

is
apositivenumber,then
H
hasadpoint.
ForaLipschitzcontinuousfunction
'
withLipschitzconstant
K
thatis
j
'
(
u
)

'
(
v
)
j
6
K
k
u

v
k
;forallu;v
2
R
m
:
(2.4.50)
Let
Lip
'
representthesmallestconstant
K
inthisinequality.Thereisfollowinglemma.
Lemma2.4.6
If
'
isaLipschitzcontinuousconvexfunctionand
y
2
@'
(
x
)
forsome
x
2
R
m
,then
k
y
k

6
Lip
'
;
(2.4.51)
where
kk

representsthedualnorm.
37
Let
C
'
:=
f
z
:
z
2
R
m
;
k
z
k

6
Lip
'

g
:
(2.4.52)
Thefollowinglemmaisestablishedin[37].
Lemma2.4.7
If
'
isaLipschitzcontinuousconvexfunctionand
B
isan
m

d
matrix,
then
H
maps
R
m
into
C
'
.If

ispositivenumber,thenallthedpointsof
H
arein
C
'
.
2.4.3.3Nonexpansivityof
H
4
Anonlinearoperator
P
:
R
d
!
R
d
iscallednonexpansiveif
kP
(
x
)
P
(
y
)
k
2
6
k
x

y
k
2
;
(2.4.53)
forall
x
,
y
2
R
d
.
P.Combettes,andV.Wajsin[15]provedthat
k
(
I

prox
 
)(
x
)

(
I

prox
 
)(
y
)
k
2
2
6
<x

y;
(
I

prox
 
)(
x
)

(
I

prox
 
)(
y
)
>:
(2.4.54)
ByapplyingCauchy-Schwarzinequalityto(2.4.54),itshows
I

prox
 
isnonexpansive.
H
isnonexpansivebasedonnextlemma.
Lemma2.4.8
If
'
isaconvexfunctionon
R
d
,
B
isan
m

d
matrix,and

ispositive
numbersuchthat
k
I

B
T
k
2
6
1
,then
H
isnonexpansive.
5
Anonlinearoperator
P
:
R
d
!
R
d
iscallednonexpansiveaveragedifthere
areanumber

2
(0
;
1)
andanonexpansiveoperator
Q
suchthat
P
=

+(1


)
Q:
(2.4.55)
38
P
isspallycallednonexpansive

-averaged.Bydirectcomputation,onecanverifythat
thecompositionoftwononexppansiveaveragedoperatorsisalsononexpansiveaveraged.
Thenthesegeneralresultscanbeappliedon
H
in(2.4.48).
Proposition2.4.9
If
'
isaconvexfunctionon
R
d
,
B
isan
m

d
matrix,and

ispositive
numbersuchthat
k
I

B
T
k
2
6
1
,then
H
isnonexpansive

-averagedforsome

2
(0
;
1)
.
Inordertoshowtheconvergence,weneedtoconstructPicardsequence.Foranoperator
P
:
R
m
!
R
m
,withinitialpoint
v
0
2
R
m
,wehavethefollowingPicardsequence,
v
n
+1
:=
P
(
v
n
)
;
(2.4.56)
for
n
2
N
.For

2
(0
;
1),theof

-averagedoperator
P

for
P
isgivenby
P

:=

+(1


)
P
:
(2.4.57)
Let
P
0
=
P
.
Z.Opialin[45],showstheconvergenceofthePicardsequenceof
P

.
Lemma2.4.10
If
C
isaclosedandconvexsetin
R
m
and
P
:
C
!
C
isanonexpansive
mappinghavingatleastonedpoint,thenfor

2
(0
;
1)
,
fP
k
g
isnonexpansive,maps
C
to
itself,andhasthesamesetofthedpointas
P
.Moreover,forany
u
2
C
and

2
(0
;
1)
,
thePicardsequenceof
P

convergestoadpointof
P
.
Correspondingly,to
H
,authorsin[37]cameupwiththeresult.
Theorem2.4.11
If
'
isaLipschitzcontinuousconvexfunction,
B
isan
m

d
matrix,and

ispositivenumber,suchthat
k
I

B
T
k
2
6
1
,thenforanyinitialpointin
C
'
andany

2
(0
;
1)
,thePicardsequenceof
H

convergestoadpointof
H
.
39
Asaconsequenceof(2.4.9),theauthorsin[37]derivedthefollowingconvergencetheorem
withaslighlystrongercondition.
Theorem2.4.12
If
'
isaLipschitzcontinuousconvexfunction,
B
isan
m

d
matrix,
and

ispositivenumber,suchthat
k
I

B
T
k
2
<
1
,thenforanyinitialpointin
C
'
,the
Picardsequenceof
H
convergestoadpointof
H
.
Theyalsoshowedthat
H
isaveragednonexpansiveasfaras
<
1
4sin
2
(
N

1)
ˇ
2
N
(2.4.58)
where
N
=
p
d
.
2.4.3.4Algorithm
Bysetting
'
(
x
)=

k
x
k
1
,theROFmodel(2.4.9)becomes
arg
min
u
f
1
2
k
u

x
k
2
2
+

k
Bu
k
1
:
u
2
R
d
g
:
(2.4.59)
Thealgorithmcanbegeneralizedin[37]as
Given
x
;
<
1
4sin
2
(
N

1)
ˇ
2
N
,
>
0,

2
[0
;
1)
Initialize:
v
0
=0
For
n
=0
;
1
;:::
v
n
+1
:=

n
+(1


)(
I

prox



1
)(
Bx
+(
I

B
T
)
v
n
)
End
Writetheoutputof
v
n
fromtheaboveloopas
v
1
andcompute
prox
'

B
x
=
x


T
v
1
.
40
Theconvergenceisguaranteedbythefollowingproposition.
Proposition2.4.13
If
>
0
and
a
,
x
0
2
R
m
,thentheiterativescheme
x
k
+1
=(
I

prox
1


1
)(
x
k
+
a
)
;k
=0
;
1
;:::;
(2.4.60)
convergestoitslimitinanumberofstepsandfor
i
=0
;
1
;:::;m
.
2.4.4SingularValueDecomposition
Inthispartwewillonlyreviewsomeimportantpropertiesofsingularvaluedecomposition.
Thedetailedtechniquesbyapplyingsingularvaluedecompositionareprovidedinthenext
chapter.
Singularvaluedecomposition(SVD)isaclassictopicinmatrixanalysisandnumeric
computation.Comparedwithpreviousiterationmethods,itsolvesthesolutionofthesystem
directly.Thedetailedmethodologyandadjustmentwillbeprovidedinthenextchapteras
ournewapproachtoROFmodel.
Foragiven
m

n
realorcomplexmatrix
A
,thereexistafactorizationformof
A
,
A
=
U

V

;
(2.4.61)
where
U
isa
m

m
unitarymatrix,isa
m

n
rectangulardiagonalmatrixwithnonnegative
realnumbersonthediagonal,and
V

istheconjugatetransposeof
V
asa
n

n
unitary
matrix.
Thediagonalentries
˙
j
ofaresocalledsingularvaluesof
A
,byconventionarranged
innon-increasingorder.
41
SVDcanbeusedforcomputingthepseudoinverseofamatrix
A
.Indeed,thepseudoin-
verseofmatrix
A
withitsSVD
A
=
U

V

is
A
+
=
V

+
U

;
where
+
isthepseudoinverseofformedbyreplacingeverynon-zerodiagonalentryby
itsreciprocalandtransposingtheresultingmatrix,and
U

istheconjugatetransposeof
U
.
AnotherimportantpropertyofSVDisthatif
A
isasymmetricreal
n

n
matrix,there
isanorthogonalmatrix
V
andadiagonalmatrix
D
suchthat
A
=
VDV
T
.Thenthisis
alsotheeigenvaluedecomposition.Thediagonalelementsof
D
aretheeigenvaluesof
A
in
descendingorder.
Ingeneral,ifamatrix
A
withsize
m

n
,then
A
T
A
isasymmetric
n

n
matrix.The
singularvaluedecompositionof
A
T
A
canbewrittenas
A
T
A
=
VDV
T
:
(2.4.62)
42
Chapter3
TechnicalDiscussions
3.1Reviewofotheralgorithms
3.1.1SplitBregmaniteration
Basedonpreviousdiscussionin2.4.2.3,weusethemodelprovidedin[22],byGoldsteinand
Osher,insteadofROFmodel(2.4.9),
arg
min
u
f

2
k
Au

f
k
2
2
+
J
(
u
)
g
:
(3.1.1)
Equivalently,
arg
min
u
f
1
2
k
Au

f
k
2
2
+

(
u
)
g
:
(3.1.2)
3.1.1.1AlgorithmofSplitBregman
ByapplyingsplitBregmanschemes(2.4.32)-(2.4.34),wehavethescheme,
(
u
k
+1
;d
k
+1
)=
arg
min
u;d
E
(
u;d
)

<p
k
u
;u

u
k
>

<p
k
d
;d

d
k
>
+

2
k

u
)

d
k
2
2
;
p
k
+1
u
=
p
k
u



T

u
k
+1
)

d
k
+1
)
;
p
k
+1
d
=
p
k
d


(
d
k
+1


u
k
+1
))
:
Let
b
k
=
p
k
d

,wehave
p
k
d
=

k
and
p
k
u
=



T
b
k
.ThenthegeneralsplitBregman
43
iterationis,
d
k
+1
=
arg
min
d
1

J
(
d
)

<b
k
;d

d
k
>
+
1
2
k

u
k
)

d
k
2
2
;
u
k
+1
=
arg
min
u
1

H
(
u
)+
<b
k
;

u

u
k
)
>
+
1
2
k
d
k
+1


u
k
)
k
2
2
;
b
k
+1
=
b
k

(
d
k
+1


u
k
+1
))
:
In[40,41,63,64],authorsusedthetansformed(3.1.1)to
arg
min
u
f
1
2
k
Au

f
k
2
2
+

k
u
k
1
g
:
(3.1.3)
Inthiscase,
J
(
u
)=

k
u
k
1
,=
I
,and
H
(
u
)=
1
2
k
Au

f
k
2
2
.Theiterationare
d
k
+1
=
arg
min
d


k
d
k
1

<b
k
;d

d
k
>
+
1
2
k
d

u
k
k
2
2
(3.1.4)
u
k
+1
=
arg
min
u
1
2

k
Au

f
k
2
2
+
<b
k
;u

u
k
>
+
1
2
k
d
k
+1

u
k
2
2
(3.1.5)
b
k
+1
=
b
k

d
k
+1
+
u
k
+1
:
(3.1.6)
Bysolving(3.1.4)and(3.1.5)explicitly,itresultsinasimplealgorithm,
Initialize
u
0
=
d
0
=
b
0
=0
While
k
u
k
+1

u
k
k
2
>
d
k
+1
=
shrink
(
u
k
+
b
k
;


)
u
k
+1
=(
"I
+
A
T
A
)

1
(
A
T
f
+

(
d
k
+1

b
k
))
b
k
+1
=
b
k

d
k
+1
+
u
k
+1
endWhile
44
where
shrink
(
v;t
)=(
˝
t
(
v
1
)
;˝
t
(
v
2
)
;

;˝
t
(
v
NL
))
T
with
˝
t
(
x
)=
sign
(
x
)max
fj
x
j
t;
0
g
.
The
shrink
(
v;t
)isasoftthreshholdfunction.Clearly,thestep
u
k
+1
=(
"I
+
A
T
A
)

1
(
A
T
f
+

(
d
k
+1

b
k
))(3.1.7)
bringsinerrorasaregularizationterm.WewillcomparethiswiththetheSVDmethod
appliedinthelaterpart.
3.1.1.2TwoSourcesandTwoMixtures
Letusstartwithsimpledeterminedcase,2sourcesand2mixtures,followingthesame
strategyas[40],[41],[63],[64].Aspreviously,2sourcesarebackgroundsource
S
1
andforegroundsource
S
2
,2mixturesare
X
1
and
X
2
.Itleadstomixingmodel
X
j
=
a
j;
1

S
1
+
a
j;
2

S
2
;
(3.1.8)
where
j
=1,2.Inordertoextractforegroundsource
S
2
,asweassumedpreviously,
S
2
=0,
where
a
6
t
6
b
,wehavetocancelationkernels
u
1
and
u
2
,suchthat
u
1

X
1
+
u
2

X
2
=
u
1

a
1
;
1

S
1
+
u
2

a
2
;
1

S
1
t
0
:
(3.1.9)
Anidealpairofsolutionsare
u
1
t
a
2
;
1
;u
2
t

a
1
;
1
:
(3.1.10)
Basedonpreviousdiscussioninquadraticprogramming,wecangettheoptimization
45
problemas
(
u

1
;u

2
)=
arg
min
(
u
1
;u
2
)
1
2
k
u
1

X
1
+
u
2

X
2
k
2
2
+

(
k
u
1
k
1
+
k
u
2
k
1
)
(3.1.11)
subjectto
u
1
(1)+
u
2
(1)=1.
Equivalently,theauthorsproposedproblem
(
u

1
;u

2
)=
arg
min
(
u
1
;u
2
)
1
2
k
u
1

X
1
+
u
2

X
2
k
2
2
+

2
2
(
2
X
j
=1
u
j
(1)

1)
2
+

(
k
u
1
k
1
+
k
u
2
k
1
)
:
(3.1.12)
Inmatrixform,(3.1.12)correspondsto(3.1.3)as
u

=
arg
min
u
f
1
2
k
Au

f
k
2
2
+

k
u
k
1
g
;
(3.1.13)
where,
A
=
2
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
4
X
1
(1)
X
1
(2)

X
1
(
m

2)
X
1
(
m

1)

X
1
(1)

X
1
(
m

3)
X
1
(
m

2)0
.
.
.
.
.
.
.
.
.
X
1
(1)

X
1
(
m

d
)0
X
2
(1)
X
2
(2)

X
2
(
m

2)
X
2
(
m

1)

X
2
(1)

X
2
(
m

3)
X
2
(
m

2)0
.
.
.
.
.
.
.
.
.
X
2
(1)

X
2
(
m

d
)0
3
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
5
T
;
46
f
=[00

0

]
T
;
X
1
=[
X
1
(1)
X
1
(2)

X
1
(
m

2)
X
1
(
m

1)]
T
;
X
2
=[
X
2
(1)
X
2
(2)

X
2
(
m

2)
X
2
(
m

1)]
T
;
m

1representsthelengthoftheaudiosignal,
f
withsize
m

1,and
d
representsthe
lengthofthecancellationkernel,
X
1
and
X
2
aretwomixtures.
3.1.1.3ThreeSourcesandThreeMixtures
Similarly,in3sourcesand3mixturescase,weshouldhave
(
u

1
;u

2
;u

3
)=
arg
min
(
u
1
;u
2
;u
3
)
1
2
k
u
1

X
1
+
u
2

X
2
+
u
3

X
3
k
2
2
+

2
2
(
3
X
j
=1
u
j
(1)

1)
2
+

(
k
u
1
k
1
+
k
u
2
k
1
+
k
u
3
k
1
)
:
(3.1.14)
47
Correspondingto(3.1.13),
A
=
2
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
4
X
1
(1)
X
1
(2)

X
1
(
m

2)
X
1
(
m

1)

X
1
(1)

X
1
(
m

3)
X
1
(
m

2)0
.
.
.
.
.
.
.
.
.
X
1
(1)

X
1
(
m

d
)0
X
2
(1)
X
2
(2)

X
2
(
m

2)
X
2
(
m

1)

X
2
(1)

X
2
(
m

3)
X
2
(
m

2)0
.
.
.
.
.
.
.
.
.
X
2
(1)

X
2
(
m

d
)0
X
3
(1)
X
3
(2)

X
3
(
m

2)
X
3
(
m

1)

X
3
(1)

X
3
(
m

3)
X
3
(
m

2)0
.
.
.
.
.
.
.
.
.
X
3
(1)

X
3
(
m

d
)0
3
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
5
T
:
f
=[00

0

]
T
;
X
1
=[
X
1
(1)
X
1
(2)

X
1
(
m

2)
X
1
(
m

1)]
T
;
X
2
=[
X
2
(1)
X
2
(2)

X
2
(
m

2)
X
2
(
m

1)]
T
;
X
3
=[
X
3
(1)
X
3
(2)

X
3
(
m

2)
X
3
(
m

1)]
T
;
where
m

1representsthelengthoftheaudiosignal;
f
isinsize
m

1;
d
representsthe
lengthofthecancellationkernel;
X
1
,
X
2
,and
X
3
arethreeentmixtures.
48
3.1.1.4
n
sourcesand
n
mixtures
Ingeneral,ifthere
n
sourcesand
n
mixtures,wearegoingtosolvethefollowingproblem,
(
u

1
;u

2
;u

3
;:::;u

n
)=
arg
min
(
u
1
;u
2
;u
3
;:::;u
n
)
1
2
k
n
X
j
=1
u
j

X
j
k
2
2
+

2
2
(
n
X
j
=1
u
j
(1)

1)
2
+

n
X
j
=1
k
u
j
k
1
:
(3.1.15)
Correspondingto(3.1.13),
A
=
2
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
4
X
1
(1)
X
1
(2)

X
1
(
m

2)
X
1
(
m

1)

X
1
(1)

X
1
(
m

3)
X
1
(
m

2)0
.
.
.
.
.
.
.
.
.
X
1
(1)

X
1
(
m

d
)0
X
2
(1)
X
2
(2)

X
2
(
m

2)
X
2
(
m

1)

X
2
(1)

X
2
(
m

3)
X
2
(
m

2)0
.
.
.
.
.
.
.
.
.
X
2
(1)

X
2
(
m

d
)0
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
X
n
(1)
X
n
(2)

X
n
(
m

2)
X
n
(
m

1)

X
n
(1)

X
n
(
m

3)
X
n
(
m

2)0
.
.
.
.
.
.
.
.
.
X
n
(1)

X
n
(
m

d
)0
3
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
5
T
:
49
f
=[00

0

]
T
;
X
1
=[
X
1
(1)
X
1
(2)

X
1
(
m

2)
X
1
(
m

1)]
T
;
X
2
=[
X
2
(1)
X
2
(2)

X
2
(
m

2)
X
2
(
m

1)]
T
;
.
.
.
X
n
=[
X
n
(1)
X
n
(2)

X
n
(
m

2)
X
n
(
m

1)]
T
;
where
m

1representsthelengthoftheaudiosignal;
f
isinsize
m

1;
d
representsthe
lengthofthecancellationkernel;
f
X
k
g
n
k
=1
are
n
tmixtures.
3.1.2ProximityOperator
Aspreviouslymentionedin2.4.3,theproximityoperatorhasbeenusedinimageprocessing.
WeuseittoestimatecancellationkernelsforBSS.Ingeneral,weconsiderthefollowing
model
arg
min
u
f
1
2
k
u

x
k
2
2
+(
'

B
)(
u
)
g
(3.1.16)
ComparedwiththeROFmodel(2.4.9),spusedinthiscase(2.4.38)
arg
min
u
f
1
2
k
u

x
k
2
2
+

j
u
j
TV
:
u
2
R
d
g
;
clearly,onejustneedstosetup
'
(
x
)=

k
x
k
1
:
Then
jj
TV
canberewrittenas
jj
TV
=
kk
1

B:
(3.1.17)
50
Next,theproblembecomes,
arg
min
u
f
1
2
k
u

x
k
2
2
+

k
Bu
k
1
g
(3.1.18)
3.1.2.1Algorithmofproximityoperator
Followedby(3.1.18),recallthealgorithmmentionedinSection2.4.3.4.
Given
x
;
<
1
4sin
2
(
N

1)
ˇ
2
N
,
>
0,

2
[0
;
1)
Initialize:
v
0
=0
For
n
=0
;
1
;:::
v
n
+1
:=

n
+(1


)(
I

prox



1
)(
Bx
+(
I

B
T
)
v
n
)
End
Writetheoutputof
v
n
fromtheaboveloopas
v
1
andcompute
prox
'

B
x
=
x


T
v
1
.
Bysolving
v
1
andreplacingthecorrespondingterminthelaststep,wehavethefollowing
algorithm.
Given
x,
<
1
4
sin

2
(
(
N

1)
ˇ
2
N
),
>
0,

2
[0
;
1)
Initialize
u
0
=0
While
k
u
k
+1

u
k
k
2
>
u
k
+1
=

k
+(1


)(
I

prox



1
)(
Bx
+(1

B
T
)
u
k
)
endWhile
u
=(
"I
+
B
T
B
)

1
B
T
x

u
k
+1
.
where
prox



1
x
=(
prox



1
x
(1)
;prox



1
x
(2)
;

;prox



1
x
(
d
))
T
,with
prox



1
x
=
max
fj
x
j


;
0
g
sign
(
x
),and
"I
isaregularizationterm.
51
3.1.2.2ApplicationforBSSofAudioSignalProcessing
Inthispartwechangethealgorithmintheformwecanusetosolvecancellationkernels.
SincethemodelfrompreviousROFmodelis(3.1.3),andbychangingtheparameters,we
shouldhave
arg
min
w
f
1
2
k
w

f
k
2
2
+

k
w
k
1
g
:
(3.1.19)
Ifweassume
w
=
Au
,thereisanequivalentproblem
arg
min
u
f
1
2
k
Au

f
k
2
2
+

k
Au
k
1
g
:
(3.1.20)
Thenwecantransferittoasimilarproblem,
arg
min
u
f
1
2
k
u

(
A
T
A
)

1
A
T
f
k
2
2
+

k
(
A
T
A
)

1
A
T
Au
k
1
g
;
i.e.,
arg
min
u
f
1
2
k
u

(
A
T
A
)

1
A
T
f
k
2
2
+

k
u
k
1
g
;
(3.1.21)
where
B
=
I
.
ByapplyingthealgorithminSection3.1.2.1,
Initialize
u
0
=0
While
k
u
k
+1

u
k
k
2
>
u
k
+1
=

k
+(1


)
prox



1
((
"I
+(
A
T
A
))

1
A
T
f
+(1


)
u
k
)
endWhile
u
=(
"I
+(
A
T
A
))

1
A
T
f

u
k
+1
.
where
prox



1
x
=(
prox



1
x
(1)
;prox



1
x
(2)
;

;prox



1
x
(
d
))
T
,with
prox



1
x
=
52
max
fj
x
j


;
0
g
sign
(
x
),
"I
isaregularizationterm.
The
prox



1
x
functionisasoftthreshholdfunctionwhichisthesameaspreviously
mentionedinsplitBregmanalgorithm3.1.1.1.Thestep
u
=(
"I
+(
A
T
A
))

1
A
T
f

u
k
+1
(3.1.22)
alsobringsinerrorfromaregularizationterm.Atleastthisstepisatthesamelevelas
(3.1.7)insplitBregman.WecancomparethiswiththetheSVDmethodappliedinthe
laterpart.
3.1.2.3TwoSourcesandTwoMixturescase
Whenweconsiderthedeterminedtwosourcesandtwomixturescase,thematrix
A
isthe
sameasinSection3.1.1.2.
A
=
2
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
4
X
1
(1)
X
1
(2)

X
1
(
m

2)
X
1
(
m

1)

X
1
(1)

X
1
(
m

3)
X
1
(
m

2)0
.
.
.
.
.
.
.
.
.
X
1
(1)

X
1
(
m

d
)0
X
2
(1)
X
2
(2)

X
2
(
m

2)
X
2
(
m

1)

X
2
(1)

X
2
(
m

3)
X
2
(
m

2)0
.
.
.
.
.
.
.
.
.
X
2
(1)

X
2
(
m

d
)0
3
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
5
T
;
53
f
=[00

0

]
T
;
X
1
=[
X
1
(1)
X
1
(2)

X
1
(
m

2)
X
1
(
m

1)]
T
;
X
2
=[
X
2
(1)
X
2
(2)

X
2
(
m

2)
X
2
(
m

1)]
T
;
where
m

1representsthelengthoftheaudiosignal;
f
isinsize
m

1;
d
representsthe
lengthofthecancellationkernel;
X
1
and
X
2
aretwomixtures.
3.1.2.4ThreeSourcesandThreeMixturescase
Asthreesourcesandthreemixturescase,wehavethesamematrix
A
,andothercorrespond-
ingparametersasinSection3.1.1.3.
3.1.2.5
n
Sourcesand
n
Mixturescase
Ingeneral,fordetermined
n
sourcesand
n
mixturescase,thematrix
A
andotherparameters
areasthesameasinSection3.1.1.4.
3.2QuadraticProgramming
3.2.1AlgorithmforSparseness
Thealgorithmforthelearningprocessislistedasfollowed.Assumetheforegroundsources
S
1
;:::;S
L
areinactive(silent)when
t
2
[
a
+
N;b
].
Take
[
s
1
;e
1
]and[
s
2
;e
2
]from[
a
+
N;b
],[
s
1
;e
1
]
T
[
s
2
;e
2
]=
;
.
forj
=1:
Q
1
Randomlychoose[
s
1
;j
;e
1
;j
]
ˆ
[
s
1
;e
1
]and[
s
2
;j
;e
2
;j
]
ˆ
[
s
2
;e
2
];
54
whileq
nnz
>
C
+
n
sp
and
n
sp
>
1
(
a
)Solve
f
b
k
g
on[
s
1
;j
;e
1
;j
];
(
b
)Finditserrorbyequation(2.4.12)on[
s
2
;j
;e
2
;j
];
(
c
)Force
n
sp
=0
:
1

q
nnz
smallestelementsof
fj
b
k
jg
be0,
q
nnz
=numberofnonzeroelementsin
f
b
k
g
,
q
nnz
=0
:
9
q
nnz
;
end
Recordpositionsofnonzeroelementsin
f
b
k
g
withminimum
error;
end
Get
thefrequencyofallthepositionsin
f
b
k
g
withnonzerovalues,
V
freq
.
Inourwork,itturnsout
Q
1
>
40,sinceitdoesnotworkwellinsomecasesif
Q
1
<
40.
Forintervals[
s
1
;j
;e
1
;j
]and[
s
2
;j
;e
2
;j
],thelengthshouldbeatleast1second.
Thealgorithmforoptimalcancelationkernelsdescribedasthesecondstageisasbelow.
Divide
[
s
1
;e
1
]into
Q
2
equalsubintervals
I
1
;:::;I
Q
2
;
n
V
freq
isthenumberofnonzeroelementsof
V
freq
;
whileq
6
C
and
q
6
n
V
freq
(
a
)Take
q
highestfrequencypositionsof
f
b
k
g
by
V
freq
and
forcetheresttobe0;
(
b
)Compute
f
b
k
g
on[
s
1
;e
1
];
(
c
)Solveerroron
I
1
;:::;I
Q
2
by(2.4.12)andtheirmean,
Err
mean
;
(
d
)
q
=1
:
1
q
;
end
Get
f
b
k
g
withminimum
Err
mean
;
Byequation(1.2.6)and(2.3.7),foregroundsourcescouldbeextracted.
55
Quadraticprogrammingisagoodtooltoprovidegoodestimateofcancellationkernels
[61].Ourapproachaimstobringsparsenesstothecancellationkernels.Itworkstheoretically
whichcanbeprovedbythenumericalexperimentsinthenextchapterviathe
mixedaudios.However,fortherealliferecordings,itonlyworksOKontwosourcestwo
mixturescase.
3.3SingularValueDecomposition
Otherthanapproximationmethodsmentionedabove,wecanalsoseetheproblemfrom
anotherangle.Wecansolvetheproblembydirectmethod,suchassingularvaluedecom-
position(SVD).Letusconsiderthefollowingproblem.
arg
min
u
f
1
2
k
Au

f
k
2
2
g
where
u
=(
u
T
1
;u
T
2
;:::;u
T
n
)
T
,subjectto
P
n
j
=1
u
j
(1)=1.
3.3.1OurMethodology
Weindeedjustneedtosolvetheequation,
Au
=
f:
(3.3.23)
Sincematrix
A
canrarelybeasquarematrix,inordertosolve(3.3.23),weneedto
transformitto
A
T
Au
=
A
T
f:
(3.3.24)
56
Asmentionedpreviously2.4.62,
A
T
A
isasymmetricpositivematrix.Thuswe
apply
SVD
methodtosolveit.
VDV
T
=
A
T
A:
(3.3.25)
Moreover,asamatrix
A
hasitsownSVD
A
=
U

V
T
:
(3.3.26)
Matrix
D
=
T

So
VDV
T
u
=
A
T
f
(3.3.27)
=
)
u
=
VD

1
V
T
A
T
f
(3.3.28)
=
)
u
=
VD

1
V
T
V

U
T
f
(3.3.29)
=
)
u
=
VD

1

U
T
f:
(3.3.30)
Theoretically(3.3.28)shouldbeperfectforsolvingtheproblem(3.3.23).Unfortunately,
thesingularvaluesof
A
T
A
arenotwelldistributed,whichmeanstheconditionnumber
of
A
T
A
isverylarge.Thisresultsinalargeerror,sometimesmayalsomakethesystem
unsolvable.
AswecanknowfromSVD,thediagonalelementsofthematrix
D
areallthesingular
valuesof
A
T
A
.
diag
(
D
)=[
˙
1
;˙
2
;:::;˙
n
]
T
;
(3.3.31)
indescendingorder.SimilarlyaspreviousinSection3.1.2.2,weneedtoaddaregularization
57
termtothediagonalofmatrix
D
.Insteadofusing
"I
,wecanadjustthediagonalofthis
relaxationmatrixmorespcorrespondto
D
.
Sincethe
k
valuesof
D
,
˙
1
;˙
2
;:::;˙
k
arethepartswhichwillnotcauseahuge
problem,startingfromthe(
k
+1)thitemofthediagonalof
D
,weaddaregularizationterm
toeachcorrespondingterminthediagonalof
D
.Then,
diag
(
D
):=[
˙
1
;˙
2
;:::;˙
k
;˙
k
+1
+
"
2
k
+1
;:::;˙
n
+
"
2
n
]
T
:
(3.3.32)
Thiswillygiveamoreaccuratecomputationalresult,comparedwithonlyadding
aregularizationtermtoalltheitemsinthediagonalof
D
.Thetechniqueofaddinga
regularizationtermtoalldiagonalelementsisequivalentassolvingtheinverseterm(
"I
+
A
T
A
)

1
oftheregularizationstep(3.1.7)insplitBregmanandthesamepartof(3.1.22)
inproximityoperator.ItclearlyindicatesthatsplitBregmanandproximityoperatormay
takesameamountoftimetosolvetheinverseterm.
Thisideaalsoinspiresthatwecanusethespecialpropertyof
D

1
toreducethe
computationaltimefromabovetechnique.Because
D
=
T
wecanestimatethatthe
diagonalelementsof
D

1
arearound
f
1
p
˙
k
g
level.Thefollowinggraphisaportionofthe
plotfor
f
1
˙
k
g
.
58
Figure1:Plotof
f
1
˙
k
g
.
Wecanpre-selectapositivenumber

0
,thenthereexistsa
K
suchthat
p
˙
K
+1
6

0
<
p
˙
K
.Thenusethevalueofthetangentlinetoreplacetheleftpartoftheplot.
Figure2:Plotof
f
1
˙
k
g
withtangentline.
Inourcomputation,werealizethistechniquebycreatingthetangentlinetotheplotof
1
˙
k
atpoint(
˙
K
,
1
˙
K
).Thecorrespondingslopeatthatpointis

1
˙
2
K
.Byalgebra,wecan
59
theequationofthelineinpointslopeform
y
=

1
˙
2
K
x
+
2
˙
K
:
(3.3.33)
Thus,wecanreplacethe
1
˙
j
elementfor
j
>
K
+1in
D

1
as

1
˙
2
K
˙
j
+
2
˙
K
,whichalso
meanswecanreplace
˙
j
with
1

1
˙
2
K
˙
j
+
2
˙
K
.
Since
1

1
˙
2
K
˙
j
+
2
˙
K
=
˙
2
K

˙
j
+2
˙
K
,and
f
˙
k
g
n
k
=1
decaysdramaticallyfast,itcanbederived
as
˙
2
K

˙
j
+2
˙
K
ˇ
˙
K
2
forlarge
j
.
Basedonournumericalexamples,especiallytherealliferecordings,theratio
˙
k
˙
1
ˇ
10

4
when150
6
k
6
200andthemaxdelayis230.Wecansimplyreplace
˙
j
with
˙
K
2
when
j
islargeenough.Inournumericalresults,weuse
˙
j
=
˙
K
2
when
j
>
5
K
4
.
Ingeneral,wecanthediagonalelementsinthematrix
D
d
j;j
=
8
>
>
>
>
>
>
>
>
<
>
>
>
>
>
>
>
>
:
˙
j
if
j
6
K;
˙
2
K

˙
j
+2
˙
K
if
K
6
j<
5
K
4
;
˙
K
2
otherwise
;
where1
6
j
6
n
.
60
3.3.2TwoSourcesandTwoMixtures
Inthedeterminedtwosourcesandtwomixturescase,thematrix
A
andothercorresponding
parametersarethesameasinSection3.1.1.2.
A
=
2
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
4
X
1
(1)
X
1
(2)

X
1
(
m

2)
X
1
(
m

1)

X
1
(1)

X
1
(
m

3)
X
1
(
m

2)0
.
.
.
.
.
.
.
.
.
X
1
(1)

X
1
(
m

d
)0
X
2
(1)
X
2
(2)

X
2
(
m

2)
X
2
(
m

1)

X
2
(1)

X
2
(
m

3)
X
2
(
m

2)0
.
.
.
.
.
.
.
.
.
X
2
(1)

X
2
(
m

d
)0
3
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
5
T
;
f
=[00

0

]
T
;
X
1
=[
X
1
(1)
X
1
(2)

X
1
(
m

2)
X
1
(
m

1)]
T
;
X
2
=[
X
2
(1)
X
2
(2)

X
2
(
m

2)
X
2
(
m

1)]
T
;
where
m

1representsthelengthoftheaudiosignal;
f
isinsize
m

1;
d
representsthe
lengthofthecancellationkernel;
X
1
and
X
2
aretwomixtures.
61
3.3.3ThreeSourcesandThreeMixtures
Inthreesourcesandthreemixturescase,thematrix
A
andothercorrespondingparameters
arethesameasinSection3.1.1.3.
3.3.4
n
Sourcesand
n
Mixtures
Ingeneral,for
n
sourcesand
n
mixturescase,thematrix
A
andotherparametersare
thesameasinSection3.1.1.4.
62
Chapter4
NumericalResults
Inthischapter,weprovideseveralnumericalexperiments,mostofthemarefromreallife
recordings.Themixedaudiosareonlyusedforquadraticprogrammingtoshow
thatitworkstheoretically.
Basedontheperformance,wecanconcludethatourmoSVDisthebest,and
proximityoperatorisslightlybetterthansplitBregmanincomputationaltime.
4.1NumericalExampleofQuadraticProgramming
4.1.1NumericalExamplesofTwoSourcesandTwoMixtures
4.1.1.1Example
1
Inthisexample,thebackgroundmusicstartsThedesiredforegroundsourceissilent
forafewseconds,anditiscompletelyoverwhelmedbythebackgroundmusic.Basedon
thework[61],wecanrequirecancellationkernelstobenon-negative,oronlyfewofthem
beingnegative,inquadraticprogramming.Inthisway,wewillnotseesomecancelation
kernelswithlargemagnitudeinnegativedirections,whichalsomakemoresense,because
soundsourcesaremorethanabsorbedinnormalroomcondition.Themathematical
theorybehindthisscenariodeservesfurtherinvestigation,suchas[65].However,
itisnotapartwefocuseoninthisstudy.
63
Inordertosolveit,severalparametershavetakenthefollowingvalues,thesamplefre-
quency
SF
=16000
Hz
,thelengthofeachcancellationkernel
d
=230,thelearningtime
interval[14
;
15],thepercentageofnonzerocancellationkernels
r
=15%.Moreover,10%
ofallthesenonzerocancellationkernelsarenegativevaluestorepresenttheabsorptions.
Thebelowshowsthetwomixturesbeforeseparationandthenormalizedresultafter
removalofthebackgroundmusic.Inordertopicktheimportantcancellationelements,the
iterativeselectionhasbeenrun80times.Thewholeprocesstakes170seconds.
Figure3:Recordedmixturesandresultafterremovalofbackgroundmusic.
Thefollowingshowsthevalueofthecorrespondingcancelationkernels.
Figure4:Cancelationkernels.
Itlooksliketheresultisnotverygoodbasedonthethirdplotofthenormalizedresult.
64
However,thetruthisthattheresultisnotasexpected,evenifwedidseparatetheforeground
source.Theforegroundsourcecanbeheard,anditisnotoverwhelmedbybackgroundmusic
comparedwithoriginalmixture.Butthereisstilladefectthatthebackgroundnoiseisa
littleloud.Thereasonisthatthebackgroundmusicissoloudcomparedtotheforeground
source.Ifweneedbetterresultwehavetouselargerdelayorlongerlearningtimeinterval,
whichwillthecomputationaltime.
ThiscanbeshowninthespectrogramplotbelowbySTFTandHannwindow.The
widowsizeis512with500overlaps.Theplotistheoriginalmixtureduringthetime
interval[15
;
17],theotheroneistheresultafterremovalthebackgroundduringthesame
timeinterval.Wecanseefromthethatthespectrogramoftheforegroundsource
canbeclearlyseenfromthesecondplotbetweenthetimeinterval[16
;
16
:
5],whileitcanbe
hardlyseenintheplot.
Figure5:Spectrogram.
Inordertoevaluatetheperformance,anewquantity,relativeerror,isintroduced,and
65
as,
f
2

P
a
+
N
6
t
6
b
[
A
T
F
(
t
)

B
T
G
(
t
)]
2
P
a
+
N
6
t
6
b
[(
A
T
F
(
t
))
2
+(
B
T
G
(
t
))
2
]
g
1
2
:
Therelativeerrorofthisexampleis23
:
34%.
4.1.1.2Example
2
Inthisexample,thebackgroundmusicstartsThedesiredforegroundsourceissilent
forafewseconds,anditisalittleweakerthanthebackgroundmusic.
Samevaluesfortheparametersaretakeninthecomputation,thesamplefrequency
SF
=16000
Hz
,thelengthofeachcancellationkernel
d
=230,thelearningtimeinterval
[14
;
15],percentageofnonzerocancellationkernels
r
=15%,and10%ofthesecancellation
kernelsarenegative.Theiterativeselectionhasbeenrun80times.
Thebelowshowsthetwomixturesbeforeseparationandresultafterremovalof
thebackgroundmusic.Ittakes160secondstocompletethecomputation.
Figure6:Recordedmixturesandresultafterremovalofbackgroundmusic.
66
Figure7:Cancelationkernels.
Thecorrespondingspectrogramoftimeinterval[15
;
17]whentheforegroundsource
startedisalsoshownbelowbyapplyingSTFTandHannwindowfunction.Sameasthe
previousexample,thewidowsizeis512with500overlaps.Theplotisfortheoriginal
mixture,andtheotheroneisfortheremovalresult.Intherstoneitcanhardlytellthe
betweenthebackgroundmusicandtheforegroundsource.Inthesecondplot,it
clearlyshowstheforegroundsourcestartedbetweentimeinterval[15
:
5
;
16],whiletheback-
groundmusichasbeenremovedtoalargeextend.Wecanseethisfactfromthespectrogram
oftheforegroundsourceinthesecondplot.
67
Figure8:Spectrogram.
Therelativeerrorofthisexampleis22
:
48%.
4.1.1.3Example
3
Inthisexample,theaudioismixed,notfromrealrecordings.Therearetwo
sourcesbeingused.Oneisabackgroundmusic,andtheotheroneisahumanspeech.
Byrandomlychoosingthesamplefrequency
SF
=16000
Hz
,thelengthofeachcan-
cellationkernel
d
=230,thepercentageofnonzerocancellationkernels
r
=15%,and
elementofthecancellationkernelnon-zero,and10%ofthesecancellationkernelsare
negative,itappliestheconvolutionformulatomixtherecordings.
Similaras
Example
1,thebackgoundmusicstartsThedesiredforegroundsource
issilentforafewseconds,andisnotoverwhelmedbythebackgroundmusic.
Alltheparametersaretakenthesamevaluesforsolvingthesystem,whilethelearning
timeintervalusedis[9
;
10].Thebelowshowsthetwomixturesbeforeseparationand
68
resultafterremovalofthebackgroundmusicwithoutanynormalization.
Figure9:mixturesandresultaftertheremovalofbackgroundsource.
Clearly,thebackgroundmusichasbeensuccessfullycompletelyremoved.Itshowsthe
factthatthismethodologyworkstheoretically.
Thefollowingshowsthevalueofthecorrespondingcancelationkernels.
Figure10:Cancelationkernels.
Thecancellationkernelsarenotasidealasexpected.Itonlyneedstopickafewelements
fromcancellationkernelstosolvethesystem.Thisisnotasurprise,sincethear
mixturesaresimplyformedbyusingtheconvolutionnotation.Theoptimizationproblem
canbesolvedbyotherestimations.
69
Therelativeerrorinthisexampleislessthan0
:
19%.
4.1.2NumericalExamplesofThreeSourcesandThreeMixtures
4.1.2.1Example
4
Inthisexample,threesinglechannelspeechsignalsarearmixedtomake3
entmixtures.Ineachofthem,thethirdsource
S
3
issilentforafewseconds,anditis
overwhelmedbyotherbackgrounds.
Themixingprocessissimilartopreviousexamplein4.1.1.3.Thesamevaluesof
parametersaretakenforproducingmitures,thesamplefrequency
SF
=16000
Hz
,thelength
ofeachcancellationkernel
d
=230,percentageofnonzerocancellationkernels
r
=15%,
andelementofthecancellationkernelnon-zero,and10%ofthesecancellationkernels
arenegative.
Theparametersforsolvingthesystemarethesameasthemixingprocess,whilethetime
interval[9
;
10].
Thebelowshowsthatthreemixturesbeforeseparationandresultaftertheremoval
oftwobackgroundsources.
70
g
Figure11:3mixturesandresultaftertheremovalofbackgroundsource.
Basedonthefourthplot,themarjorityenergyofthetwobackgroundsisclearly
removed,thoughthereisstillsomesmallportionleft.
Thebelowshowsthecancelationkernels.
71
Figure12:Cancelationkernels.
Thecancellationkernelsarenotasidealasexpected.Itonlyneedstopickafewelements
fromcancellationkernelstoprovidethesolution.Thisisnotasurprise,sincethe
mixturesareonlysimplyformedbyusingtheconvolutionnotation.Theoptimizationprob-
lemcanbesolvedbyotherestimations.
Therelativeerroris3
:
3%.Ittakes80secondstoeliminatingbackgroundsignals.
4.2NumericalExamplesofSVDMethod
Inthispart,weapplyourmoSVDmethoddevelopedinSection3.3tothesame
examplesofrealliferecordings.Inthefollowingnumericalexamples,itwilldemonstrate
thatourmoSVDisaveryfastalgorithmandprovidesgoodresults.
72
4.2.1TwoSourcesTwoMixturescase
4.2.1.1Example
5
ByusingthesameaudiorecordingsfromExample1insection4.1.1.1,wesolvetheproblem
byusingSVDmethod.
Forthecorrespondingparameters,samplefrequency
SF
=16000
Hz
,lengthofeach
cancellationkernel
d
=230,thetimeinterval[14
;
15],

0
isthevalue
p
˙
K
when
˙
K
+1
˙
1
6
10

4
6
˙
K
˙
1
.
ThenwehavethefollowingresultasshownintheItonlytakes0
:
158tosolvethe
SVDprocesstothesigularvalue
˙
K
withrelativeerror5
:
1%.
Figure13:Recordedmixturesandresultsaftertheremovalofbackgroundsource.
Thecorrespondingspectrogramoftimeinterval[15
;
17]whentheforegroundsource
startedisalsoshownbelowbyapplyingSTFTandHannwindowfunction.Sameasthe
previousexample,thewidowsizeis512with500overlaps.
73
Figure14:Spectrogram.
Theoneisfortheoriginalmixture,whilethesecondoneisfortheresult.Fromthe
secondplot,thespectrogramoftheforegroundsourcecanbeclearlyseenbetweenthetime
interval[16
;
16
:
5],whileitcanhardlyseenintheplot.ComparedwithExample1,alot
lowfrequencyenergyhasbeenremovedcomparedwiththesecondplotinFigure5,especially
forthefrequenciesbetween[0
;
500].SothereisimprovementfromExample1to
Example5.
4.2.1.2Example
6
UsingthesameaudiorecordingsfromExample2insection4.1.1.2,wesolvetheproblemby
usingSVDmethod.
Forthecorrespondingparameters,samplefrequency
SF
=16000
Hz
,lengthofeach
cancellationkernel
d
=230,thetimeinterval[14
;
15],

0
isthevalue
p
˙
K
when
˙
K
+1
˙
1
6
10

4
6
˙
K
˙
1
.
74
ThenwehavethefollowingresultasshownintheIttakes0
:
172tosolvetheSVD
processtothesigularvalue
˙
K
withrelativeerror6
:
02%
Figure15:Recordedmixturesandresultsaftertheremovalofbackgroundsource.
ThefollowingpartusesSTFTandHannwindowfunctiontocheckthespectrogramof
themixtureandresultbetweentimeinterval[15
;
17].Sameasthepreviousexample,the
widowsizeis512with500overlaps.
Figure16:Spectrogram.
75
Theplotisfortheoriginalmixture,whilethesecondoneisfortheresult.Fromthe
secondplot,thespectrogramoftheforegroundsourcecanbeclearlyseenbetweenthetime
interval[15
:
5
;
16],whilethemajorityofthesourcehasbeeneliminated.Comparedwith
Example2,alotlowfrequencyenergyhasbeenremovedcomparedwiththesecondplotin
Figure8,especiallyforthefrequenciesbetween[0
;
500].Sothereisimprovement
fromExample2toExample6.
4.2.2ThreeSourcesThreeMixtures
4.2.2.1Example
7
Inthisexample,thesourceismusic;theothertwosourcesarespeechesoftwopeople.
Thesecondsourcestartsafewsecondslaterthanthesource.Andthethirdsource
startsafewsecondslaterthanthesecondone.WeuseourmoSVDmethodtoremove
towsourcesandkeepthethirdsource.
Forthecorrespondingparameters,samplefrequency
SF
=16000
Hz
,lengthofeach
cancellationkernel
d
=230,thetimeinterval[18
;
19],

0
isthevalue
p
˙
K
when
˙
K
+1
˙
1
6
10

4
6
˙
K
˙
1
.
Thefollowingaretheoriginalaudiosignalsandresultfromtheabovemethod.
76
Figure17:Recordedmixturesandresultsaftertheremovalofbackgroundsources.
Clearly,thetwosourceshavebeenlargelyremovedinthefourthplot.Sincewe
normalizedtheresulttothemaximumof0
:
95,itmaylooklikethatthereisstillalarge
portionoftwosourcesintheresult.Infact,theresultisverygood.Therelativeerror
is11
:
2%.
4.2.2.2Example
8
Inthisexample,allthreesourcesarehumanspeeches.Thesecondsourcestartsafewseconds
laterthantheone.Andthethirdonestartsafewsecondslaterthanthesecondone.
WeusetheSVDmethodtoremovethetwosourcesandextractthethirdone.
Forthecorrespondingparameters,samplefrequency
SF
=16000
Hz
,lengthofeach
cancellationkernel
d
=230,thetimeinterval[14
;
15],

0
isthevalue
p
˙
K
when
˙
K
+1
˙
1
6
77
10

4
6
˙
K
˙
1
.
Thefollowingaretheoriginalaudiosignalsandresultsfromthismethod.
Figure18:Recordedmixturesandresultsaftertheremovalofbackgroundsources.
Basedonaboveplot,thetwosourceshavebeenlargelyremovedinthefourthplot.
Sincewenormalizedtheresulttothemaximumof0
:
95,itmaylooklikethatthereisstilla
largeportionoftwosourcesintheresult.Infact,theresultisverygood.Therelative
erroris14
:
6%.
Ingeneral,ourmoSVDprovidesverygoodresults.
4.3NumericalExamplesofSplitBregmanIteration
Inthefollowingexamples,wechoose

=

=10

3
,

=1,

=2

sameas[40].
78
4.3.1Twosourcestwomixturescase
4.3.1.1Example
9
ByusingthesameaudiorecordingsfromExample1insection4.1.1.1,wehavethefollowing
resultasshownintheFigure19.
Figure19:Recordedmixturesandresultaftertheremovalofbackgroundmusic.
Therelativeerrorforthisexampleis4
:
5%.
4.3.1.2Example
10
ByusingthesameaudiorecordingsfromExample2insection4.1.1.2,wehavethefollowing
resultasshownintheFigure20.
79
Figure20:Recordedmixturesandresultaftertheremovalofbackgroundmusic.
Therelativeerrorforthisexampleis4
:
1%.
4.3.2Threesourcesthreemixtures
4.3.2.1Example
11
Inthisexample,weusethesameaudiofromExample7insection4.2.2.1.Therearetwo
waystoremovetheforegroundsources.OneistousethesplitBregmaniterationdirectly
forthemixtures.
Theotheristoremovethesourcebytwogroupsofttwomixtureslikewhat
weusefortwosourcestwomixturescase.Thenusethecorrespondingresultstoremovethe
secondsource.
ThefollowingplotsinFigure21aretheoriginalaudiosignalsandtheresultsfromthe
twowaysmentionedabove.
80
Figure21:Recordedmixturesandresultsaftertheremovalofbackgroundsources.
4.3.2.2Example
12
Inthisexample,weusethesameaudiofromExample8insection4.2.2.2.Weusethe
similartwowayslistedinExample11insection4.3.2.1tosolvetheproblem.
ThefollowingplotsinFigure22aretheoriginalaudiosignalsandresultsfromtheabove
twoapproachesmentionedinExample11.
81
Figure22:Recordedmixturesandresultsaftertheremovalofbackgroundsources.
4.4NumericalExamplesofProximityOperatorMethod
Inthefollowingexamples,wechoose

=0and

=
1
4
sameas[37].
Ingeneral,theproximityoperatorisslightlybetterthansplitBregman,butthecompu-
tationaltimeisslowerthanourmoSVD.Itdeservesmoreinvestigationsfor
morereasonisbehindthisphenomena.
82
4.4.1Twosourcestwomixturescase
4.4.1.1Example
13
ByusingthesameaudiorecordingsfromExample1insection4.1.1.1,wesolvetheproblem
byusingproximityoperatormethod.Thenwehavethefollowingresultasshowninthe
Figure23.
Figure23:Recordedmixturesandresultsaftertheremovalofbackgroundsource.
Therelativeerrorforthisexampleis4
:
5%.
4.4.1.2Example
14
UsingthesameaudiorecordingsfromExample2insection4.1.1.2,wesolvetheproblem
byusingproximityoperatormethod.Thenwehavethefollowingresultasshowninthe
Figure24.
83
Figure24:Recordedmixturesandresultsaftertheremovalofbackgroundsource.
Therelativeerrorforthisexampleis3
:
9%.
4.4.2ThreeSourcesThreeMixtures
4.4.2.1Example
15
Inthisexample,weusethesameaudiofromExample7inSection4.2.2.1.Therearetwo
methodstoremovetheforegroundsources.Oneistousetheproximityoperatordirectly.
Theotheristoremovethesourcebytwogroupsofttwomixtureslikewhat
weusefortwosourcestwomixturescasebyproximityoperatormethod.Thenusethe
correspondingresultstoremovethesecondsource.
ThefollowingplotsinFigure25aretheoriginalaudiosignalsandresultsfromtheabove
twoways.
84
Figure25:Recordedmixturesandresultsafterremovalofbackgroundsources.
4.4.2.2Example
16
Inthisexampleexample,weusethesameaudiofromExample8inSection4.2.2.2.There
aretwomethodstoremovetheforegroundsources.Oneistousetheproximityoperator
directlyonthreemixutrestosolvetheproblem.twogroupsofttwomixtureslike
whatweusefortwosourcestwomixturescasebyproximityoperatormethod.Thenusethe
correspondingresultstoremovethesecondsource.
ThefollowingplotsinFigure26aretheoriginalaudiosignalsandresultsfromtheabove
twoways.
85
Figure26:Recordedmixturesandresultsaftertheremovalofbackgroundsources.
4.5Summarization
WeuseasystemwithCPUIntelCorei7

4770and16GBDDR3800MHzmemorytorun
alltheabovenumericalexamples.
Aslistedabove,thereisabigperformancebetweenquadraticprogramming
withsparsenessandthemoSVD.Clearly,theperformanceofSVDmethodisbetter
thanthequadraticprogram.Moreover,basedontheanalysisofSection3.3,theSVDmethod
isatleastatthesamelevelofcomputaitonaltimecomparedwithproximityoperatormethod
andsplitBregman.
Inournumericalresults,ourmoSVDdoeshavethebestperformance.Itisfastest
withthesamelevelofrelativeerrorcomparedwithproximityoperatorandsplitBregman,
86
especiallywhenweconsiderasmalllengthofeachcancellationkernel
d
=230.Proximity
operatormethodisslightlybetterthansplitBregmaniterationintermscomputationaltime
buttheydohavethesamelevelofrelativeerror.
87
BIBLIOGRAPHY
88
BIBLIOGRAPHY
[1]
S.Alliney.
Apropertyoftheminimumvectorsofaregularizingfunctionaldby
meanoftheabsolutenorm
.IEEETransactionsonSignalProcessing,451997,pp.913-
917.
[2]
S.I.Amari,A.Cichocki,andH.H.Yang.
Anewlearningalgorithmforblindsignal
separation
.Advancesinneuralinformationprocessingsystems(1996):757-763.
[3]
S.Araki,S.Makino,H.Sawada,andR.Mukai.
Reducingmusicalnoisebya
overlap-addmethodappliedtosourceseparationusingatime-frequencymask
.Proc.
ICASSP,III,81-84,2005.
[4]
J.Allen,andL.Rabiner.
Adapproachtoshort-timeFourieranalysisandsynthe-
sis
.ProceedingsoftheIEEE,Vol.65,NO.11,Nov.1977.
[5]
L.Bregman.
Therelaxationmethodofthecommonpointsofconvexsetsand
itsapplicationtothesolutionofproblemsinconvexoptimization
.USSRComputational
MathematicsandMathematicalPhysics,1967,7,pp.200-217.
[6]
A.Bell,andT.Sejnowski.
Aninformation-maximizationapproachtoblindseparation
andblinddeconvolution
.NeuralComputation,1995,7(6),pp.1129-1159.
[7]
R.Blackman,andJ.Tukey.
Themeasurementofpowerspectrafromthepointofview
ofcommunicationsEngineering
.1958,DoverPublicationInc.,NewYork,pp.170.
[8]
J.Cai,S.Osher,andZ.Shen.
LinearizedBregmaniterationsforcompressedsensing.
MathematicsofComputation78.267(2009):1515-1536.
[9]
J.Cai,S.Osher,andZ.Shen.
SplitBregmanmethodsandframebasedimagerestoration
.
MultiscaleModel.Simul.,Vol.8(2),2010,pp.337-369.
[10]
J.F.Cardoso.
Sourcesseparationusinghigherordermoments
.Proc.Internat.Conf.
Acoust.SpeechSignalProcess.,Glasgow,1989,pp.2109-2112.
[11]
J.F.Cardoso,andA.Souloumiac.
Blindbeamformingfornon-Gaussiansignals
.IEE
ProceedingsF(RadarandSignalProcessing).Vol.140.No.6.1993.
89
[12]
A.CichockiandS.Amari.
Adaptiveblindsignalandimageprocessing:learningalgo-
rithmsandapplications
.Wiley,2002.
[13]
S.Choi,A.Cichocki,H.ParkandS.Lee.
Blindscourcesepararionandindependent
componentanalysis:Areview
.NeuralInform.Process.Lett.Rev.,6,2005,pp.1-57.
[14]
P.Combettes.
Convexiteetsignal
.Proc.CongresdeMathematiquesAppliqueesetIn-
dustriellesSMAI.Vol.1,2001.
[15]
P.Combettes,andV.Wajs.
Signalrecoverybyproximalforward-backwardsplitting
.
MutiscaleModel.Simul.,2005,4,pp.1168-1200.
[16]
P.Combettes,andJ.Pesquet.
Proximalsplittingmethodsinsignalprocessing.Fixed-
pointalgorithmsforinverseproblemsinscienceandengineering
.SpringerNewYork,
185

212,2011.
[17]
P.Comon.
Independentcomponentanalysis,Anewconcept
.SignalProcessing36,1994,
pp.287-314.
[18]
P.Comon,andC.Jutten.
HandbookofBlindSourceSeparation:Independentcomponent
analysisandapplications
.Academicpress,2010.
[19]
T.Cover,andJ.Thomas.
Elementsofinformationtheory
.NewYork:Wiley(1991).
[20]
N.Delfosse,andP.Loubaton.Adaptiveblindseparationofindependentsources:a
approach.SignalProcessing,45(1995),5983.
[21]
G.Giannakis,Y.InouyeandJ.M.Mendel.
Cumulantbasedationofmultichannel
movingaveragemodels
.IEEEAutomat.Control,Vol.34,July1989,pp.783-787.
[22]
T.Goldstein,andS.Osher.
ThesplitBregmanmethodfor
L
1
regularizedproblems
.
SIAMJournalImagingSci.,Vol.2,April2009,pp.323-343.
[23]
J.Herault,andC.Jutten.
Spaceortimeadaptivesignalprocessingbyneuralnetwork
models
.AIPConf.Proc.151,206(1986).
[24]
J.Hughes,D.Mao,D.Rockmore,Y.Wang,Q.Wu.
Empiricalmodedecomposition
analysisforvisualstylometry
.IEEETransPatternAnalMachIntell,Nov.2012,34(11),
pp.2147-57.
90
[25]
A.arinen,J.Karhunen,andE.Oja.
IndependentComponentAnalysis
.JohnWiley,
NewYork,2001.
[26]
A.arine,andE.Oja.
IndependentComponentAnalysis:AlgorithmsandApplica-
tions
.NeuralNetworks,13(4

5),2000,pp.411-430.
[27]
Y.Inouye,andT.Matsui.
Cumulantbasedparameterestimationoflinearsystems
.Proc.
WorkshopHigher-OrderSpectralAnalysis,Vail,Colorado,June1989,pp.180-185.
[28]
S.Johnson,andM.Frigo.
Amodsplit-radixFFTwithfewerarithmeticoperations
.
SignalProcessing,IEEETransactionson55
:
1(2007):111-119.
[29]
C.Jutten,andJ.Herault.
Blindseparationofsources,partI:Anadaptivealgorithm
basedonneuromimeticarchitecture
.SignalProcessing24,1991,pp.1-10.
[30]
A.Jourjine,S.Rickardand

O.Yilmaz.
Blindseparationofdisjointorthogonalsignals:
demixingNsourcesfrom2mixtures
.ProceedingsoftheIEEEInternationalConference
onAcoustics,Speech,andSignalProcessing,Jun2000,pp.2985-2988.
[31]
D.D.Lee,andH.S.Seung.
Learningofthepartsofobjectsbynon-negativematrix
factorization
.Nature,401:788

791,1999.
[32]
J.Liu,J.Xin,Y.Qi,andF.Zeng.
Atimedomainalgorithmforblindseparation
ofconvolutivesoundmixturesand
L
1
constrainedminimizationofcrosscorrelations
.
Commun.Math.Sci.,Vol.7,No.1,2009,pp.109-128.
[33]
J.Liu,J.Xin,andY.Qi.
Adynamicalgorithmforblindseparationofconvolutivesound
mixtures
.Neurocomputing72
:
1(2008):521-532.
[34]
J-J.Moreau.
Fonctionsconvexesdualesetpointsproximauxdansunespacehilbertien
.
CRAcad.Sci.ParisSer.AMath255:2897-2899,1962.
[35]
J-J.Moreau.
Proprietesdesapplications"prox"
.CRAcad.Sci.Paris256(1963),pp.
1069-1071.
[36]
J-J.Moreau.
Proximiteetdualitedansunespacehilbertien
.BulletindelaSociete
mathematiquedeFrance93(1965),pp.273-299.
[37]
C.Micchelli,L.Shen,andY.Xu.
Proximityalgorithmsforimagemodels:denoising
.
InverseProblems,IOPScience,2011,Vol.27.
91
[38]
C.Micchelli,L.Shen,Y.Xu,andX.Zeng.
ProximityalgorithmsfortheL1/TVimage
denoisingmodel
.Adv.Comput.Math.,2013,38(2),pp.401-426.
[39]
J.Liu,J.Xin,Y.Qi,andF.Zheng.
Atimedomainalgorithmforblindseparation
ofconvolutivesoundmixturesandL1constrainedminimizationofcrosscorrelations
.
Commun.Math.Sci.,2009,Vol.7,No.1,pp.1-247.
[40]
W.Ma,M.Yu,J.Xin,andS.Osher.
Reducingmusicalnoiseinblindsourceseparation
bytime-domainsparseandsplitBregmanmethod
.Interspeech2010,pp.402-405,
Sept26-30,2010,Chiba,Japan.
[41]
W.Ma,M.Yu,J.Xin,andS.Osher.
Aconvexmodeland
L
1
minimizationformusical
noisereductioninblindsourceseparation
.Commun.Math.Sci.,2012Vol.10,No.1,
pp.223-238.
[42]
D.Mao,Y.Wang,andQ.Wu.
Anewapproachforanalyzingphysiologicaltimeseries
.
Jul.2010.
[43]
J.Nadal,andN.Parga.
Non-linearneuronsinthelownoiselimit:afactorialcode
maximizesinformationtransfer
.Network,5(1994),565581.
[44]
A.Nuttall.
Somewindowswithverygoodsidelobebehavior
.IEEETransactiononAcous-
tics,Speech,andSignalProcessing,Vol.Assp29,NO.1,Feb,1981.
[45]
Z.Opial.
Weakconvergenceofthesequenceofsuccessiveapproximationsfornonexpan-
sivemappings
.Bull.Amer.Math.Soc.,1967,Vol.73,Num.4,pp.591-597.
[46]
V.Oppenheim.
SpeechspectrogramsusingthefastFouriertransform
.IEEESpectrum,
vol.7,Aug.1970,pp.57-62.
[47]
S.Osher,M.Burger,D.Goldfarb,J.Xu,andW.Yin.
Aniterativeregularizationmethod
fortotalvariation-basedimagerestoration
.MultiscaleModel.Simul.,Vol.4,N.O.2,
2005.
[48]
S.Osher,Y.Mao,B.Dong,W.Yin.
FastlinearizedBregmaniterationforcompressive
sensingandsparsedenoising
.arXivpreprintarXiv:1104.0262(2011).
[49]
S.Osher,andL.I.Rudin.
Featureorientedimageenhancementusingshock
.SIAM
J.Num.Anal.27(1990)919.
92
[50]
A.Papoulis,
Probability,randomvariables,andstochasticprocesses(3rded.)
.NewYork:
McGraw-Hill1991.
[51]
M.Pinsky.
IntroductiontoFourierAnalysisandWavelets
.AmericanMathematical
Society,2002.
[52]
L.Rudin.
Images,numericalanalysisofsingularitiesandshock
.Caltech,C.S.
Dept.Report1987
]
TR.5250:87.
[53]
L.Rudin,andS.Osher.
Totalvariationbasedimagerestorationwithfreelocalcon-
straints
.ImageProcessing,1994.Proceedings.ICIP-94.,IEEEInternationalConference.
Vol.1.IEEE,1994,pp.31-35.
[54]
L.Rudin,S.OsherandE.Fatemi.
Nonlineartotalvariationbasednoiseremovalalgo-
rithms
.
PhysicaD
,60(1992)pp.259-268.
[55]
S.Rickard,and

O.Yilmaz.
Onthew-disjointorthogonalityofspeech
.Proceedingsofthe
IEEEinternationalconferenceonacoustics,speech,andsignalprocessing,May2002,
pp.529-532.
[56]
D.Strong,andT.Chan.
Edge-preservingandscale-dependentpropertiesoftotalvaria-
tionregularization
.InverseProblems,19(2003),pp.
S
165-
S
187.
[57]
F.BachandM.Jordan.
Beyondindependentcomponents:treesandclusters
.Journal
ofMachineLearningResearch,4:1205-1233,2003.
[58]
L.Vese,andS.Osher.
Modelingtestureswithtotalvariationminimizationandoscilla-
torypatternsinimageprocessing
.Journalofsciencomputing,19
:
1-3(2003),pp.
553-572.
[59]
M.VanSegbroeck,andH.Vanhamme.
Robustspeechrecognitionusingcepstraldomain
missingdatatechniquesandnoisymasks
.IEEEInternationalConferenceonAcoustics,
Speech,andSignalProcessing,Vol.1,2004.
[60]
Y.Wang,

O.Yilmaz,andZ.Zhou.
Phasealiasingcorrectionforrobustblindsource
separationusingDUET
.AppliedandComput.Harm.Anal.,Vol.35,Issue2,Sept.
2013,pp.341-349
[61]
Y.Wang,andZ.Zhou.
Sourceextractioninaudioviabackgroundlearning
.Inverse
problemsandimaging7
:
1(2013):283.
93
[62]
B.Yang.
Astudyofinverseshorttimefouriertransform
.IEEEInternationalConference
onAcoustics,SpeechandSignalProcessing,2008.
[63]
M.Yu,W.Ma,J.Xin,andS.Osher.
Convexityandfastspeechextractionbysplit
Bregmanmethod
.Interspeech2010,pp.398-401,Sept26-30,2010,Chiba,Japan.
[64]
M.Yu,W.Ma,J.Xin,andS.Osher.
Multi-channel
l
1
regularizedconvexspeechen-
hancementmodelandfastcomputationbythesplitBregmanmethod
.Audio,Speech
andLanguageProcessing,IEEETransactionson20(2),(2012):661-675.
[65]
Z.Zeng.
Thenumericalgreatestcommondivisorofunivariatepolynomials
.Random-
ization,relaxation,andcomplexityinpolynomialequationsolving,Providence,RI.
Contemp.Math.Amer.Math.Soc556(2011):187-217.
94