Distância do Movimentador de Terra (EMD) entre dois Gaussianos

26

Existe uma fórmula de formulário fechado para (ou algum tipo de ligação) no EMD entre e ?x 2N ( μ 2 , Σ 2 )x1N(μ1,Σ1)x2N(μ2,Σ2)

ifog
fonte
2
De acordo com en.wikipedia.org/wiki/Earth_mover%27s_distance, o EMD é o mesmo que a distância de Mallows ou Wasserstein, para que você possa tentar fazer isso no Google.
Kjetil b halvorsen
2
Você pode achar este documento útil: vldb.org/pvldb/vol5/p205_brianeruttenberg_vldb2012.pdf
jojer

Respostas:

27

A distância do movedor de terra pode ser escrita comoEMD(P,Q)=infE__X-Y__ , onde o menor é tomado sobre todas as distribuições conjuntas deX eY com marginaisXP ,YQ . Isso também é conhecido como a primeira distância de Wasserstein , que éWp=inf(E__X-Y__p)1 1/p com o mesmo máximo.

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

EXYE(XY)=μxμy,
inferior: pela desigualdade de Jensen, uma vez que as normas são convexas, \ E \ lVert X - Y \ rVert \ ge \ lVert \ E (X - Y) \ rVert = \ lVert \ mu_x - \ mu_y \ rVert, portanto , o EMD é sempre pelo menos a distância entre os meios (para quaisquer distribuições).

W2 superior baseado em W_2 : Novamente pela desigualdade de Jensen, (EXY)2EXY2 . Assim W1W2 . Mas Dowson e Landau (1982) estabelecem que

W2(P,Q)2=μxμy2+tr(Σx+Σy2(ΣxΣy)1/2),
fornecendo um limite superior em EMD=W1 .

Um limite superior mais apertado: considere o acoplamento Este é o mapa derivado por Knott e Smith (1984) , Sobre o mapeamento ideal de distribuições , Journal of Optimization Theory and Applications, 43 (1) pp 39-49 como o mapeamento ideal para ; veja também esta postagem no blog . Observe que e

XN(μx,Σx)Y=μy+Σx12(Σx12ΣyΣx12)12Σx12A(Xμx).
W2A=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,
para que o acoplamento seja válido.

A distância é então , onde agora que é normal com 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.

Portanto, um limite superior para é . Infelizmente, um formulário fechado para essa expectativa é surpreendentemente desagradável para anotações para normais gerais multivariados: veja esta questão , bem como esta .W1(P,Q)ED

Se a variância de acaba sendo esférica (por exemplo, se , , a variação de se torna ), a primeira pergunta dá a resposta em termos de um polinômio generalizado de Laguerre.DΣx=σx2IΣy=σy2ID(σxσy)2I

Em geral, temos um limite superior simples para base na desigualdade de Jensen, derivada, por exemplo, da primeira pergunta: 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.
A igualdade no final ocorre porque as matrizes e são semelhantes , então eles têm os mesmos valores próprios e, portanto, suas raízes quadradas têm o mesmo traço.ΣxΣyΣx12ΣyΣx12=Σx12(ΣxΣy)Σx12

Essa desigualdade é estrita desde que não seja degenerado, como na maioria dos casos, quando .DΣxΣy

Uma conjectura : Talvez esse limite superior mais próximo, , esteja apertado. Por outro lado, eu tive um limite superior diferente aqui por um longo tempo que ser rígido, que na verdade era mais flexível que o , então talvez você não deva confiar muito nessa conjectura. :)EDW2

Dougal
fonte