where \(G^{-1}\)  may be computed by interpolation and an efficient search
algorithm, such as binary search. The overall cost of computing the discrete
\(W_2\)  metric in one dimension will then be \({\mathcal {O}}(n \, \log n)\) .
In multiple dimensions, i.e. when \({\mathcal {X}}, {\mathcal {Y}} \subset {\mathbb {R}}^d\)  with \(d \ge 2\) , however, the computation of the optimal
map \(M\) , and hence the \(W_2\)  metric, may be
either expensive or infeasible. The map is indeed given by the gradient of a convex
function that is the solution to a constrained nonlinear
Monge-Ampère equation. We refer to [1]} for more discussion on
the finite difference approximation of the Monge-Ampère equation
in two dimensions.
