La distance du déménageur peut être écrite commeEMD(P,Q)=infE∥X−Y∥ , où l'infimum est pris sur toutes les distributions conjointes deX etY avec marginauxX∼P ,Y∼Q . Ceci est également connu comme la première distance de Wasserstein , qui estWp=inf(E∥X−Y∥p)1/p avec le même infimum.
Soit X∼P=N(μx,Σx) , Y∼Q=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).
E∥X−Y∥≥∥E(X−Y)∥=∥μ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 .(E∥X−Y∥)2≤E∥X−Y∥2W1≤W2
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)E∥D∥
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=σ2xIΣy=σ2yID(σ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:
E∥D∥
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Σ12xΣyΣ12x=Σ−12x(ΣxΣy)Σ12x
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. :)E∥D∥W2
Réponses:
SoitX∼P=N(μx,Σx) , Y∼Q=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).E∥X−Y∥≥∥E(X−Y)∥=∥μ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 .(E∥X−Y∥)2≤E∥X−Y∥2 W1≤W2 W2(P,Q)2=∥μx−μy∥2+tr(Σx+Σy−2(Σ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 etXY∼N(μx,Σx)=μy+Σ−12x(Σ12xΣyΣ12x)12Σ−12xA(X−μx). W2 A=AT EYVarY=μy+A(EX−μx)=μy=AΣxAT=Σ−12x(Σ12xΣyΣ12x)12Σ−12xΣxΣ−12x(Σ12xΣyΣ12x)12Σ−12x=Σ−12x(Σ12xΣyΣ12x)Σ−12x=Σy,
pour que le couplage soit valide.
La distance est alors , où maintenant qui est normal avec∥X−Y∥ ∥D∥ D=X−Y=X−μy−A(X−μx)=(I−A)X−μy+Aμx, EDVarD=μx−μy=(I−A)Σx(I−A)T=Σx+AΣxA−AΣx−ΣxA=Σx+Σy−Σ−12x(Σ12xΣyΣ12x)12Σ12x−Σ12x(Σ12xΣyΣ12x)12Σ−12x.
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) E∥D∥
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=σ2xI Σy=σ2yI D (σ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:E∥D∥ (E∥D∥)2≤E∥D∥2=∥μx−μy∥2+tr(Σx+Σy−AΣx−ΣxA)=∥μx−μy∥2+tr(Σx)+tr(Σy)−2tr(Σ−12x(Σ12xΣyΣ12x)12Σ12x)=∥μx−μy∥2+tr(Σx)+tr(Σy)−2tr((Σ12xΣyΣ12x)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 Σ12xΣyΣ12x=Σ−12x(ΣxΣy)Σ12x
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. :)E∥D∥ W2
la source