{"id":19,"date":"2010-04-30T14:06:37","date_gmt":"2010-04-30T12:06:37","guid":{"rendered":"http:\/\/djalil.chafai.net\/blog\/?p=19"},"modified":"2024-07-22T10:33:23","modified_gmt":"2024-07-22T08:33:23","slug":"wasserstein-distance-between-two-gaussians","status":"publish","type":"post","link":"https:\/\/djalil.chafai.net\/blog\/2010\/04\/30\/wasserstein-distance-between-two-gaussians\/","title":{"rendered":"Wasserstein distance between two Gaussians"},"content":{"rendered":"
\"Leonid
Leonid Vitaliyevich Kantorovich (1912 \u2013 1986)<\/figcaption><\/figure>\n

The \\( {W_2} \\) Wasserstein coupling distance between two probability measures \\( {\\mu} \\) and \\( {\\nu} \\) on \\( {\\mathbb{R}^n} \\) is<\/p>\n

\\[ W_2(\\mu;\\nu):=\\inf\\mathbb{E}(\\Vert X-Y\\Vert_2^2)^{1\/2} \\]<\/p>\n

where the infimum runs over all random vectors \\( {(X,Y)} \\) of \\( {\\mathbb{R}^n\\times\\mathbb{R}^n} \\) with \\( {X\\sim\\mu} \\) and \\( {Y\\sim\\nu} \\). It turns out that we have the following nice formula for \\( {d:=W_2(\\mathcal{N}(m_1,\\Sigma_1);\\mathcal{N}(m_2,\\Sigma_2))} \\): <\/a><\/p>\n

\\[ d^2=\\Vert m_1-m_2\\Vert_2^2 +\\mathrm{Tr}(\\Sigma_1+\\Sigma_2-2(\\Sigma_1^{1\/2}\\Sigma_2\\Sigma_1^{1\/2})^{1\/2}). \\ \\ \\ \\ \\ (1) \\]<\/p>\n

This formula interested several authors including Givens and Shortt<\/a>, Knott and Smith<\/a>, Olkin and Pukelsheim<\/a>, and Dowson and Landau<\/a>. Note in particular that we have<\/p>\n

\\[ \\mathrm{Tr}((\\Sigma_1^{1\/2}\\Sigma_2\\Sigma_1^{1\/2})^{1\/2})= \\mathrm{Tr}((\\Sigma_2^{1\/2}\\Sigma_1\\Sigma_2^{1\/2})^{1\/2}). \\]<\/p>\n

In the commutative case where \\( {\\Sigma_1\\Sigma_2=\\Sigma_2\\Sigma_1} \\), the formula (1)<\/a> boils down simply to<\/p>\n

\\[ W_2(\\mathcal{N}(m_1,\\Sigma_1);\\mathcal{N}(m_2,\\Sigma_2))^2 =\\Vert m_1-m_2\\Vert_2^2 +\\Vert\\Sigma_1^{1\/2}-\\Sigma_2^{1\/2}\\Vert_{Frobenius}^2. \\]<\/p>\n

To prove (1)<\/a>, one can first reduce to the centered case \\( {m_1=m_2=0} \\). Next, if \\( {(X,Y)} \\) is a random vector (Gaussian or not) of \\( {\\mathbb{R}^n\\times\\mathbb{R}^n} \\) with covariance matrix<\/p>\n

\\[ \\Gamma= \\begin{pmatrix} \\Sigma_1 & C\\\\ C^\\top&\\Sigma_2 \\end{pmatrix} \\]<\/p>\n

then the quantity<\/p>\n

\\[ \\mathbb{E}(\\Vert X-Y\\Vert_2^2)=\\mathrm{Tr}(\\Sigma_1+\\Sigma_2-2C) \\]<\/p>\n

depends only on \\( {\\Gamma} \\). Also, when \\( {\\mu=\\mathcal{N}(0,\\Sigma_1)} \\) and \\( {\\nu=\\mathcal{N}(0,\\Sigma_2)} \\), one can restrict the infimum which defines \\( {W_2} \\) to run over Gaussian laws \\( {\\mathcal{N}(0,\\Gamma)} \\) on \\( {\\mathbb{R}^n\\times\\mathbb{R}^n} \\) with covariance matrix \\( {\\Gamma} \\) structured as above. The sole constrain on \\( {C} \\) is the Schur complement constraint:<\/p>\n

\\[ \\Sigma_1-C\\Sigma_2^{-1}C^\\top\\succeq0. \\]<\/p>\n

The minimization of the function<\/p>\n

\\[ C\\mapsto-2\\mathrm{Tr}(C) \\]<\/p>\n

under the constraint above leads to (1)<\/a>. A detailed proof is given by Givens and Shortt<\/a>. Alternatively, one may find an optimal transportation map as Knott and Smith<\/a>. It turns out that \\( {\\mathcal{N}(m_2,\\Sigma_2)} \\) is the image law of \\( {\\mathcal{N}(m_1,\\Sigma_1)} \\) with the linear map<\/p>\n

\\[ x\\mapsto m_2+A(x-m_1) \\]<\/p>\n

where<\/p>\n

\\[ A=\\Sigma_1^{-1\/2}(\\Sigma_1^{1\/2}\\Sigma_2\\Sigma_1^{1\/2})^{1\/2}\\Sigma_1^{-1\/2}=A^\\top. \\]<\/p>\n

To check that this maps \\( {\\mathcal{N}(m_1,\\Sigma_1)} \\) to \\( {\\mathcal{N}(m_2,\\Sigma_2)} \\), say in the case \\( {m_1=m_2=0} \\) for simplicity, one may define the random column vectors \\( {X\\sim\\mathcal{N}(m_1,\\Sigma_1)} \\) and \\( {Y=AX} \\) and write<\/p>\n

\\[ \\begin{array}{rcl} \\mathbb{E}(YY^\\top) &=& A \\mathbb{E}(XX^\\top) A^\\top\\\\ &=& \\Sigma_1^{-1\/2}(\\Sigma_1^{1\/2}\\Sigma_2\\Sigma_1^{1\/2})^{1\/2} (\\Sigma_1^{1\/2}\\Sigma_2\\Sigma_1^{1\/2})^{1\/2}\\Sigma_1^{-1\/2}\\\\ &=& \\Sigma_2. \\end{array} \\]<\/p>\n

To check that the map is optimal, one may use,<\/p>\n

\\[ \\begin{array}{rcl} \\mathbb{E}(\\|X-Y\\|_2^2) &=&\\mathbb{E}(\\|X\\|_2^2)+\\mathbb{E}(\\|Y\\|_2^2)-2\\mathbb{E}(\\left<X,Y\\right>) \\\\ &=&\\mathrm{Tr}(\\Sigma_1)+\\mathrm{Tr}(\\Sigma_2)-2\\mathbb{E}(\\left<X,AX\\right>)\\\\ &=&\\mathrm{Tr}(\\Sigma_1)+\\mathrm{Tr}(\\Sigma_2)-2\\mathrm{Tr}(\\Sigma_1A) \\end{array} \\]<\/p>\n

and observe that by the cyclic property of the trace,<\/p>\n

\\[ \\mathrm{Tr}(\\Sigma_1 A) =\\mathrm{Tr}((\\Sigma_1^{1\/2}\\Sigma_2\\Sigma_1^{1\/2})^{1\/2}). \\]<\/p>\n

The generalizations to elliptic families of distributions and to infinite dimensional Hilbert spaces is probably easy. Some more ``geometric'' properties of Gaussians with respect to such distances where studied more recently by Takastu<\/a> and Takastu and Yokota<\/a>.<\/p>\n

The optimal transport map looks strange. Actually, the uniqueness in the Brenier theorem states that if a map \\( {T} \\) maps \\( {\\mu} \\) to \\( {\\nu} \\) and is the gradient of a convex function, then it is the optimal transport map that maps \\( {\\mu} \\) to \\( {\\nu} \\) and<\/p>\n

\\[ W_2^2(\\mu,\\nu)=\\int|T(x)-x|^2\\mathrm{d}\\mu. \\]<\/p>\n

On the other hand, the affine map \\( {x\\in\\mathbb{R}^d\\rightarrow m+Ax\\in\\mathbb{R}^d} \\) is the gradient of a convex function if and only if the \\( {d\\times d} \\) matrix \\( {A} \\) is semidefinite symmetric. As a direct application, since<\/p>\n

\\[ x\\mapsto m_2+\\Sigma_1^{-1\/2}(\\Sigma_1^{1\/2}\\Sigma_2\\Sigma_1^{1\/2})^{1\/2}\\Sigma_1^{-1\/2}(x-m_1) \\]<\/p>\n

is the gradient of a convex function and maps \\( {\\mathcal{N}(m_1,\\Sigma_1)} \\) to \\( {\\mathcal{N}(m_2,\\Sigma_2)} \\), it is the optimal transport map, and we get the formula for \\( {W_2} \\) ! This is an alternative to Givens and Shortt.<\/p>\n","protected":false},"excerpt":{"rendered":"

The \\( {W_2} \\) Wasserstein coupling distance between two probability measures \\( {\\mu} \\) and \\( {\\nu} \\) on \\( {\\mathbb{R}^n} \\) is \\[ W_2(\\mu;\\nu):=\\inf\\mathbb{E}(\\Vert…<\/p>\n

Continue readingWasserstein distance between two Gaussians<\/span><\/a><\/div>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"iawp_total_views":19329},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/19"}],"collection":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/comments?post=19"}],"version-history":[{"count":25,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/19\/revisions"}],"predecessor-version":[{"id":20477,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/19\/revisions\/20477"}],"wp:attachment":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/media?parent=19"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/categories?post=19"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/tags?post=19"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}