Signal Processing - July 2017 - 51

and the corresponding representation of the transformed data
in the LDA discriminant subspace [Figure 4(d)]. It is clear that
the image classes become more linearly separable in the transform space. In addition, the cumulative percentage variation
(CPV) of the data set in the image space, the Radon transform
space, the Ridgelet transform space, and the Radon-CDT space
are shown in Figure 5. The figure shows that the variations in
the data set could be explained with fewer components in the
Radon-CDT space.

Numerical methods
The development of robust and efficient numerical methods
for computing transport-related maps, plans, metrics, and geodesics is crucial for the development of algorithms that can be
used in practical applications. We next present several notable
approaches for finding transportation maps and plans. Table 2
provides a high-level overview of these methods.

simplifies to a one-to-one assignment problem that can be solved
in O (N 2 log N ) . In addition, several multiscale approaches and
sparse approximation approaches have recently been introduced to improve the computational performance of the linear
programming solvers [37], [46].

Entropy-regularized solution
Cuturi's work [14] provides a fast and easy-to-implement variation of the Kantorovich problem by considering the transportation problem from a maximum-entropy perspective. The
idea is to regularize the Wasserstein metric by the entropy of
the transport plan. This modification simplifies the problem
and enables much faster numerical schemes with complexity

CPV

100
80

The linear programming problem is an optimization problem
with a linear objective function and linear equality and
inequality constraints. Several numerical methods exist for
solving linear programming problems, among which are
the simplex method and its variations and the interior-point
methods. The computational complexity of the mentioned
numerical methods, however, scales at best cubically in the
size of the domain. Hence, assuming the measures considered
have N particles, the number of unknowns c ij s is N2 and the
computational complexities of the solvers are at best
O (N 3 log N ) [14], [44]. The computational complexity of the
linear programming methods is a very important limiting factor for the applications of the Kantorovich problem.
We note that, in the special case where I0 and I1 both have
N equidistributed particles, the optimal transport problem

CPV

A linear programming problem

Image Space
+ Radon Space
Ridgelet Space
Radon-CDT Space

20
0

20
40
60
Number of Eigenvalues (k)

CPV =

∑i =1λi
N

∑n =1λn

λi = i th Eigenvalue

FIGURE 5. The cumulative percentage of the face data set in Figure 4 in the
image space, the Radon transform space, the Ridgelet transform space,
and the Radon-CDT transform space.

Table 2. The key properties of various numerical approaches.
Comparison of Numerical Approaches
Method

Remark

Linear programming

Applicable to general costs. Good approach if the PDFs are supported at very few sites.

Multiscale linear programming

Applicable to general costs. Fast and robust method, though truncation involved can lead to
imprecise distances.

Auction algorithm

Applicable only when the number of particles in the source and the target is equal and all of their
masses are the same.

Entropy-regularized linear
programming

Applicable to general costs. Simple and performs very well in practice for moderately large problems.
Difficult to obtain high accuracy.

Fluid mechanics

This approach can be adapted to generalizations of the quadratic cost, based on action along paths.

AHT minimization

Quadratic cost. Requires some smoothness and positivity of densities. Convergence is guaranteed
only for infinitesimal step size.

Gradient descent on the dual problem

Quadratic cost. Convergence depends on the smoothness of the densities, hence a multiscale
approach is needed for nonsmooth densities (i.e., normalized images).

Monge-Ampère solver

Quadratic cost. One in [7] is proved to be convergent. Accuracy is an issue due to the wide stencil used.

Semidiscrete approximation

An efficient way to find the map between a continuous and discrete signal [31].

AHT: Angenent, Haker, and Tannenbaum.

IEEE SIGNAL PROCESSING MAGAZINE

July 2017

Table of Contents for the Digital Edition of Signal Processing - July 2017