Расстояние Движителя Земли (EMD) между двумя гауссианами

26

Существует ли формула замкнутой формы для (или какого-либо ограничения) EMD между и ?x 2N ( μ 2 , Σ 2 )x1N(μ1,Σ1)x2N(μ2,Σ2)

ifog
источник
2
Согласно en.wikipedia.org/wiki/Earth_mover%27s_distance, EMD соответствует расстоянию Мэллова или Вассерштейна, так что вы можете попробовать это с помощью googlin.
kjetil b halvorsen
2
Вы можете найти этот документ полезным: vldb.org/pvldb/vol5/p205_brianeruttenberg_vldb2012.pdf
jojer

Ответы:

27

Расстояние движителя земли можно записать как ЕMD(п,Q)знак равноинфЕ| |Икс-Y| | , где инфимум берется по всем совместным распределениям Икс и Y с маргинальными Икс~п , Y~Q . Это также известно как первое расстояние Вассерштейна , которое равно Wпзнак равноинф(Е| |Икс-Y| |п)1/п с тем же инфимумом.

Пусть Икс~пзнак равноN(μИкс,ΣИкс) , Y~Qзнак равноN(μY,ΣY) .

Нижняя граница: по неравенству Дженсена, так как нормы выпуклые,

Е| |Икс-Y| || |Е(Икс-Y)| |знак равно| |μИкс-μY| |,
поэтому EMD всегда по крайней мере, расстояние между средствами (для любых распределений).

Верхняя граница, основанная на W2 : опять же из-за неравенства Дженсена (Е| |Икс-Y| |)2Е| |Икс-Y| |2 . Таким образом, W1W2 . Но Доусон и Ландау (1982) устанавливают, что

W2(P,Q)2=μxμy2+tr(Σx+Σy2(ΣxΣy)1/2),
давая верхнюю границу EMD=W1 .

Более жесткая верхняя граница: рассмотрим соединение Это карта, полученная Ноттом и Смитом (1984) , Об оптимальном отображении распределений , Журнал теории оптимизации и приложений, 43 (1) С. 39-49 как оптимальное отображение для ; см. также этот блог . Обратите внимание, что и

XN(μx,Σx)Y=μy+Σx12(Σx12ΣyΣx12)12ΣИкс-12A(Икс-μИкс),
W2Aзнак равноAT
ЕYзнак равноμY+A(ЕИкс-μИкс)знак равноμYVarYзнак равноAΣИксATзнак равноΣИкс-12(ΣИкс12ΣYΣИкс12)12ΣИкс-12ΣИксΣИкс-12(ΣИкс12ΣYΣИкс12)12ΣИкс-12знак равноΣИкс-12(ΣИкс12ΣYΣИкс12)ΣИкс-12знак равноΣY,
поэтому связь действительна.

Расстояние тогда равно , где теперь что нормально с | |Икс-Y| || |D| |

Dзнак равноИкс-Yзнак равноИкс-μY-A(Икс-μИкс)знак равно(я-A)Икс-μY+AμИкс,
ЕDзнак равноμИкс-μYVarDзнак равно(я-A)ΣИкс(я-A)Tзнак равноΣИкс+AΣИксA-AΣИкс-ΣИксAзнак равноΣИкс+ΣY-ΣИкс-12(ΣИкс12ΣYΣИкс12)12ΣИкс12-ΣИкс12(ΣИкс12ΣYΣИкс12)12ΣИкс-12,

Таким образом, верхняя оценка для равна . К сожалению, закрытую форму для этого ожидания удивительно неприятно записать для общих многомерных нормалей: см. Этот вопрос , а также этот .W1(п,Q)Е| |D| |

Если дисперсия оказывается сферической (например, если , , то дисперсия становится ), прежняя Вопрос дает ответ в терминах обобщенного полинома Лагерра.DΣИксзнак равноσИкс2яΣYзнак равноσY2яD(σИкс-σY)2я

В общем, у нас есть простая верхняя оценка для основанная на неравенстве Дженсена, полученная, например, из первого вопроса: Е| |D| |

(Е| |D| |)2Е| |D| |2знак равно| |μИкс-μY| |2+Tр(ΣИкс+ΣY-AΣИкс-ΣИксA)знак равно| |μИкс-μY| |2+Tр(ΣИкс)+Tр(ΣY)-2Tр(ΣИкс-12(ΣИкс12ΣYΣИкс12)12ΣИкс12)знак равно| |μИкс-μY| |2+Tр(ΣИкс)+Tр(ΣY)-2Tр((ΣИкс12ΣYΣИкс12)12)знак равноW2(п,Q)2,
Равенство в конце объясняется тем, что матрицы и похожи Таким образом, они имеют одинаковые собственные значения, и, следовательно, их квадратные корни имеют одинаковый след.ΣИксΣYΣИкс12ΣYΣИкс12знак равноΣИкс-12(ΣИксΣY)ΣИкс12

Это неравенство является строгим до тех пор, пока не вырожден, что в большинстве случаев имеет место .| |D| |ΣИксΣY

Гипотеза : может быть, эта более близкая верхняя граница, , является жесткой. С другой стороны, у меня в течение долгого времени была другая верхняя граница, которую я предположил, чтобы быть жесткой, которая на самом деле была более слабой, чем , так что, возможно, вам не следует слишком сильно доверять этой гипотезе. :)EDW2

Дугал
источник