Odległość Earth Mover's (EMD) między dwoma Gaussianami

26

Czy istnieje formuła zamknięta dla (lub pewnego rodzaju powiązania) EMD między i ?x 2N ( μ 2 , Σ 2 )x1N(μ1,Σ1)x2N(μ2,Σ2)

ifog
źródło
2
Według en.wikipedia.org/wiki/Earth_mover%27s_distance EMD jest taki sam jak odległość Mallows lub Wasserstein, więc możesz spróbować googlin.
kjetil b halvorsen
2
Ten artykuł może ci się przydać: vldb.org/pvldb/vol5/p205_brianeruttenberg_vldb2012.pdf
jojer

Odpowiedzi:

27

Odległość można zapisać jako , gdzie infimum jest przejmowane przez wszystkie wspólne rozkłady X i Y z marginesowymi X \ sIM P , Y \ sIM Q . Jest to również znane jako pierwsza odległość Wassersteina , która wynosi W_p = \ inf \ left (\ E \ lVert X - Y \ rVert ^ p \ right) ^ {1 / p} z tym samym minimum.EMD(P,Q)=infEXYXYXPYQWp=inf(EXYp)1/p

Niech XP=N(μx,Σx) , YQ=N(μy,Σy) .

Dolna granica: według nierówności Jensena, ponieważ normy są wypukłe,

EXYE(XY)=μxμy,
więc EMD jest zawsze przynajmniej odległość między środkami (dla dowolnych rozkładów).

Górna granica oparta na W2 : Znów nierówność Jensena, (EXY)2EXY2 . Zatem W1W2 . Ale Dowson i Landau (1982) ustalili, że

W2(P,Q)2=μxμy2+tr(Σx+Σy2(ΣxΣy)1/2),
podając górną granicę dla EMD=W1 .

Węższa górna granica: rozważ sprzężenie To jest mapa opracowana przez Knott i Smitha (1984) , O optymalnym odwzorowaniu rozkładów , Journal of Optimization Theory and Applications, 43 (1) str. 39–49 jako optymalne odwzorowanie dla ; zobacz także ten post na blogu . Zauważ, że i

XN(μx,Σx)Y=μy+Σx12(Σx12ΣyΣx12)12Σx12A(Xμx).
W2A=ATEYW2A=AT
EY=μy+A(EXμx)=μyVarY=AΣxAT=Σx12(Σx12ΣyΣx12)12Σx12ΣxΣx12(Σx12ΣyΣx12)12Σx12=Σx12(Σx12ΣyΣx12)Σx12=Σy,
więc połączenie jest prawidłowe.

Odległość wynosi wtedy , gdzie teraz co jest normalne z XYD

D=XY=XμyA(Xμx)=(IA)Xμy+Aμx,
ED=μxμyVarD=(IA)Σx(IA)T=Σx+AΣxAAΣxΣxA=Σx+ΣyΣx12(Σx12ΣyΣx12)12Σx12Σx12(Σx12ΣyΣx12)12Σx12.

Zatem górna granica dla to . Niestety, forma zamknięta dla tego oczekiwania jest zaskakująco nieprzyjemna w przypadku ogólnych norm wielowymiarowych: patrz to pytanie , jak również to .W1(P,Q)ED

Jeśli wariancja jest sferyczna (np. Jeśli , , wówczas wariancja staje się ), poprzednia pytanie daje odpowiedź w postaci uogólnionego wielomianu Laguerre'a.DΣx=σx2IΣy=σy2ID(σxσy)2I

Ogólnie rzecz biorąc, mamy prostą górną granicę dla opartą na nierówności Jensena, wyprowadzoną np. Z tego pierwszego pytania: ED

(ED)2ED2=μxμy2+tr(Σx+ΣyAΣxΣxA)=μxμy2+tr(Σx)+tr(Σy)2tr(Σx12(Σx12ΣyΣx12)12Σx12)=μxμy2+tr(Σx)+tr(Σy)2tr((Σx12ΣyΣx12)12)=W2(P,Q)2.
Równość na końcu wynika z tego, że macierze i są podobne , więc mają te same wartości własne, a zatem ich pierwiastki kwadratowe mają ten sam ślad.ΣxΣyΣx12ΣyΣx12=Σx12(ΣxΣy)Σx12

Ta nierówność jest surowa, o ile nie ulega degeneracji, co w większości przypadków występuje w przypadku .DΣxΣy

Przypuszczenie : Może ta bliższa górna granica, , jest ciasna. Z drugiej strony, przez długi czas miałem tutaj inną górną granicę, którą przypuszczałem, że jest ciasna, która w rzeczywistości była luźniejsza niż , więc może nie powinieneś zbytnio ufać tej . :)EDW2

Dougal
źródło