-
Notifications
You must be signed in to change notification settings - Fork 2
/
mdop2r2.tex
1746 lines (1536 loc) · 90.8 KB
/
mdop2r2.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
\documentclass[twoside,11pt]{article}
\usepackage{jmlr2e}
%\RequirePackage[colorlinks,citecolor=blue,urlcolor=blue]{hyperref}
\usepackage{xcolor}
\usepackage[cmex10]{amsmath}
%\usepackage{amssymb, amsfonts, amsthm}
%\usepackage{mathptmx}
\usepackage{graphicx}
\graphicspath{{./figures/},{./poster/}}
\DeclareGraphicsExtensions{.pdf,.jpeg,.png}
\usepackage{grffile}
\usepackage{hyperref}
\usepackage{paralist}
%\usepackage{fullpage}
\usepackage[ruled,vlined]{algorithm2e}
\usepackage{array}
%\newtheorem{theorem}{Theorem}[section]
%\newtheorem{lemma}[theorem]{Lemma}
%\newtheorem{proposition}[theorem]{Proposition}
%\newtheorem{corollary}[theorem]{Corollary}
%\newtheorem{definition}{Definition}[section]
\newcolumntype{V}{>{\centering\arraybackslash} m{.5\linewidth} }
\newcommand{\parent}[0]{\operatorname{parent}}
\newcommand{\children}[0]{\operatorname{children}}
\newcommand{\descendants}[0]{\operatorname{descendants}}
\newcommand{\cost}[0]{\mathtt{c}}
\newcommand{\couplingcost}[0]{\mathtt{cost}}
\newcommand{\coupling}[0]{\pi}
\newcommand{\couplings}[0]{\mathcal{C}}
\def\argmin{\mathop{\rm argmin}}
\newcommand{\dimX}{\mathtt{d}}
\newcommand{\Xsp}{{\mathbf{X}}}
\newcommand{\Ysp}{{\mathbf{Y}}}
\newcommand{\lambdaX}{\lambda^\Xsp}
\newcommand{\lambdaY}{\lambda^\Ysp}
\newcommand{\Cjk}{C_{j,k}}
\newcommand{\CjkX}{C^\Xsp_{j,k}}
\newcommand{\CjkY}{C^\Ysp_{j,k}}
\newcommand{\psijkX}{\psi^\Xsp_{j,k}}
\newcommand{\psijkY}{\psi^\Ysp_{j,k}}
\hyphenation{homeo-morphic diffeo-morphic mani-fold eff-ect-ive-ness me-tho-do-lo-gy}
%\addtolength{\oddsidemargin}{-.2in}
%\addtolength{\evensidemargin}{-.2in}
%\addtolength{\textwidth}{0.4in}
%\addtolength{\topmargin}{-.6in}
%\addtolength{\textheight}{1.2in}
\setlength{\textfloatsep}{10pt plus 1.0pt minus 2.0pt}
% Heading arguments are {volume}{year}{pages}{submitted}{published}{author-full-names}
\jmlrheading{18}{2017}{1-32}{3/16; Revised 6/17}{8/17}{16-108}{Samuel Gerber and Mauro Maggioni}
% Short headings should be running head and authors last names
\ShortHeadings{Multiscale Optimal Transport}{Gerber and Maggioni}
\firstpageno{1}
\title{Multiscale Strategies for Computing Optimal Transport}
\author{\name Samuel Gerber$^1$ \email samuel.gerber@kitware.com \\
\name Mauro Maggioni$^{2,3,4}$ \email mauro.maggioni@jhu.edu \\
\addr $^1$Kitware, NC, U.S.A\\
\addr Department of $^2$\!Mathematics, $^3$\!Applied Mathematics, $^4$\!Institute for Data Intensive Engineering and Science, Johns Hopkins University, Baltimore, MD, U.S.A.
}
\editor{Nikos Vlassis}
%\author{Samuel Gerber \and Mauro Maggioni}
\begin{document}
\maketitle
\begin{abstract}%
This paper presents a multiscale approach to efficiently compute approximate
optimal transport plans between point sets. It is particularly well-suited for
point sets that are in high-dimensions, but are close to being intrinsically
low-dimensional. The approach is based on an adaptive multiscale decomposition
of the point sets. The multiscale decomposition yields a sequence of optimal
transport problems, that are solved in a top-to-bottom fashion from the
coarsest to the finest scale. We provide numerical evidence that this
multiscale approach scales approximately linearly, in time and memory, in the
number of nodes, instead of quadratically or worse for a direct solution.
Empirically, the multiscale approach results in less than one percent relative
error in the objective function. Furthermore, the multiscale plans constructed
are of interest by themselves as they may be used to introduce novel features
and notions of distances between point sets. An analysis of sets of brain MRI
based on optimal transport distances illustrates the effectiveness of the
proposed method on a real world data set. The application demonstrates that
multiscale optimal transport distances have the potential to improve on
state-of-the-art metrics currently used in computational anatomy.
\end{abstract}
\section{Introduction}
\label{sec:introduction}
The study of maps between shapes, manifolds and point clouds is of great
interest in a wide variety of applications. There are many data types, e.g.
shapes (modeled as surfaces), images, sounds, and many more, where a similarity
between a pair of data points involves computing a map between the points, and
the similarity is a functional of that map. The map between a pair of data
points however contains much more information than the similarity measure
alone, and the study of networks of such maps have been successfully used to
organize, extract functional information and abstractions, and help regularize
estimators in large collections of shapes \citep{bigdata5,bigdata10,bigdata8}.
The family of maps to be considered depends on the type of shape, manifold or
point cloud, as well as on the choice of geometric features to be preserved in
a particular application. These considerations are not restricted to data sets
where each point is naturally a geometric object: high-dimensional data sets of
non-geometric nature, from musical pieces to text documents to trajectories of
high-dimensional stochastic dynamical systems, are often mapped, via feature
sets, to geometric objects. The considerations above therefore apply to a very
wide class of data types.
In this paper we are interested in the problem where each object is a point
cloud -- a set of points in $\mathbb{R}^D$ -- and will develop techniques for
computing maps from one point cloud to another, in particular in the situation
where $D$ is very large, but the point clouds are close to being
low-dimensional, for example they may be samples from a $d$-dimensional smooth
manifold $\mathcal{M}$ ($d\ll D$). The two point clouds may have a different
number of points, and they may arise from a sample of a low-dimensional
manifold $\mathcal{M}$ perturbed by high-dimensional noise (for more general
models see the works by~\citet{LMR:MGM1},~\citet{MMS:NoisyDictionaryLearning}
and~\citet{LiaoMaggioni}). In this setting we have to be particularly careful
in both the choice of maps and in their estimation since sampling and noise
have the potential to cause significant perturbations.
We find optimal transport maps rather well-suited for these purposes. They
automatically handle the situation where the two point clouds have different
cardinality, they handle in a robust fashion noise, and even changes in
dimensionality, which is typically ill-defined, for point clouds arising from
real-world data~\citep{LMR:MGM1}. Optimal transport has a very long history in
a variety of disciplines and arises naturally in a wide variety of contexts,
from optimization problems in economics and resource allocation, to mathematics
and physics, to computer science (e.g. network flow algorithms). Thus,
applications of optimal transport range from logistics and
economics~\citep{beckmann:eco1952,carlier:jcc2008}, geophysical
models~\citep{cullen:book2006}, image
analysis~\citep{rubner:iccv1998,haker:ijcv2004} to machine
learning~\citep{cuturi:arxiv2013,cuturi:jmlr2014}. Despite these widespread
applications, the efficient computation of optimal transport plans remains
challenging, especially in complex geometries and in high dimensions.
\begin{figure}[!b]
\centering
\begin{tabular}{cc}
\includegraphics[width=0.45\linewidth]{scale-3} &
\includegraphics[width=0.45\linewidth]{scale-5} \\
\includegraphics[width=0.45\linewidth]{scale-7} &
\includegraphics[width=0.45\linewidth]{scale-9}
\end{tabular}
\caption{\label{fig:multiscale-strategy}
Optimal transport between two noisy elliptical shapes in $2$-D. We
visualize coarse-to-fine approximations to the source (purple dots) and target
(yellow dots) point clouds, together with the optimal transportation plan at
each scale (gray edges). The intensity of the points is proportional to mass
-- at coarser scales each point represents an agglomerate of points at finer
scales, and its mass is the sum of the masses of the points it represents.
Similarly the intensity of the lines is proportional to the amount of mass
transported along the line. Notice that the optimal transport formulation
permits multiple lines exiting a source point or entering a target point.}
\end{figure}
For point sets the optimal transport problem can be solved by a specialized
linear program, the minimum network flow
problem~\citep{Ahuja:1993:NFT:137406,Tarjan1997}. The minimum network flow
problem has been extensively studied in the operations research community and
several fast algorithms exist. However, these algorithms, at least on desktop
hardware, do not scale beyond a few thousand source and target points. Our
framework extends the applications of these algorithms to problem instances
several orders of magnitude larger, under suitable assumptions on the geometry
of the data. We exploit a multiscale representation of the source and target
sets to reduce the number of variables in the linear program and quickly find
good initial solutions, as illustrated in Figure~\ref{fig:multiscale-strategy}.
The optimal transport problem is solved (with existing algorithms) at the
coarsest scale and the solution is propagated to the next scale and refined.
This process is repeated until the finest scale is reached. This strategy,
discussed in detail in Section~\ref{sec:mdop}, is adaptable to memory
limitations and speed versus accuracy trade-offs. For some of the refinement
strategies, it is guaranteed to converge to the optimal solution.
Our approach draws from a varied set of work that is briefly summarized in
Section~\ref{sec:background}. The proposed approach generalizes and builds on
previous and concurrently developed hierarchical
methods~\citep{glimm:arxiv2011,schmitzer2013hierarchical,schmitzer2015sparse,oberman2015efficient}.
The work in this paper adds the following contributions:
\begin{compactitem}
\item The description of a general multiscale framework for discrete optimal
transport that can be applied in conjunction with a wide range of optimal
transport algorithms.
\item A set of propagation and refinement heuristics, including approaches
that are similar and/or refine existing ones
\citep{glimm:arxiv2011,oberman2015efficient,schmitzer2015sparse} as well as
novel ones. In particular we propose a novel propagation strategy based on
capacity restrictions of the network flow problem at each scale. This new
approach proves to be very efficient and accurate in practice. Overall, the
heuristics result empirically in a linear increase in computation time with
respect to data set size.
\item An implementation in the R package {\em mop} that allows the combination
of multiple heuristics to tailor speed and accuracy to the requirements of
particular applications.
\end{compactitem}
Compared to other linear programming based approaches, the multiscale approach results
in a speedup of up to multiple orders of magnitude in large problems and
permits to solve approximately transportation problems of several orders of
magnitudes larger than previously possible. Comparing to PDE based approaches
is difficult and PDE based methods are limited to low-dimensional domains and
specific cost metrics. The proposed framework is demonstrated on several
numerical examples and compared to the state-of-the-art approximation algorithm
by~\citet{cuturi:nips2013}.
\section{Background}
\label{sec:background}
Optimal transport is the problem of minimizing the cost of moving a source
probability distribution to a target probability distribution given a function
that assigns costs to moving mass from source to target locations. The
classical formulation by~\citet{monge:book1781} considers the minimization over
mass preserving mappings. Later~\citet{kantorovitch:ms1958} considered the
same problem but as a minimization over couplings between the two probability
measures, which permits to split mass from a single source across multiple
target locations. More precisely, for two probability measures $\mu$ and
$\nu$ on probability spaces ${\Xsp}$ and ${\Ysp}$ respectively, a coupling of
$\mu$ and $\nu$ is a measure $\coupling$ on ${\Xsp}\times{\Ysp}$ such that the
marginals of $\coupling$ are $\mu$ and $\nu$, i.e.
$\coupling(A\times{\Ysp})=\mu(A)$ for all ($\mu$-measurable) sets
$A\subseteq{\Xsp}$ and $\coupling({\Xsp}\times B)=\nu(B)$ for all
($\nu$-measurable) sets $B\subseteq{\Ysp}$. We denote by $\mathcal{C}(\mu,\nu)$
the set of couplings between $\mu$ and $\nu$. Informally, we may think of
$d\coupling(x,y)$ as the amount of infinitesimal mass to be transported from
source $x$ to destination $y$, with the condition that $\coupling$ is a
coupling guaranteeing that the source mass is distributed according to $\mu$
and the destination mass is distributed according to $\nu$. Such couplings
always exist: we always have the trivial coupling $\coupling=\mu\times\nu$. The
trivial coupling is uninformative, every source mass $d\mu(x)$ is transported
to the same target distribution $\nu$. In Monge's formulation the coupling is
restricted to the special form $\coupling(x,y)=\delta_{T(x)}$ where $\delta_y$
is the Dirac-$\delta$ measure with mass at $y\in{\Ysp}$, and $T$ is a function
$\Xsp\rightarrow\Ysp$: in this case the coupling is ``maximally informative''
in the sense that there is a function mapping each source $x$ to a single
destination $y$; in particular the mass $d\mu(x)$ at $x$ is not split into
multiple portions that are shipped to different target $y$'s.
To define optimal transport and optimal couplings, we need a cost function
$\cost(x,y)$ on ${\Xsp}\times{\Ysp}$ representing the work or cost needed to
move a unit of mass from $x$ to $y$. Then for every coupling $\coupling$ we may
define the cost of $\coupling$ to be
\begin{equation}
\mathbb{E}_{(X,Y)\sim\coupling}[\cost(X,Y)]\,,
\end{equation}
with $(X,Y)$ being a pair of random variables distributed according to $\coupling$.
An optimal coupling $\coupling$ minimizes this cost over all choices of couplings.
When seeking an optimal transportation plan, the above becomes
$$
\mathbb{E}_{X\sim\mu}[\cost(X,T(X))]=\int_{{\Xsp}} \cost(x,T(x)) d\mu(x)\,,
$$
and one minimizes over all (measurable) functions $T:{\Xsp}\rightarrow{\Ysp}$.
One often designs the cost function $c$ in an application-dependent fashion,
and the above framework is extremely general. When ${\Xsp}={\Ysp}$ is a metric
space with respect to a distance $\rho$ (with suitable technical conditions
relating the metrics and the measures $\mu$, $\nu$ that we will not delve into,
referring the reader to \cite{villani:book2009}), then distinguished choices
for the cost are those that are related to the metric structure. The natural
choice of $\cost(x,y)=\rho(x,y)^p$, for some $p>0$ leads to the definition of
the Wasserstein-Kantorovich-Rubinstein metric on the space of probability
measures on ${\Xsp}$:
\begin{equation}
W_p(\mu,\nu):=\min_{\coupling\in\mathcal{C}(\mu,\nu)}\left(\int_{{\Xsp}}\int_{{\Xsp}}
\rho(x,y)^p d\coupling(x,y)\right)^{\frac1p}\,.
\end{equation}
Computational solutions to optimal transport split roughly in two settings:
Approaches based on the solution of partial differential equations derived from
the continuous optimal transport formulation, briefly discussed in
Section~\ref{sec:continuous} and, more relevant to this paper, combinatorial
optimization methods to directly solve for a discrete optimal transport plan
discussed in Section~\ref{sec:lp}.
\subsection{Continuous Optimal Transport}
\label{sec:continuous}
In case that at least the source distribution admits a density, and when the
cost function is the squared Euclidean distance, the optimal coupling is
deterministic, i.e. there exists a transport map, and the optimal solution is
the gradient of a convex function~\citep{brenier:cpam1991}. This has been
exploited to solve the optimal transport problem by numerical partial
differential equation
approaches~\citep{benamou:nm2000,angenent:jma2003,haker:ijcv2004,iollo:jcp2011,papadakis:arxiv2013,benamou2014numerical}.
An alternative formulation proposed by~\citet{aurenhammer:algorithmica1998}
shows that the optimal transport from a source density to a target distribution
of a set of weighted Dirac delta's can be solved through a finite dimensional
unconstrained convex optimization. \citet{merigot:cgf2011} proposes a
multiscale approach for the formulation of~\citet{aurenhammer:algorithmica1998}.
%The multiscale framework proposed here is in essence a generalization of the
%multiscale decomposition idea by~\citet{merigot:cgf2011} to both source and
%target point sets.
Both the numerical PDE based approaches as well as the unconstrained convex
optimization require a discretization of the full domain which is generally not
feasible for higher dimensional domains. For arbitrary cost functions and
distributions the optimal transport problem does typically not result in a
deterministic coupling and can not be solved through PDE based approaches.
\subsection{Discrete Optimal Transport and Linear Programming}
\label{sec:lp}
For two discrete distributions $\mu = \sum_1^n w(x_i) \delta(x_i)$ and $ \nu =
\sum_1^m v(y_i) \delta(y_i)$ with $\sum w(x_i) = \sum v(y_i) = 1$ the optimal
transport problem is equivalent to the linear program
\begin{equation}
\min_\coupling \sum_{\substack{i=1,\dots,n\\ j=1,\dots,m}}
\cost(x_i, y_j) \coupling(x_i, y_j) \quad \text{s.t.}\quad
\begin{cases}
\sum_j \coupling(x_i, y_j) = \mu(\{x_i\})= w(x_i) & \\
\sum_i \coupling(x_i, y_j) = \nu(\{y_j\}) = v(y_j) & \\
\coupling(x_i,y_j)\ge 0
\end{cases}\,.
\label{e:LPformulation}
\end{equation} The solution is called an optimal coupling $\coupling^*$, and the
minimum value attained at $\coupling^*$, is called the cost of $\pi^*$, or the
optimal cost of the transport problem, and is denoted by
$\couplingcost(\coupling^*)=\sum_{i,j} \cost(x_i,y_j)\pi^*(x_i,y_j)$. The
constraints enforce that $\coupling$ is a coupling. The variables
$\coupling(x_i, y_j)$ correspond to the amount of mass transported from
source $x_i$ to target $y_j$, at cost $\cost(x_i, y_j)$. The linear
constraints are of rank $n+m-1$: when $n+m-1$ of the constraints are satisfied,
either the $n$ constraints of the source density or the $m$ constraints of the
target density are satisfied. Since the sum of outgoing mass is equal to the sum
of incoming mass, i.e. $\mu(\Xsp) = \nu(\Ysp)$, it follows that all constraints
must be satisfied. The optimal solution lies, barring degeneracies, on a corner
of the polytope defined by the constraints, i.e. is a basic feasible solution.
This implies that exactly $n+m-1$ entries of the optimal coupling $\coupling$
are non-zero, i.e. $\pi$ is a sparse matrix. The optimal coupling is a Monge
transport map if and only if all the mass of a source $x_i$ is transported to
exactly one target location. A Monge solution does not exist for every optimal
transport problem, in fact a small perturbation of $\mu$ will always suffice to
make a Monge solution impossible.
%Linear programming duality and the special structure of the constraint matrix
%imply that at the optimal solution there exist
%$\phi,\psi:{\Xsp}\rightarrow\mathbb{R}$ such that the {\em reduced cost}
%$\cost(x_i, y_j) - \phi(x_i) - \psi(y_j) \ge 0$ with equality iff
%$\coupling^*(x_i, y_j) > 0$. This also follows directly from the Kantorovich
%dual formulation of optimal transport with $\phi$ and $\psi$ the {\em{potential
%functions}}~\citep[Chapter~5]{villani:book2009}. We exploit the reduced cost
%property to quickly refine approximate solutions propagated across scales.
For source and target data sets with the same cardinality and equally weighted
$\delta$-functions, Kantorovich's optimal transport problem reduces to
an assignment problem, whose solution is a Monge optimal transport map. In this
special case, the optimal transport problem can be efficiently solved by the
Hungarian algorithm~\citep{kuhn:nrlq1955}. The assignment problem results in
a degenerate linear program since only $n$ entries are non-zero (instead of
$2n-1$). We can therefore think of optimal transport as a robust version of
assignments. This can also be seen from the point of view of convexity: in the
assignment problem, $\coupling$ is a permutation matrix deciding to which $y_j$
each $x_i$ is transported. The convex hull of permutation matrices is exactly
the set of doubly-stochastic matrices, to which a coupling $\pi$ belongs as a
consequence of the constraints in \eqref{e:LPformulation}.
For point sets with different cardinalities and/or points with different masses
the optimal transport problem can be solved by a linear program and is a
special case of the minimum cost network flow problem. The minimum cost flow
problem is well studied and a number of
algorithms~\citep{ford:ms1956,klein:ms1967,
cunningham:mp1976,goldberg:stoc1987,bertsekas:or1988,orlin:mp1997} exist for
its solution. This discrete solution approach is not constrained to specific
cost functions and can work with arbitrary cost functions.
However, the linear programming approach neglects possibly useful geometric
properties of the measures and the cost function. Our work makes
assumptions about the underlying geometry of the measure spaces and the
associated cost function, and in this way is a mixing of the low-dimensional
``geometric PDE'' approaches with the discrete non-geometric optimization
approaches. It exploits the geometric assumptions to relieve the shortcomings
of either approach, namely it scales to high-dimensional data, provided that
the intrinsic dimension is low in a suitable sense, and does not require a mesh
data structure. At the same time we use the geometry of the data
to speed up the linear program, which per--se does not leverage geometric
structures.
The refinement strategies of the proposed multiscale approach add subsets of paths among
all pairwise paths at each subsequent scale to improve the optimal transport
plan. This strategy of adding paths, is akin to column generation
approaches~\citep{desrosiers:book2005}. Column generation, first developed
by~\citet{dantzig:informs1960} and~\citet{ford:ms1956}, reduces the number of
variables in a linear program by solving a smaller linear program on a subset
of the original variables and introducing new variables on demand. However, the
proposed approach exploits the geometry of the problem instead of relying on an
auxiliary linear program~\citep{dantzig:informs1960} or shortest path
computations~\citep{ford:ms1956} to detect the entering variables.
\subsection{Approximation Strategies}
In the computer vision literature, the Earth Movers distance or equivalently the
Wasserstein-1 distance, which is simply the cost of the optimal coupling, is
a successful similarity measure for image retrieval~\citep{rubner:iccv1998}. In
this application the transport plan is not of interest but only the final
transport cost. For this
purpose~\citet{indyk2003fast},~\citet{shirdhonkar:cvpr2008} and
~\citet{andoni:soda2008} developed algorithms that compute an approximate cost
but do not yield a transport plan. Some of these approaches are based on the
dual formulation of optimal transport, which involves testing against Lipschitz
functions, and observing that Lipschitz functions may be characterized by decay
properties of their wavelet coefficients. In this sense these approaches
are multiscale as well.
To speed up computations in machine learning
applications~\citet{cuturi:nips2013} proposes to {\em smooth} transport plans by
adding a maximum entropy penalty to the optimal transport formulation. The
resulting optimization problem is efficiently solved through matrix scaling
with Sinkhorn fixed-point iterations. Because of the added regularization
term, the solution will in general be different from the optimal
transportation. It may however be the case that these particular (or
perhaps other) regularized solutions are better suited for certain
applications.
\subsection{Related Work}
Very recently a number of approaches have been proposed to solve the optimal
transport in a multiscale
fashion~\citep{glimm:arxiv2011,schmitzer2013hierarchical,schmitzer2015sparse,oberman2015efficient}.
\citet{glimm:arxiv2011} design an iterative scheme to solve a discrete optimal
transport problem in reflector design and propose a heuristic for the iterative
refinements based on linear programming duality. This iterative scheme can be
interpreted as a multiscale decomposition of the transport problem based on
geometry of the source and target sets. The proposed potential refinement
strategy extends the heuristic proposed by~\citet{glimm:arxiv2011} to guarantee
optimal solutions and adds a more efficient computation strategy: Their
approach requires to check all possible variables at the next scale. In
Section~\ref{sec:potential} we introduce a variation of the approach
by~\citet{glimm:arxiv2011} by adding a branch and bound strategy to avoid
checking all variables, and an iterative procedure that guarantees optimal
solutions.
\citet{schmitzer2013hierarchical} propose a multiscale approach on grids that
uses a refinement strategy based on spatial neighborhoods, akin to the
neighborhood refinement described in Section~\ref{sec:neighborhood}.
\citet{schmitzer2015sparse} uses a multiscale approach to develop a modified
auction algorithm with guaranteed worst case complexity and optimal solutions.
We use data structures that enable us to quickly construct neighborhoods, even
for point clouds that live in high-dimensions, but have low-intrinsic dimension;
we also exploit these structures to not compute all the pairwise possible
costs, as well as the candidate neighborhoods in our propagation steps. This
can result in substantial savings in the scaling of the algorithm, from
$|\mathbf{X}|^3$ to just $|\mathbf{X}|\log|\mathbf{X}|$. We are therefore able
to scale to larger problem, solving on a laptop problems an order of magnitude
larger than those in \citet{oberman2015efficient} for example, and showing
linear scaling on a large range of scales. \citet{schmitzer2015sparse} use the
c--cyclical monotonicity property of optimal transport
plans~\citep[Chapter~5]{villani:book2009} to construct ``shielding
neighborhoods'' that permit to exclude paths from further consideration. The
idea of shielding neighborhoods is combined with a multiscale strategy that
permits to quickly refine initial neighborhood estimates.
Finally, in our work we emphasize that the multiscale construction is not only
motivated by its computational advantage, but also as a way of revealing
possibly important features of the optimal transportation map. As we show in
Section \ref{s:brainMR}, features collected from the multiscale optimal
transportation maps leads to improved predictors for brain conditions. More
generally, we expect multiscale properties of optimal transportation maps to be
useful in a variety of learning tasks; the connections between learning and
optimal transportation are still a very open field, to be explored and
exploited.
\section{Multiscale Optimal Transport}
\label{sec:mdop}
Solving the optimal transport problem for two point sets $\Xsp$ and $\Ysp$
directly requires $|\Xsp||\Ysp|$ variables, or paths to consider. In other
words, the number of paths along which mass can be transported grows
quadratically in the number of points and quickly yields exceedingly large
problems. The basic premise of the multiscale strategy is to solve a sequence
of transport problems based on increasingly accurate approximations of the
source and target point set. The multiscale strategy helps to reduce the
problem size at each scale by using the solution from the previous scale to
inform which paths to include in the optimization at the next finer scale.
Additionally, the solution at the previous scale helps to find a good
initialization for the current scale which results in fewer iterations to solve
the reduced size linear program.
The multiscale algorithm (see Algorithm~\ref{f:algo} and
Figure~\ref{fig:multiscalepic} for a visual illustration) comprises of three
key elements:
\begin{itemize}
\item[(I)] A way of {\textit{\textbf{coarsening} the sets}} of source points ${\Xsp}$ and measure $\mu$ in a multiscale fashion, yielding a chain
\begin{equation}
({\Xsp},\mu)=:({\Xsp}_J,\mu_J) \rightarrow({\Xsp}_{J-1},\mu_{J-1})
\rightarrow\dots\rightarrow({\Xsp}_j,\mu_j)
\rightarrow\dots\rightarrow({\Xsp}_0,\mu_0)
\end{equation}
connecting the scales from fine to coarse, with ${\Xsp}_j$ of decreasing
cardinality as the scale decreases, and the discrete measure $\mu_j$
``representing'' a coarsification of $\mu$ at scale $j$, with
$\mathrm{supp}(\mu_j)={\Xsp}_j$ (the support of $\mu_j$ is the set of points
with positive measure). Similarly for $\Ysp$ and $\nu$ we obtain the chain
\begin{equation}
({\Ysp},\mu)=:({\Ysp}_J,\nu_J) \rightarrow({\Ysp}_{J-1},\nu_{J-1})
\rightarrow\dots\rightarrow({\Ysp}_j,\nu_j)
\rightarrow\dots\rightarrow({\Ysp}_0,\nu_0)
\end{equation}
This coarsening step is described in Section~\ref{sec:coarsening} and the
resulting multiscale family of transport problems is discussed in
Section~\ref{sec:multiscaleproblems}.
\item[(II)] A way of {\textit{\textbf{propagating} a coupling}} $\coupling_j$
solving the transport problem $\mu_j\rightarrowtail\nu_j$ at scale $j$ to a
coupling $\coupling_{j+1}$ at
scale $j+1$. This is described in Section~\ref{sec:propagation}.
\item[(III)] A way of {\textit{\textbf{refining} the propagated solution}} to
the optimal coupling at scale $j$. This is described in
Section~\ref{sec:refinement}.
\end{itemize}
%Let ${\Xsp}_j=\mathrm{supp.}(\mu_j)=:\{x_{j,k}\}_{k=1,\dots,K^{{\Xsp}}_j}$ and
%similarly for $\{y_{j,k}\}_{k=1,\dots,K^{{\Ysp}}_j}$. The coarsening scheme
%guarantees that $K^{{\Xsp}}_j\le K^{{\Xsp}}_{j+1}$ and $K^{{\Ysp}}_j\le
%K^{{\Ysp}}_{j+1}$. The multiscale representation induces a sequence of
%transport problems $\mu_j\rightarrowtail\nu_j$: let $\coupling_j^*$ the
%corresponding optimal coupling. Clearly $\coupling_J^*$ is the solution of the
%optimal transport problem $\mu\rightarrowtail\nu$ since $\mu_J:=\mu$ and
%$\nu_J:=\nu$. The transport problem $\mu_j\rightarrowtail\nu_j$ at scale $j$
%has $K^{{\Xsp}}_j + K^{{\Ysp}}_j$ constraints and $K^{{\Xsp}}_jK^{{\Ysp}}_j$
%paths/variables, with the optimal coupling having (barring degeneracies) only
%$K^{{\Xsp}}_j+K^{{\Ysp}}_j-1$ nonzero entries.
\begin{algorithm}[h]
%\SetAlgoLined
\KwIn{Two discrete measures $\mu$ and $\nu$, and a stopping scale $J_0\le J$}
\KwOut{Multiscale family of transport plans $(\coupling_j: \mu_j\rightarrowtail
\nu_j)_{j=0}^{J_0}$}
Construct multiscale structures $\{\{{\Xsp}_j,\mu_j)\}_{j=0}^J$ and
$\{\{{\Ysp}_j,\nu_j)\}_{j=0}^J$.
Let $\tilde \coupling_0$ be an arbitrary coupling $\mu_0\rightarrowtail\nu_0$.
\For{ $j=0\dots J_0-1$ }{
Refine initial guess $\tilde\coupling_j$ to the optimal coupling $\coupling_j: \mu_j\rightarrowtail\nu_j$.
Propagate $\coupling_j$ from scale $j$ to scale $j+1$, obtaining a
coupling $\tilde\coupling_{j+1}$}
\caption{Multiscale Discrete Optimal Transport
\label{f:algo}
}
\end{algorithm}
%Section~\ref{sec:coarsening} describes the multiscale construction and
%Section~\ref{sec:multiscaleproblems} the resulting multiscale family of optimal
%transport problems. Sections~\ref{sec:propagation} and~\ref{sec:refinement}
%show how to employ these constructions to reduce the size of optimization
%problems solved at each scale.
\subsection{The Coarsening Step: Multiscale Approximations to $\Xsp$, $\mu$ and $\cost$}
\label{sec:coarsening}
To derive approximation bounds for the error of the multiscale transport
problem at each scale we rely on the notion of a regular family of multiscale
partitions formally described in Section~\ref{sec:mspartitions}. The multiscale
partition is used to define approximations to $\mu$ and $\cost$ at
all scales. An integral part of the definitions is that the constructions can be
interpreted as a tree, with all nodes at a fixed height corresponding to one scale
of the multiscale partitioning.
We start with some notation needed for the definition of the
multiscale partitions. Let $({\Xsp},\rho,\mu)$ be a measure metric space with
metric $\rho$ and finite measure $\mu$. Without loss of generality assume that
$\mu(\Xsp)=1$. The metric ball of center $z$ and radius $r$ is $B_z(r)=\{
x\in{\Xsp} : \rho(x,z)<r\}$. We say that ${\Xsp}$ has doubling dimension $d$ if
every ball $B_z(r)$ can be covered by at most $2^d$ balls of radius
$r/2$~\citep{assouad1983plongements}. Furthermore, a space has a doubling
measure if $\mu(B_z(r))\asymp r^d$, i.e. if there exist a constant $c_1$ such
that for every $z\in\Xsp$ and $r>0$ we have $c_1^{-1}r^d\le\mu(B_z(r))\le
c_1r^d$. Here and in what follows, we say that $f\asymp g$ if there are two
constants $c_1,c_2>0$ such that for every $z$ in the domain of both functions
$f,g$ we have $c_1 f(z)\le g(z)\le c_2 f(z)$ (and therefore a similar set of
inequalities holds with the roles of $f$ and $g$ swapped), and we say that $f$
and $g$ have the same order of magnitude. Having a doubling measure implies
having a doubling metric, and up to changing the metric to an equivalent one,
one may choose the same $d$ in the doubling condition for the metric and in
that for the measure: we assume this has been done from now on. This family of
spaces is rather general, it includes regular domains in $\mathbb{R}^D$, as
well as smooth compact manifolds $\mathcal{M}$ endowed with volume measures.
\subsubsection{Multiscale Approximations to $\Xsp$ and $\mu$}
\label{sec:mspartitions}
A regular family of multiscale partitions, with scaling parameter $\theta>1$,
is a family of sets $\{\{C_{j,k}\}_{k=1}^{K_j}\}_{j=0}^J$, where $j$ denotes
the scale and $k$ indexes the sets at scale $j$, such that:
\begin{itemize}
\item[(i)] the sets $\{C_{j,k}\}_{k=1}^{K_j}$ form a partition of ${\Xsp}$,
i.e. they are disjoint and $\cup_{k=1}^{K_j}C_{j,k} = {\Xsp}$;
\item[(ii)] either $C_{j+1,k'}$ does not intersect a $C_{j,k}$, or it is
completely contained in it;
\item[(iii)] there exists a constant $A>0$ such that for all $j,k$ we have
the diameter $\mathrm{diam}(C_{j,k})\le A\theta^{-j}$;
\item[(iv)] each $C_{j,k}$ contains a ``center'' point $c_{j,k}$ such that
$B_{c_{j,k}}(\theta^{-j})\subseteq C_{j,k}$.
\end{itemize}
To ease the notation we will fix $\theta=2$ in what follows, but the
constructions and results hold, mutatis mutandis, for general $\theta>1$. The
properties (i) and (ii) above imply that there exists a tree $\mathcal{T}$, with nodes at
scale $j$ (i.e. at distance $j$ from the root) in bijection with
$\{C_{j,k}\}_{k=1}^{K_j}$, such that $(j+1,k')$ is a child of $(j,k)$ if and
only if $C_{j+1,k'}$ is contained in $C_{j,k}$. Moreover properties (iii) and
(iv), together with the properties of spaces with a doubling measure, imply
that $\mu(C_{j,k})\asymp 2^{-jd}$ and $K_j\asymp 2^{jd}$. These partitions are
classical in harmonic analysis, mimicking dyadic cubes in Euclidean space, and
they have recently been used to construct multiscale decompositions of data
sets in high-dimensions ~\citep{LMR:MGM1,CM:MGM2,IM:GMRA_CS,6410789}. We say
that $C_{j+1,k'}$, or even $(j+1,k')$, is a child of $C_{j,k}$ (respectively,
of $(j,k)$) if $C_{j+1,k'}\subseteq C_{j,k}$, and that such $C_{j,k}$
(respectively $(j,k)$) is a parent of $C_{j+1,k'}$ (resp. $(j+1,k')$).
Given two discrete sets ${\Xsp}$ and ${\Ysp}$ in a doubling metric space of
homogeneous type with dimension $d$, we construct the corresponding families of
multiscale partitions $\{\{C^{{\Xsp}}_{j,k}\}_{k=1}^{K^{{\Xsp}}_j}\}_{j=0}^J$
and $\{\{C^{{\Ysp}}_{j,k}\}_{k=1}^{K^{{\Ysp}}_j}\}_{j=0}^J$ (we assume the same
range of scales to keep the notation simple). The construction of the
multiscale approximations is illustrated in Figure~\ref{fig:multiscalepic}.
\begin{figure}[thb]
\centering
\includegraphics[width=0.99\linewidth]{figures/MultiscalePic.pdf}
\caption{
\label{fig:multiscalepic}
An illustration of the multiscale framework. The coarsening step constructs
from a set of weighted points $\Xsp_{j+1}$ at scale $j+1$ a smaller set of
weighted points at scale $j$ (blue bars). An equivalent
coarsening is performed on the target point set $\Ysp_{j+1}$ Neighboring points
at scale $j+1$ are combined into a single representative at scale $j$ with mass
equivalent to the weights of the combined points. The optimal transport plan
(green arrows) is solved at the coarser scale $j$, then propagated to scale
$j+1$ and refined.
%MAURO: Would it make sense to not use a regular grid as to not give the
%impression we require some regular partitioning? What is the triple prime for
%in the transport plan at scale j?
}
\end{figure}
The space ${\Xsp}_j$ will be the partition at scale $j$, namely the set
$\{C^{{\Xsp}}_{j,k}\}_{k=1}^{K^{{\Xsp}}_j}$, of cardinality $K^{{\Xsp}}_j$.
The measures $\mu$ and $\nu$ may be coarsened in the natural way, by letting
$\mu_j$ be defined recursively on ${\Xsp}_j$ by
\begin{equation}
\mu_j( C_{j,k}^{{\Xsp}} )= \sum_{(j+1,k')\text{ child of } (j,k)} \mu_{j+1}( C_{j+1,k'}^{{\Xsp}} )\,,
\label{e:muj}
\end{equation}
and similarly for $\nu_j$.
These are in fact projections of these measures, and may also be interpreted as
conditional expectations with respect to the $\sigma$-algebra generated by the
multiscale partitions. We can associate a point $\overline c_{j,k}^{{\Xsp}}$
to each $C_{j,k}^{{\Xsp}}$ in various ways, by ``averaging'' the points in
$C_{j+1,k'}^{{\Xsp}}$, for $(j+1,k')$ a child of $(j,k)$. At the finest scale
we may let $\overline{c}^{{\Xsp}}_{J,k}={c}^{{\Xsp}}_{J,k}$ (this being a
``center'' for $C_{J,k}$ as in item (iv) in the definition of multiscale
partitions), and then recursively we defined the coarser centers step from
scale $j+1$ to scale $j$ in one of the following ways:
\begin{itemize}
\item[(i)] If the metric space is also a vector space a natural definition of
$x_{j,k}:=\overline c_{j,k}^{{\Xsp}}$ is a weighted average of the $\overline
c_{j+1,k'}^{{\Xsp}}$ corresponding to children:
$$
\overline{c}^{{\Xsp}}_{j,k} =
\sum_{(j+1,k')\text{ child of } (j,k)} \mu_{j+1}(\{\overline c_{j+1,k'}^{{\Xsp}}\}) \overline c_{j+1,k'}^{{\Xsp}}\,.
$$
\item[(ii)] In general we can define $x_{j,k}:=\overline c_{j,k}^{{\Xsp}}$ as the point
$$
\overline{c}^{{\Xsp}}_{j,k}=\mathrm{argmin}_{c \in{\Xsp}}\,\,
\sum_{(j+1,k')\text{ child of } (j,k) } \rho^p( c, \overline c_{j+1,k'}^{{\Xsp}} ) \,,
$$
for some $p \geq 1$, typically $p=1$ (median) or $p=2$ (Fr\'echet mean).
%\item[(ii)] $x_{j,k}:=\overline c_{j,k}^{{\Xsp}}$ is a point minimizing
\end{itemize}
Of course similar constructions apply to the space ${\Ysp}_j$, yielding points
$y_{j,k}:=\overline c_{j,k}^{{\Ysp}}$.
We discuss algorithms for these constructions in Section \ref{s:multiscalepointsets}.
\subsubsection{Coarsening the cost function $\cost$}
The multiscale partition provides several ways to coarsen the cost function: for
every $x_{j,k}$ and $y_{j,k'}$ we consider
\begin{itemize}
\item[($\cost$-i)] the pointwise value
\begin{equation}
\cost_j(c_{j,k}^{\Xsp}, c_{j,k'}^{\Ysp}) :=
\cost(x_{j,k}^{\Xsp},y_{j,k'}^{\Ysp})\,,
\label{e:costpointwise}
\end{equation}
where $x_{j,k}$ and $y_{j,k'}$ are defined in any of the ways above;
\item[($\cost$-ii)] the local average
\begin{equation}
\cost_j(c_{j,k}^{\Xsp}, c_{j,k'}^{\Ysp}) :=
\argmin_{\alpha} \sum_{\substack{x\in C^{{\Xsp}}_{j,k},\,y \in
C^{{\Ysp}}_{j,k'}}}\left(\alpha-\cost(x,y)\right)^2
= \frac{\sum_{\substack{x\in C^{{\Xsp}}_{j,k},\,y\in
C^{{\Ysp}}_{j,k'}}}\cost(x,y)}{|C_{j,k}^{{\Xsp}}| |C_{j,k'}^{{\Ysp}}|}\,;
\label{e:costlocalave}
\end{equation}
\item[($\cost$-iii)] the local weighted average
\begin{align*}
\cost_j(c_{j,k}^{\Xsp},c_{j,k'}^{\Ysp})
&:=\argmin_{\alpha}\sum_{\substack{x\in C^{{\Xsp}}_{j,k},\, y\in
C^{{\Ysp}}_{j,k'}}}\left(\alpha-\cost(x,y)\right)^2
\coupling^*_{j-1}(x_{j-1,k_1},y_{j-1,k'_1})\\
&=\frac{\sum_{\substack{x\in C^{{\Xsp}}_{j,k},\,y\in C^{{\Ysp}}_{j,k'}}}\cost(x,y)\coupling^*_{j-1}(x_{j-1,k_1},y_{j-1,k'_1})}{
\sum_{\substack{x\in C^{{\Xsp}}_{j,k},\,y\in C^{{\Ysp}}_{j,k'}}}\coupling^*_{j-1}(x_{j-1,k_1},y_{j-1,k'_1})
}\,,
\end{align*}
where $\pi^*_{j-1}$ is the optimal or approximate transportation plan at scale
$j-1$, defined in \eqref{e:LPformulation_j}; $k_1$ is the unique index for
which $C^{{\Xsp}}_{j,k}\subseteq C^{{\Xsp}}_{j-1,k_1}$ and $k'_1$ is the unique
index for which $C^{{\Ysp}}_{j,k}\subseteq C^{{\Ysp}}_{j-1,k'_1}\,.$
\end{itemize}
\subsection{Multiscale Family of Optimal Transport Problems}
\label{sec:multiscaleproblems}
With the definitions of the multiscale family of coarser spaces ${\Xsp}_j$ and
${\Ysp}_j$, corresponding measures $\mu_j$ and $\nu_j$, and corresponding cost
$\cost_j$, we may consider, for each scale $j$, the following optimal transport
problem:
\begin{equation}
\begin{aligned}
\coupling_j^*&: = \argmin_\coupling\!\!\!\sum_{\substack{k=1,\dots,K_j^{{\Xsp}}\\ k'=1,\dots,K_j^{{\Ysp}}}}
\!\!\!\!\cost_j(x_{j,k}, y_{j,k'}) \coupling(x_{j,k}, y_{j,k'})
\,\,\text{s.t.}\,\,
\begin{cases}
\sum_{k'} \coupling(x_{j,k}, y_{j,k'}) = \mu_j(\{x_{j,k}\}) & \forall k\in K_j^\Xsp \\
\sum_{k} \coupling(x_{j,k}, y_{j,k'}) = \nu_j(\{y_{j,k'}\}) & \forall k'\in K_j^\Ysp\\
\coupling(x_{j,k},y_{j,k'})\ge 0
\end{cases}
\label{e:LPformulation_j}
\end{aligned}
\end{equation}
The problems in this family are related to each other, and to the optimal transportation
problem in the original spaces. We define the cost of a coupling as
\begin{equation}
\couplingcost(\coupling_j) = \sum_{\substack{k=1,\dots,K_j^{{\Xsp}}\\
k'=1,\dots,K_j^{{\Ysp}}}} \cost_j(x_{j,k}, y_{j,k'}) \coupling_j(x_{j,k},
y_{j,k'}) \, .
\end{equation}
The cost of the optimal coupling $\coupling_j^*$ at scale $j$ is provably an
approximation to the cost of the optimal coupling $\coupling^*$ (which is equal
to $\coupling_J^*$):
\begin{proposition}
Let $\coupling^*$ be the optimal coupling, i.e. the solution to
\eqref{e:LPformulation}, and $\coupling^*_j$ the optimal coupling at scale $j$,
i.e. the solution to \eqref{e:LPformulation_j}. Define
\begin{equation}
E_j(\coupling^*) := \sum_{\substack{k=1,\dots,K_j^{{\Xsp}}\\ k'=1,\dots,K_j^{{\Ysp}}}}
\sum_{\substack{x\in C^{{\Xsp}}_{j,k}\\ y\in C^{{\Ysp}}_{j,k'}}}
\left(\cost_j(x_{j,k},y_{j,k'})-\cost(x,y)\right) \coupling^*(x,y)\,.
\end{equation}
Then
\begin{equation}
\couplingcost(\coupling_j^*)\le\couplingcost(\coupling^*)+E_j(\coupling^*)\,,
\label{e:UBcouplingcostpij}
\end{equation}
and if $\cost_j=\cost$ and $\cost$ is Lipschitz with constant $||\nabla\cost||_\infty$, we have
\begin{equation}
\couplingcost(\coupling_j^*)\le\couplingcost(\coupling^*)+2^{-j}A||\nabla \cost||_\infty\,,
\label{e:UBcouplingcostpijboundednabld}
\end{equation}
where $A$ is such that
$\max_{k,k'}\{\mathrm{diam}(C^{{\Xsp}}_{j,k}),\mathrm{diam}(C^{{\Ysp}}_{j,k'})\}\le
A\cdot2^{-j}$.
\end{proposition}
\begin{proof}
Consider the coupling $\coupling_j$ induced at scale $j$ by the optimal
coupling $\coupling^*$, defined by
\begin{equation*}
\coupling_j(x_{j,k},y_{j,k'}) = \sum_{\substack{x\in C^{{\Xsp}}_{j,k}\,,
y\in C^{{\Ysp}}_{j,k'}}} \coupling^*(x,y)\,.
\end{equation*}
First of all, since $\{C^{{\Xsp}}_{j,k}\}_k$ and $\{C^{{\Ysp}}_{j,k'}\}_{k'}$
are partitions, it is immediately verified that $\coupling_j$ is a coupling. Secondly,
observe that
\begin{align*}
\couplingcost(\coupling_j)
&=\sum_{\substack{k=1,\dots,K_j^{{\Xsp}}\\ k'=1,\dots,K_j^{{\Ysp}}}}
\cost_j(x_{j,k}, y_{j,k'}) \coupling_j(x_{j,k}, y_{j,k'})
=\sum_{\substack{k=1,\dots,K_j^{{\Xsp}}\\ k'=1,\dots,K_j^{{\Ysp}}}}
\sum_{\substack{x\in C^{{\Xsp}}_{j,k}\\ y\in C^{{\Ysp}}_{j,k'}}}
\cost_j(x_{j,k}, y_{j,k'}) \coupling^*(x,y)\\
&=\sum_{\substack{x\in{\Xsp}\\ y\in{\Ysp}}} \cost(x,y)\coupling^*(x,y)+
\sum_{\substack{k=1,\dots,K_j^{{\Xsp}}\\ k'=1,\dots,K_j^{{\Ysp}}}}
\sum_{\substack{x\in C^{{\Xsp}}_{j,k}\\ y\in C^{{\Ysp}}_{j,k'}}}
\left(\cost_j(x_{j,k},y_{j,k'})-\cost(x,y)\right) \coupling^*(x,y)\\
&= \couplingcost(\coupling^*) + \underbrace{ \sum_{\substack{k=1,\dots,K_j^{{\Xsp}}\\
k'=1,\dots,K_j^{{\Ysp}}}} \sum_{\substack{x\in C^{{\Xsp}}_{j,k}\\ y\in C^{{\Ysp}}_{j,k'}}}
\left(\cost_j(x_{j,k},y_{j,k'})-\cost(x,y)\right) \coupling^*(x,y)}_{=:E_j(\coupling^*)}\,.
\end{align*}
Since $\couplingcost(\coupling^*_j)\le\couplingcost(\coupling_j)$ (since
$\coupling^*_j$ is optimal), we obtain \eqref{e:UBcouplingcostpij}.
When $\cost_j=\cost$ and $\cost$ is Lipschitz with constant $||\nabla\cost||_\infty$, we have
\begin{align*}
E_j(\coupling^*)
&\le \sum_{\substack{k\,:\,x\in C^{{\Xsp}}_{j,k}\\
k'\,:\,y\in C^{{\Ysp}}_{j,k'}}} \sum_{\substack{k=1,\dots,K_j^{{\Xsp}}\\
k'=1,\dots,K_j^{{\Ysp}}}}||\nabla\cost||_\infty\cdot ||(x_{j,k},y_{j,k'})-(x,y)||\coupling^*(x,y)\\
&\le \sum_{\substack{k\,:\,x\in C^{{\Xsp}}_{j,k}\\
k'\,:\,y\in C^{{\Ysp}}_{j,k'}}} \sum_{\substack{k=1,\dots,K_j^{{\Xsp}}\\
k'=1,\dots,K_j^{{\Ysp}}}}||\nabla\cost||_\infty 2^{-j}A\coupling^*(x,y)\\
&\le 2^{-j}A||\nabla\cost||_\infty \,,
\end{align*}
with $A$ as in the claim.
\end{proof}
%This result may also be proven using standard arguments, such as Proposition
%XXX in~\citep{villani:book2009}; we presented the proof above for the sake of
%keeping the presentation self-contained.
In the discrete, finite case that we are considering, $\mu_j\rightarrow\mu$ and
$\nu_j\rightarrow\nu$ trivially since $\mu_J=\mu$ and $\nu_J=\nu$ by
construction. If $\mu$ and $\nu$ were continuous, and at least when
$\cost(x,y)=\rho(x,y)^p$ for some $p\ge1$, then if $\mu$ and $\nu$ have finite
$p$-moment (i.e. $\int_\Xsp \rho(x,x_0)^pd\mu$ and similarly for $\nu$), we
would obtain convergence of a subsequence of $\cost(\coupling^*_j)$ to $\cost(\coupling^*)$ by
general results (e.g. as a simple consequence of Lemma 4.4. in ~\citep{villani:book2009}).
Note that the approximations do not guarantee that the transport plans are
close in any other sense but their cost. Consider the arrangement in
Figure~\ref{fig:counter-approximation}, the transport plans are
$\epsilon$-close in cost but the distances between the target locations of the
sources are far no matter how small $\epsilon$ gets.
\begin{figure}[thb]
\centering
\begin{tabular}{VV}
\includegraphics[width=0.99\linewidth]{counter-approximation} &
\includegraphics[width=0.99\linewidth]{counter-approximation2} \\
(a) & (b)
\end{tabular}
\vspace{-0.1in}
\caption{
\label{fig:counter-approximation}
An example that illustrates that closeness in cost does not indicate closeness
of the transport plan. The transport plans (green arrows) between the sources A
and B (purple) and the targets Y and Z (orange) in (a) and (b) are
$\epsilon$-close but their respective target locations are very far. }
\end{figure}
\subsection{Propagation Strategies}
\label{sec:propagation}
The approximation bounds in Section~\ref{sec:multiscaleproblems} show that the
optimal solution $\coupling_{j}$ at scale $j$ is $| E_{j+1} - E_j |$ close to
optimal solution $\coupling_{j+1}^*$ at scale $j+1$. This suggests that the
solution at scale $j$ can provide a reasonably close to optimal initialization
for scale $j+1$.
As proposed by~\citet{glimm:arxiv2011} the solution at a given scale can be
interpolated at the next scale (or finer discretization). The most direct
approach to initialize the transport problem at scale $j+1$ given the solution
$\coupling_{j}^*$ at scale $j$ is to distribute the mass $\coupling_{j}^*(x_k,
y_{k'})$ equally to all combinations of paths between $\children(x_k)$ and
$\children(y_{k'})$.
%Which a yields a transport plan that exactly satisfies the bound $| E_{j+1} -
%E_j |$.
This propagation strategy results in a reduction in the number of iterations
required to find an optimal solution at the subsequent scale. This
warm-starting alone is often not sufficient, however. At the finest scale the
problems still requires the solution of a problem of size $O(n^2)$. This
quickly reaches memory constraints with $\Omega(10^4)$ points, and a single
iteration of Newton's method or a pivot step of a linear program becomes
prohibitively slow. Thus, we consider reducing the number of variables, which
substantially speeds up the algorithm, albeit we may lose guarantees on its
computational complexity and/or its ability to achieve arbitrary accuracy, so
that only numerical experiments will support our constructions. These
reductions are achieved by considering only a subset $\mathbf{R}_{j+1}$ of all
possible paths $\mathbf{A}_{j+1}$ at scale $j+1$.
To distinguish the optimal solution on the reduced set of paths at scale $j$
from the optimal solution over all paths we introduce some notation. Let
$\mathbf{A}_{j+1}$ be the set of all possible paths between sources and targets
at scale $j+1$. Let $\mathbf{R}_{j+1} \subseteq \mathbf{A}_{j+1}$ be the set of
paths propagated from the previous solution (e.g. children of mass-bearing
paths found at scale $j$). Let $\coupling^*_{j+1} |_{\mathbf{P}}$ be the
optimal solution to the transport problem restricted to a set of paths
$\mathbf{P} \subset \mathbf{A}_{j+1}$. With this notation, $ \coupling_{j+1}^*
|_{\mathbf{A}_{j+1}} = \coupling_{j+1}^*$. The optimal coupling
$\coupling_{j+1}^*|_{\mathbf{R}_{j+1}}$ on the reduced set of paths problem does
not need to match the optimal coupling $\coupling_{j+1}^*$ on all paths.
However $ \coupling_{j+1}^* |_\mathbf{R_{j+1}}$ does provide a starting point
for further refinements discussed in Section~\ref{sec:refinement}.
\subsubsection{Simple Propagation}
\label{sec:simple}
The most direct approach to reduce the number of paths considered at subsequent
scales is to include only paths at scale $j+1$ whose endpoints are children of
endpoints of mass-bearing paths at scale $j$. The optimal solution at scale $j$
has exactly $K_j^{\Xsp} + K_j^{\Ysp} - 1$ paths with non-zero weight. Thus, the
number of paths at scale $j+1$ reduces to $O( C^2(K_{j}^{\Xsp} + K_j^{\Ysp}))$,
where $C$ is the maximal number of children of any node at scale $j$. In
particular, $C\asymp 2^{d}$ for a doubling space of dimension $d$. This reduces
the number of variables from ``quadratic'', $O(K_{j}^{\Xsp} K_j^{\Ysp} )$, to
linear, $O(K_{j}^{\Xsp}+K_j^{\Ysp} )$. This propagation strategy by itself,
however, often leads to a dramatic loss of accuracy in both the cost the
transportation plan, and the transportation plan itself.
\subsubsection{Capacity Constraint Propagation}
\label{sec:capacity}
This propagation strategy solves a modified minimum flow problem at scale $j$
in order to include additional paths at scale $j+1$ that are likely to be
included in the optimal solution $\coupling_{j+1}^*$. This is achieved by
adding a capacity constraint to the mass bearing paths at scale $j$ in the
optimal coupling $ \coupling_j^* |_{\mathbf{R}_j}$: The amount of mass of a
mass bearing path $ \coupling_j^* |_{\mathbf{R}_j}( x_{j,k}, y_{j,k'} )$ is
constrained to $\lambda \min \left ( \mu_j(x_{j,k}), \nu_j(y_{j,k'}) \right)$
with $\lambda$ random uniform on $[0.1, 0.9]$. The randomness is introduced to
avoid degenerate constraints. The solution of this modified minimum--flow
problem forces the inclusion of $n_c$ additional paths, where $n_c$ is the
number of constraints added. There are various options for adding capacity
constraints, we propose to constrain all mass bearing paths of the optimal
solution at scale $\coupling_j^*|_{\mathbf{R}_j}$. The capacity constrained
problem thus results in a solution with twice the number of paths as in the
coupling $\coupling_j^*|_{\mathbf{R}_j}$. The solution of the capacity
constrained minimum flow problem is propagated as before to the next scale.
To increase the likelihood of including paths required to find an optimal
solution at the next scale, the capacity constrained procedure can be iterated
multiple times. Each time the mass bearing paths in the modified solution are
constrained and a new solution is computed. Each iteration doubles the number
of mass bearing paths and the number of iterations controls how many paths are
propagated to the next scale. Thus, the capacity constraint propagation
strategy bounds the number of paths considered in the linear program. The
optimal transport plan on a source set $\Xsp$ and $\Ysp$ results in a linear
program with $|\Xsp| + |\Ysp|$ constraints and $|\Xsp| |\Ysp|$ variables and
the optimal transport plan has $|\Xsp| + |\Ysp| - 1$ mass bearing paths. It
follows that the capacity constraint propagation strategy considers linear
programs with at most $O\left( 2^i (|\Xsp| + |\Ysp|) \right)$ constraints,
where $i$ is the number of iterations of the capacity propagation scheme. This
results in a significant reduction in problem size, since at each scale we only
consider a number of paths scaling as $O(|\Xsp|+|\Ysp|)$ instead of $O(|\Xsp|
|\Ysp|)$.
\subsection{Refinement Strategies}
\label{sec:refinement}
Solving the reduced transport problem at scale $j+1$, propagated from scale
$j$, can not guarantee an optimal solution at scale $j+1$. Propagating a
sub-optimal solution further may lead to an accumulation of errors. This
section describes strategies to refine the reduced transport problem to find
closer approximations or even optimal transport plans at each scale. These
refinement strategies are essentially batch column generation
methods~\citep{desaulniers:book2002}, that take advantage of the multiscale
structure.
\subsubsection{Potential Refinement}
\label{sec:potential}
This refinement strategy exploits the potential functions, or dual solution, to
determine additional paths to include given the currently optimal solution on
the reduced set of paths from the propagation. The dual formulation of the
optimal transport can be written as:
\begin{equation}
\max_{\phi, \psi}
\sum_{i=1,\dots,n} \mu(\{x_i\}) \phi(x_i) -
\sum_{j=1,\dots,m} \nu(\{y_j\}) \psi(y_j)
\quad \text{s.t.} \quad