Distance de l'engin de terre (EMD) entre deux Gaussiens

26

Existe-t-il une formule sous forme fermée pour (ou une sorte de liaison sur) l'EMD entre x1N(μ1,Σ1) et x2N(μ2,Σ2) ?

ifog
la source
2
Selon en.wikipedia.org/wiki/Earth_mover%27s_distance, l'EMD est le même que la distance Mallows ou Wasserstein, vous pouvez donc essayer googlin.
kjetil b halvorsen
2
Vous pourriez trouver cet article utile: vldb.org/pvldb/vol5/p205_brianeruttenberg_vldb2012.pdf
jojer

Réponses:

27

La distance du déménageur peut être écrite commeEMD(P,Q)=infEXY , où l'infimum est pris sur toutes les distributions conjointes deX etY avec marginauxXP ,YQ . Ceci est également connu comme la première distance de Wasserstein , qui estWp=inf(EXYp)1/p avec le même infimum.

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

inférieure: par l'inégalité de Jensen, puisque les normes sont convexes, donc l'EMD est toujours au moins la distance entre les moyens (pour toutes les distributions).

EXYE(XY)=μxμy,

supérieure basée sur : àW2 nouveau par l'inégalité de Jensen, . Ainsi . Mais Dowson et Landau (1982) établissent que donnant une limite supérieure sur .(EXY)2EXY2W1W2

W2(P,Q)2=μxμy2+tr(Σx+Σy2(ΣxΣy)1/2),
EMD=W1

Une limite supérieure plus stricte: considérez le couplage Voici la carte dérivée de Knott et Smith (1984) , On the optimal mapping of distributions , Journal of Optimization Theory and Applications, 43 (1) pp 39-49 as the optimal mapping for ; voir aussi cet article de blog . Notez que et

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,
pour que le couplage soit valide.

La distance est alors , où maintenant qui est normal avec 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.

Ainsi, une limite supérieure pour est . Malheureusement, une forme fermée pour cette attente est étonnamment désagréable à écrire pour les normales multivariées générales: voir cette question , ainsi que celle-ci .W1(P,Q)ED

Si la variance de finit par être sphérique (par exemple, si , , alors la variance de devient ), l'ancien question donne la réponse en termes de polynôme de Laguerre généralisé.DΣx=σx2IΣy=σy2ID(σxσy)2I

En général, nous avons une borne supérieure simple pour basée sur l'inégalité de Jensen, dérivée par exemple dans cette première question: 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.
L'égalité à la fin est due au fait que les matrices et sont similaires , donc ils ont les mêmes valeurs propres, et donc leurs racines carrées ont la même trace.ΣxΣyΣx12ΣyΣx12=Σx12(ΣxΣy)Σx12

Cette inégalité est stricte tant que n'est pas dégénéré, ce qui est généralement le cas lorsque .DΣxΣy

Une conjecture : peut-être que cette limite supérieure plus proche, , est serrée. Là encore, j'avais une limite supérieure différente depuis longtemps que je supposais être serrée, qui était en fait plus lâche que celle de , alors peut-être que vous ne devriez pas trop faire confiance à cette conjecture. :)EDW2

Dougal
la source