# Multiresolution Analysis Applied to the Monge-Kantorovich Problem

Authors: Armando Sánchez-Nungaray; Carlos González-Flores; Raquiel R. López-Martínez
Journal: Abstract and Applied Analysis
 (2018)

---

## Abstract

We give a scheme of approximation of the MK problem based on the symmetries of the underlying spaces. We take a Haar type MRA constructed according to the geometry of our spaces. Thus, applying the Haar type MRA based on symmetries to the MK problem, we obtain a sequence of transportation problem that approximates the original MK problem for each of MRA. Moreover, the optimal solutions of each level solution converge in the weak sense to the optimal solution of original problem.


---

## Body

## 1. Introduction

The optimal transport problem was first formulated by Monge in 1781 and concerned finding the optimal way in the sense of minimal transportation cost of moving a pile of soil from one site to another. This problem was given a modern formulation in the work of Kantorovich in 1942 and so is now known as the Monge-Kantorovich problem.On the other hand, a big advantage over schemes of approximation was given in the seminal article [1]; it introduced approximation schemes for infinite linear program; in particular, it showed that under suitable assumptions the program’s optimum value can be finite-dimensional linear programs and that, in addition, every accumulation point of a sequence of optimal solutions for the approximating programs is an optimal solution for the original problem. An example given in this article is the Monge-Kantorovich mass transfer (MK) problem on the space itself, where the underlying space is compact.In [2], a general method of approximation for the MK problem is given, where X and Y are Polish spaces; however, this method is noneasier implementation. Later, in [3], a scheme of approximation of MK problem is provided, which consists in giving a sequence of finite transportation problems underlying original MK problem (the space is compact); nevertheless, a general procedure is given, but the examples are in a two-dimensional cube and use the dyadic partition of the cube for approximation. Our objective is to give other families to approximate this kind of problems, based on Haar type multiresolution analysis (MRA). The advantage of using this technique is that we select a multiresolution analysis that is constructed according to the symmetries of the underlying space. Therefore, the new schemes of approximation take a lot of characteristics of the space into consideration. Note that the dyadic partition of the cube is a particular case of the MRA type Haar using translations and dilations of the underlying space.The MRA is an important method to approximate functions in different context (signal processing, differential equations, etc.). In particular, we focus on Haar type MRA onRn; the constructions of this kind of MRA are associated with the symmetries of the spaces; thus the approximations are related to the geometrical properties of the space. In this construction, the symmetries that we use are general dilations, rotations, reflections, translations, and so forth; for more details, see [4–6].The main objective of this paper is giving a scheme of approximation of the MK problem based on the symmetries of the underlying spaces. We take a Haar type MRA constructed according to the geometry of our spaces. Thus, applying the Haar type MRA based on symmetries to the MK problem, we obtain a sequence of transportation problems that approximate the original MK problem for each level of MRA. Moreover, the optimal solutions of each level solution converge in the weak sense to the optimal solution of original problem.This paper is organized as follows. In Section2, we introduce the basic elements of the Haar type multiresolution analysis and we give some examples of this kind of MRA. In Section 3, we present the approximation of probability measures using Haar type MRA. In Section 5, we apply the Haar type multiresolution analysis to MK problem for each level of this MRA; thus for each level, this new problem is equivalent to transport problem. Moreover, we prove that the optimal solution of MK problems is equal to the limit of the optimal solutions of underlying transportation problems when the level of the MRA goes to infinity. Finally, we give an illustrative example of this method.


## 2. Haar Type Multiresolution Analysis

We introduce the basic concepts of Haar type multiresolution analysis, following Gröchenig and Madych in [4] and Guo et al. in [5]. Similar results have been obtained independently by Krishtal et al. to be published in [6].LetΓ be a lattice such that Γ=MZn for any M∈GLn(R). The classical multiresolution analysis (MRA) associated with a sequence of dilations {aj}j∈Z=A, where |deta|≤1, is a sequence {Vj}j∈Z of closed subspaces of L2(Rn), which satisfies the following conditions:(i)
Vk⊂Vk+1.(ii)
⋃j∈ZVj¯=L2(Rn).(iii)
⋂j∈ZVj={0}.(iv)
Vj=Da-jV0.(v)
There existsφ∈V0 such that {Tγφ}, γ∈Γ, is an orthonormal basis for V0.LetB be a finite subgroup of GLn(R) such that |detb|=1 for all b∈B and Γ=B(Γ). The operator generator by the dilations Db, b∈B, and the translations Tγ, γ∈Γ form a group. The relation (1)DcTτDbTγf=DcbTb-1τ+γf.allows us to define the operation to B×Γ given by (2)c,τ·b,γ=cb,b-1τ+γand we obtain a new group denoted by BΓ. The BΓ-invariant spaces are the closed subspaces V of L2(Rn) such that DbTγf∈V whenever f∈V, b∈B, and γ∈Γ. This leads us to the following version of (v): (v′
) There existsφ∈V0 such that {DbTγφ}, b∈B and γ∈Γ, is an orthonormal basis for V0.In consequence, we have the following concept.Definition 1.
LetA={aj}i∈Z be dilatation set, let B be a finite subgroup of GLn(R) with |detb|=1, and let Γ be a complete lattice such that Γ=B(Γ). The multiresolution analysis associated with the dilation set A and the group B or AB-MRA is a collection {Vj}j∈Z of closed subspaces of L2(Rn), which satisfies conditions (i), (ii), (iii), (iv), and (v′).The classical MRA is considered as anAB-MRA when B is the trivial group. Note that the space V0 is not generated by the Γ-translations of the single scaling function φ; however, the relation DbTγφ=TbγDbφ and the conditions B(Γ)=Γ imply that the functions Dbφ, with b∈B, are the generators of V0. Also, we have the following set:(3)Γj=ajγ:γ∈γNote that Γj⊂Γj+1 and BΓj=Γ.We consider the scaling functionφ=EχΔ, where χΔ is the characteristic function of Δ⊂Rn, E∈R, and φ2=1. The region Δ satisfies(4)⋃α∈BΓΔα=Rnwhere intΔα∩intΔα′=∅ for α≠α′ and Δα is the action of α=(b,γ) on Δ. In addition, the symbol Δαj denotes the translation and scaling of the region Δ by α and aj, respectively. Thus, the function DajDbTγφ=|deta|-j/2EχΔαj is denoted by φαj. And so we have the following relation: (5)∑α∈BΓφαj=det⁡a-j/2E∑α∈BΓχΔαj=det⁡a-j/2E·χRn.Finally, we definePj as the orthogonal projection from L2(Rn) to Vj which is given by(6)Pjf=∑α∈BΓf,φαjφαjfor all f∈L2(Rn).We show some examples of the multiresolution analysis associated with the dilation setA and the finite group B:(1)
We take a matrixa=q=1-111 and the group B={bi}, 0≤i≤7, of symmetries of unit square; thus, (7)b0=1001,b1=0110,b2=0-110,b3=-1001,andbi=-bi-4 for 4≤i≤7. Let Δ0 be the triangular region with vertices in (0,0), (1/2,0), and (1/2,1/2); we denote Δi=biΔ0 for 1≤i≤7. If φ=22χΔ0, then the system (8)DbTkφ:b∈B,k∈Z2is an orthogonal basis for its closed spanV0. The space V0 is the subspace of L2(R2), consisting of all square integrable functions that are constant on each Z2-translate of the triangles Δi, 1≤i≤7. Thus, the spaces Vj=Dq-jV0, j∈Z, consist of all functions in L2(R2), which are constant in each q-jZ2-translate of the triangles q-1Δi, 1≤i≤7, in consequence Vj⊂Vj+1. Hence, {Vj} is an AB-MRA with φ as a scaling function.Figure1 is reproduced from Krishtal et al. (2007) [under the Creative Commons Attribution License/public domain].(2)
LetB be the group generated by the matrix ρ=1/21-331. This group has order of 6 and is the counter-clockwise rotation by π/3 radians. Consider the hexagon with vertices in set (9)±32,0,34,±34,-34,±34.LetΔ0 be the triangle with vertices in (0,0), (3/2,0), and (3/4,3/4). We define Δi=ρiΔ0 for 0≤i≤5. We take c=1/403363 and we define Γ=cZ2. The set of all functions that are constant on Γ-translates of triangles Δi, 0≤i≤5, is the space V0⊂L2(R2). Moreover, the elements of Γ translate the center of the hexagon to the point of Γ, and so we have a partition of R2. Let q=1-331 and the function φ=EχΔ0, with E=4/274. The MRA {Vj} is obtained by the system (10)DqjDρiTγφ:j∈Z,0≤i≤5,γ∈Γwhere the spacesVj are q-j-dilatation of V0, for j∈Z.Figure2 can be found in [6].Figure 1Figure 2


## 3. Approximation of Measures Using Multiresolution Analysis

### 3.1. Absolutely Continuous Measures with respect to Lebesgue Measures

We consider the following conditions:(A1)
X is a compact subset of Rn.(A2)
The measureμ is absolutely continuous with respect to λ, where λ is the Lebesgue measure.Condition (A2) guarantees the existence of functionsf∈L1(X), where f is the Radon-Nikodym derivative with respect to Lebesgue measure λ.In this analysis, we also assume the following extra condition:(A3)
The functionsf also belong in L2(Xk).Notice that(11)f∈L1X∩L2X⊂L2Rn.Let{Vj} be an AB-MRA on Rn; the elements of {Vj} are given by scaling functions φ=E1χΔ, the latice Γ, finite group B1, and dilatation A={a1j}.Remark 2.
Note that the classical multiresolution analysis of Haar onL2(R2) is a particular case of AB-MRA on R2, where the complete lattice is Γ=Z2, the group B is trivial, and the dilation associated is A={2-j(1,1)}. In this case, we have that scaling function is φΔ, where Δ=[0,1]×[0,1] is the fundamental domain associated with the action of Γ on R2.We denote byPj the projection from L2(Rn) into Vj, which is given by (12)Pjf=∑α∈BΓjf,φαjφαjfor all f∈L2(Rn). Moreover, if the function f has support in X, then the above sum is finite, since X is compact.From now on, we shall only functions with support in the compact setX and we have L2(X)⊂L2(Rn); that is, each function f∈L2(X) can be considered in L2(Rn), where f(x)=0 if x∉X.We know that theAB-MRA is dense in L2(X); thus we have that (13)Pjf-f2⟶0,whenj⟶∞Using the fact that X is compact, we obtain that (14)Pjf-f1≤λX1/2Pjf-f2From the above equation, we define the approximation of the measure to the levelj by(15)dμj=Pjfdλ,which are measures in X for each j. Now we want to prove that these measures are probability measures.Definition 3.
The expectationE with respect to Lebesgue measure λ of function f is defined by (16)Ef=∫Rnfdλ,where f is a Lebesgue measurable function. Also, the conditional expectation of f given A, with A being a Lebesgue measurable set, is defined by E[f∣A]=E[f·χA].In particular, the expectation on the Lebesgue measureλ satisfies the following property.Theorem 4.
Consider thatj∈Z is fixed and f∈L2(Rn). Then E[Pjf]=E[f], where Pj is the projection of the level j associated with AB-MRA {Vj}.Proof.
We takef∈L2(Rn); now we calculate E[Pjf]; thus (17)EPjf=∫Rn∑α∈BΓf,φαjφαjdλ=∑α∈BΓf,φαj∫RnφαjdλWe have that the functions φαj=EjχΔαj, where Δαj is the translation and dilation of the fundamental region Δ and Ej=λ(Δαj)-1/2; this value does not depend on α. From this, we have that (18)∫Rnφk=∫Δkφk=Ej-1.
Using the above equations, we have that(19)EPjf=∑α∈BΓf,χΔαj.Moreover, using the fact that Δαj∩Δβj=∅ for α≠β, it is clear that (20)EPjf=f,∑α∈BΓχΔαj=f,χRn=Ef.As immediate consequence of the previous theorem, we get the following result.Corollary 5.
We suppose that the measureμ on X satisfies (A1)-(A2); then the sequences of probability measures {μj}⊂M+(X) given by (15) converge to μ in L1 and L2 sense.


### 3.2. Non-Absolutely-Continuous Measures with respect to Lebesgue Measure

Now, we consider thatμ is a probability measure on the compact set X, which is unnecessarily absolutely continuous measure with respect to Lebesgue measure λ. Note that each element of sequence (15) can be written by(21)μjU=∑α∈BΓμΔαjλU∩ΔαjλΔαjfor all Borel measurable sets U on X. Moreover, these approximations are well defined for every measure μ on X.Definition 6.
Let{μn;n≥0} be a sequence of probability measures on a metric space (X,d). We say that μn converges weakly to μ and denote μn→wμ if μn(f)→μ(f) as n→∞ for all bounded continuous functions f on M, where μ(f)=∫M‍fdμ.Theorem 7.
Given a measureμ on the compact set X, the sequence of measures {μj} on X defined in (21) converge weakly to measure μ.Proof.
Letf:X→R be a continuous and bounded real function. From the fact that X is compact, we obtain that f is absolutely continuous function on X; thus, given ϵ>0, there exists δ>0 such that (22)x-y<δimpliesfx-fy<ϵ2We take j0∈Z such that for all x,y∈Δαj implies |x-y|<δ for all j≥j0 and α∈BΓ. Moreover, we know that there exist α1,…,αr∈BΓ such that (23)X⊂⋃m=1rΔαmj.
In consequence, we obtain the following relations:(24)∫Xfdμ-∫Xfdμj≤∫∪Δαmjfdμ-∫∪Δαmjfdμj≤∑m=1r∫Δαmjfdμ-∫Δαmjfdμj=∑m=1r∫Δαmjfdμ-∫ΔαmjfμΔαmjλΔαmjdλ;we take an element xαmj∈Δαmj to obtain the following relations: (25)∫Δαmjfdμ-∫Δαmjfxαmjdμ+fxαmjμΔαmj-∫ΔαmjfμΔαmjλΔαmjdλ≤∫Δαmjf-fxαmjdμ+μΔαmjλΔαmj∫Δαmjf-fxαmjdλTherefore, (26)∫Xfdμ-∫Xfdμj≤∑m=1r∫Δαmjf-fxαmjdμ+μΔαmjλΔαmj∫Δαmjf-fxαmjdλ<∑m=1rϵ2∫Δαmjdμ+μΔαmjλΔαmjϵ2∫Δαmjdλ=ϵ2∑m=1rμΔαmj+μΔαmjλΔαmjλΔαmj=ϵ∑m=1rμΔαmj=ϵ·μX=ϵ.


## 3.1. Absolutely Continuous Measures with respect to Lebesgue Measures

We consider the following conditions:(A1)
X is a compact subset of Rn.(A2)
The measureμ is absolutely continuous with respect to λ, where λ is the Lebesgue measure.Condition (A2) guarantees the existence of functionsf∈L1(X), where f is the Radon-Nikodym derivative with respect to Lebesgue measure λ.In this analysis, we also assume the following extra condition:(A3)
The functionsf also belong in L2(Xk).Notice that(11)f∈L1X∩L2X⊂L2Rn.Let{Vj} be an AB-MRA on Rn; the elements of {Vj} are given by scaling functions φ=E1χΔ, the latice Γ, finite group B1, and dilatation A={a1j}.Remark 2.
Note that the classical multiresolution analysis of Haar onL2(R2) is a particular case of AB-MRA on R2, where the complete lattice is Γ=Z2, the group B is trivial, and the dilation associated is A={2-j(1,1)}. In this case, we have that scaling function is φΔ, where Δ=[0,1]×[0,1] is the fundamental domain associated with the action of Γ on R2.We denote byPj the projection from L2(Rn) into Vj, which is given by (12)Pjf=∑α∈BΓjf,φαjφαjfor all f∈L2(Rn). Moreover, if the function f has support in X, then the above sum is finite, since X is compact.From now on, we shall only functions with support in the compact setX and we have L2(X)⊂L2(Rn); that is, each function f∈L2(X) can be considered in L2(Rn), where f(x)=0 if x∉X.We know that theAB-MRA is dense in L2(X); thus we have that (13)Pjf-f2⟶0,whenj⟶∞Using the fact that X is compact, we obtain that (14)Pjf-f1≤λX1/2Pjf-f2From the above equation, we define the approximation of the measure to the levelj by(15)dμj=Pjfdλ,which are measures in X for each j. Now we want to prove that these measures are probability measures.Definition 3.
The expectationE with respect to Lebesgue measure λ of function f is defined by (16)Ef=∫Rnfdλ,where f is a Lebesgue measurable function. Also, the conditional expectation of f given A, with A being a Lebesgue measurable set, is defined by E[f∣A]=E[f·χA].In particular, the expectation on the Lebesgue measureλ satisfies the following property.Theorem 4.
Consider thatj∈Z is fixed and f∈L2(Rn). Then E[Pjf]=E[f], where Pj is the projection of the level j associated with AB-MRA {Vj}.Proof.
We takef∈L2(Rn); now we calculate E[Pjf]; thus (17)EPjf=∫Rn∑α∈BΓf,φαjφαjdλ=∑α∈BΓf,φαj∫RnφαjdλWe have that the functions φαj=EjχΔαj, where Δαj is the translation and dilation of the fundamental region Δ and Ej=λ(Δαj)-1/2; this value does not depend on α. From this, we have that (18)∫Rnφk=∫Δkφk=Ej-1.
Using the above equations, we have that(19)EPjf=∑α∈BΓf,χΔαj.Moreover, using the fact that Δαj∩Δβj=∅ for α≠β, it is clear that (20)EPjf=f,∑α∈BΓχΔαj=f,χRn=Ef.As immediate consequence of the previous theorem, we get the following result.Corollary 5.
We suppose that the measureμ on X satisfies (A1)-(A2); then the sequences of probability measures {μj}⊂M+(X) given by (15) converge to μ in L1 and L2 sense.


## 3.2. Non-Absolutely-Continuous Measures with respect to Lebesgue Measure

Now, we consider thatμ is a probability measure on the compact set X, which is unnecessarily absolutely continuous measure with respect to Lebesgue measure λ. Note that each element of sequence (15) can be written by(21)μjU=∑α∈BΓμΔαjλU∩ΔαjλΔαjfor all Borel measurable sets U on X. Moreover, these approximations are well defined for every measure μ on X.Definition 6.
Let{μn;n≥0} be a sequence of probability measures on a metric space (X,d). We say that μn converges weakly to μ and denote μn→wμ if μn(f)→μ(f) as n→∞ for all bounded continuous functions f on M, where μ(f)=∫M‍fdμ.Theorem 7.
Given a measureμ on the compact set X, the sequence of measures {μj} on X defined in (21) converge weakly to measure μ.Proof.
Letf:X→R be a continuous and bounded real function. From the fact that X is compact, we obtain that f is absolutely continuous function on X; thus, given ϵ>0, there exists δ>0 such that (22)x-y<δimpliesfx-fy<ϵ2We take j0∈Z such that for all x,y∈Δαj implies |x-y|<δ for all j≥j0 and α∈BΓ. Moreover, we know that there exist α1,…,αr∈BΓ such that (23)X⊂⋃m=1rΔαmj.
In consequence, we obtain the following relations:(24)∫Xfdμ-∫Xfdμj≤∫∪Δαmjfdμ-∫∪Δαmjfdμj≤∑m=1r∫Δαmjfdμ-∫Δαmjfdμj=∑m=1r∫Δαmjfdμ-∫ΔαmjfμΔαmjλΔαmjdλ;we take an element xαmj∈Δαmj to obtain the following relations: (25)∫Δαmjfdμ-∫Δαmjfxαmjdμ+fxαmjμΔαmj-∫ΔαmjfμΔαmjλΔαmjdλ≤∫Δαmjf-fxαmjdμ+μΔαmjλΔαmj∫Δαmjf-fxαmjdλTherefore, (26)∫Xfdμ-∫Xfdμj≤∑m=1r∫Δαmjf-fxαmjdμ+μΔαmjλΔαmj∫Δαmjf-fxαmjdλ<∑m=1rϵ2∫Δαmjdμ+μΔαmjλΔαmjϵ2∫Δαmjdλ=ϵ2∑m=1rμΔαmj+μΔαmjλΔαmjλΔαmj=ϵ∑m=1rμΔαmj=ϵ·μX=ϵ.


## 4. Discretization of the Monge-Kantorovich Problem Using Multiresolution Analysis

LetM(X×Y) be the linear space of finite signed on X×Y and let M+(X×Y) be the set of all nonnegative measures in M(X×Y). Given μ∈M(X×Y), we denote by Π1μ and Π2μ the marginal of μ on X and Y, respectively; that is, (27)Π1μA×Y=ν1A,Π2μX×B=ν2Bfor all sets A and B, such that ν1 and ν2 are measurable, respectively.The Monge-Kantorovich mass transfer problem is given as follows:(28)
MK:  minimize
μ
,
c
≔
∫
c
d
μ
subject  to:
Π
1
μ
=
ν
1
,
Π
2
μ
=
ν
2
,
μ
∈
M
+
X
×
YA measureμ∈M(X×Y) is said to be a feasible solution for MK problem if it satisfies (28) and 〈μ,c〉 is finite. The MK problem is called consistent if the set of feasible solutions is nonempty, in which case its optimal value is defined as (29)inf⁡MK=inf⁡μ,c:μis  a  feasible  solution  for  MK.It is said that the MK problem is solvable if there is a feasible solutionμ∗ that attains the optimal value. In this case, μ∗ is called an optimal solution for the MK problem and the value inf⁡(MK) is written as min⁡(MK)=〈μ∗,c〉.Note that sinceν1 and ν2 are probability measures, a feasible solution for MK is also a probability measure. Moreover, if c is a continuous function on X×Y and X and Y are compact subsets on Rn, then the product measure μ≔ν1×ν2 is a feasible solution. Therefore the MK problem is consistent, and so the MK problem is solvable in this case.We assume the following conditions:X and Y are compact subsets of Rn and c:X×Y→R is a bounded continuous function.Let{Vj} and {Vj′} be AB-MRA on Rn with scaling functions φ1=E1χΔ1 and φ2=E2χΔ2, lattices Γ1 and Γ2, finite groups B1 and B2, and dilatations A1={a1j} and A2={a2j}, respectively. We can obtain a new AB-MRA {Vj∗} on R2n with scaling functions φ=φ1φ2=E1E2χΔ1×Δ2, lattice Γ=Γ1×Γ2, finite group B=B1×B2, and dilatation {a1j×a2j}. The projections of these AB-MRA to the level j are denoted by P1j, P2j, and Qj.Now we proceed to discretization of the MK-problem using the results of Section2; then we have that μj, ν1j, and ν2j are the projections to level j of the respective AB-MRA; thus, using these measures, we obtain the discretization of the MK-problem in the level j, which is given by(30)
M
K
j
:
m
i
n
i
m
i
z
e
μ
j
,
c
≔
∫
c
d
μ
j
subject  to:
Π
1
μ
j
=
ν
1
j
,
Π
2
μ
j
=
ν
2
j
,
μ
j
∈
M
+
X
×
Y
.We shall give explicit expressions for the discretization of the measures and the cost function associated with MK-problem using theAB-MRA, which are given by(31)μj=∑α,β∈BΓ0jμα,βjφ1,αjxφ2,βjy,withμα,βj=μ,φ1,αjφ2,βj≥0cj=∑α,β∈BΓ0jcα,βjφ1,αjxφ2,βjy,withcα,βj=c,φ1,αjφ2,βjν1j=∑α∈BΓ10jaαjφ1,αjx,withaαj=ν1,φ1,αjν2j=∑β∈BΓ20jbβjφ2,βjy,withbβj=ν2,φ2,βjwhere μα,βj, aα,βj, and bα,β are nonnegative real numbers. Now we calculate 〈μj,c〉; thus (32)μj,c=μj,Qjc+Qjc⊥=Qjc,μj,and hence, using the above equation and the orthonormality of family {φ1,αjφ2,βj}, we obtain(33)μj,c=∑α,β∈BΓ0jcα,βj·μα,βj.We consider thatαi is a fixed element in (BΓ1)0j and we have that Δ1,αij is the region associated with αi for i=1,…,r; then we obtain (34)μjΔ1,αij×Rn=∫Δ1,αij×Rndμj=∫R2nχΔ1,αij·χRn∑α,β∈BΓμα,βjφ1,αjxφ2,βjydλxdλy=∑α,β∈BΓμα,βj∫RnχΔ1,αij·E1χΔ1,αjxdλx·∫RnχRn·E2χΔ2,βjydλy=∑β∈BΓ20jμαi,βj.On the other hand, we have that(35)ν1jΔ1,αij=∫Δ1,αijP1jf1xdλx=∫Δ1,αij∑α∈BΓ10jaαjφ1,αjx=∑α∈BΓ10jaαj∫RnχΔ1,αij·E1χΔ1,αjxdλx=aαijFrom the above equations, we have that the condition μj(Δ1,αij×Rn)=ν1j(Δ1,αij) is equivalent to (36)∑β∈BΓ20jμαi,βj=aαij,,i=1,…,r.Analogously, for all the elementsβ1,…,βs of (BΓ2)0j, we have that(37)∑α∈BΓ10jμα,βkj=bβkj,k=1,…,s.Using Theorem 4, we obtain that(38)∑α,β∈BΓ0jμα,βj=∑k=1raαkj=∑k=1sbβkj=1In summary, we have that theMKj problem given by (30) is equivalent to the following problem:(39)MKDj:minimize∑α,β∈BΓ0jμα,βj·cα,βjsubject  to:∑β∈BΓ20jμαk,βj=aαkjk=1,…r∑α∈BΓ10jμα,βkj=bβkj,k=1,…s∑α,β∈BΓ0jμα,βj=1μα,βj≥0,∀α,β∈BΓ0jThe problemMKDj, given the above system, has a feasible solution, so we know that c is bounded. Then we have that the problem MKDj has an optimal solution; for more details, see Chapter 10 in [7].Letμ∗ be the optimal solution of MK problem given in (28). We use the optimal solution μ∗ to induce a sequence of measures μ∗j such that μ∗j=Qjμ∗ (see Section 3.2). Let η∗j be the optimal solution of MKj problem given in (30).Forj∈Z, we defined the following σ-algebras: (40)F1j=Δ1,αj,∀α∈BΓ1jF2j=Δ2,βj,∀β∈BΓ2jFj=Δα,βj,∀α,β∈BΓjwhere 〈Ai〉i∈I denotes the σ-algebra generated by the sets Ai with i∈I and the lattices BΓ1j, BΓ2j, and BΓj are defined as in (3).Definition 8.
LetF′ be a sub-σ-algebra of F, and let X∈L1 be a random variable. We say that the random variable X′ is the conditional expectation of X with respect to F′ and denote it by E[X∣F′] if and only if (i)
X′∈L1.(ii)
X′ is F′-measurable.(iii)
E[X′χA]=E[XχA], for all a∈F′.Remark 9.
Givenf∈L1(X1×X2), we have that (41)Ef∣Fj=EQjf.There are analogous results for P1j and P2j through the conditional expectations of F1j and F2j, respectively.Proposition 10.
Letμ be a feasible solution of the MK problem; then μj is a feasible solution of the MKDj-problem.Proof.
We suppose thatμ satisfies (28). Then we have the following relations: (42)Π1μjE=μ∗jE×Rn=∫E×Rndμ∗j=∫E∫Rn∑α,β∈BΓ0jμα,βjφ1,αjxφ2,βjydxdy=∫E∑α,β∈BΓ0jμα,βjφ1,αjx∫Rnφ2,βjydydx=∫E∑α,β∈BΓ0jμα,βjφ1,αjxE2j-1dx=∫E∑α,β∈BΓ0j∫Δ1,α×Δ2,βE1jdμφ1,αjxdx=∫E∑α∈Γ1∑β∈BΓ0jαE1j2χΔ1,αjxdx=∫E∑α∈Γ1∫Δ1,α×RndμE1j2χΔ1,αjxdx=ν1jEwhere [(BΓ)0j]α={(α,β)∈(BΓ)0j:αisfixed} and E a measurable set. Similarly, we obtain that Π2μj(E)=ν2j(E). Therefore the result is as follows.Remark 11.
Ifμ∗ is an optimal solution of the MK problem, then μ∗j is a feasible solution of the MKDj-problem.Proposition 12.
GivenE∈F1j and F∈F2j, one has (43)ηjE×Rn=μE×Rn,ν1jE=ν1EηjRn×F=μRn×F,ν2jF=ν2F,where μ and ηj are feasible solutions of the MK and MKj problems, respectively.Proof.
LetΔαj be a generator element of σ-algebra Fj. Then (44)μΔαj×Rj=Π1μΔαj=ν1Δαj=ν1jΔαj=Π1ηjΔαj=ηjΔαj×RjIn above equation, we use the fact that ν1j(E)=ν1(E) for all E∈Fj in consequence ηj(E×Rn)=μ(E×Rn) for all E∈F1j. Analogously, we have that ηj(Rn×F)=μ(Rn×F).Definition 13.
Let(X,τ) be a topological space, and let F be σ-algebra on X that contains the topology τ. Let M be a collection of measures defined on F. The collection M is called tight if, for any ϵ>0, there is a compact subset Kϵ of X such that, for all measures μ∈M, |μ|(X∖Kϵ)<ϵ, where |μ| is the total variation measure of μ.Proposition 14.
Consider the sequence{η∗j} of probability measures, where η∗j is the optimal solution of MKj for each j∈Z. Then there exists a subsequent {η∗jn} and a probability measure η∗ such that μ∗jn→μ∗ weakly. Moreover, the probability measure η∗ is an optimal solution of MK.Proof.
We know thatX1 and X2 are compact sets, provided that the measures {μ∗j} are tight for each j∈Z. Now, using Prokhorov’s Theorem (for details, see Chapter 1 in [8]), there exists a subsequence {μ∗jn} of {μ∗j} and a probability measure η∗ such that μ∗jn→η∗ weakly.
Notice thatμ∗jn is an optimal solution of MKjn; thus, we obtain (45)Π1μ∗jn=ν1jn,Π2μ∗jn=ν2jn.Using the Theorem, we have that Π1μ∗jn→ν1 and Π2μ∗jn→ν2 weakly. From this fact, it is clear that η∗ is a feasible solution of MK.
Now, we considerμ∗ as the optimal solution of MK. from Proposition 10, we have that μ∗j is feasible solution of MKj. It follows that (46)η∗j,c≤μ∗j,c;taking the limit when j→∞, we have (47)η∗,c≤μ∗,c.
On the other hand,η∗ is a feasible solution of MK; then (48)μ∗,c≤η∗,c,which completes the proof of the theorem.


## 5. An Illustrative Example of This Method

In this section, we present an example of the ideas presented in the previous section. LetC be the square with vertices in the points (49)-52,±12,-32,±12and let H be a hexagon with vertices being in set (50)±32,0,34,±34,-34,±34We consider the function c:C×H→R defined by c(x,y)=x-y2. We claim to solve the following problem:(51)MK  minimize:μ,csubject  to:Π1μ=λ1,Π2μ=λ2,μ∈M+X×Ywhere λ1 and λ2 are the normalized Lebesgue measures to C and H, respectively; that is, λ1(C)=λ2(H)=1. We consider the following AB-MRA on L2(R2): (1)
{V1j}, where the fundamental region is Δ1=[0,1/2]×[0,1/2] and the scaling function φ1=2χ[0,1/2]×[0,1/2], the lattice is Γ1=Z2, the finite group B1 is the trivial group, and the dilation A1={2-j(1,1)}.(2)
{V2j}, where the scaling function φ2=EχΔ2, with Δ2 being the triangle with vertices in (0,0), (3/2,0), and (3/4,3/4) and E=4/274; the lattice is Γ2=c1Z2, where c1=1/403363; the finite group B2 is the rotation group of a regular hexagon with vertices in the unit circle; the scaling is given by A2={aj}, where a=1-331.We denote byCmj and Tnj the squares and the triangles associated with level j of the multiresolution analysis presented above. Since c is a continuous function in each pair of sets (Cmj,Tnj), we have that c|Cmj×Tnj is approximated to c(xmj,ynj), where xmj and ymj are the centroids of Cmj and Tnj, respectively.In particular, we present a discretization of MK problem given by (51) for the level j=2; the graphical description of the process of discretization is given in Figure 3 (which was generated using Mathematica 11.1.0).Figure 3Using{V1j} and {V2j} in C and H, respectively, notice that C is the union of congruent squares {Cm2}m=164 with disjoined interiors. Similarly, the hexagon H is the union by congruent equilateral triangles {Tn2}n=196, with disjoined interiors. Note that λ(Cm2)=1/64 and λ(Tn2)=1/96.In consequence, a discrete approximation for the problem defined in (51) is as follows:(52)MKD2:minimize∑m=164∑n=196xm2-yn22·μm,n2subject  to:∑n=196μm,n2=196m=1,…,64∑m=164μm,n2=164,n=1,…,96∑m=116∑n=124μm,n2=1,μm,n2≥0∀m=1,…,64,n=1,…,96.The optimal solution of this linear programming problem is 4.02996. In Table 1 we present the solution for some levels.Table 1 Level Solution MK1 4.037306413676646 MK2 4.029959684992724 MK3 4.026748275774876


## 6. Conclusions

The application of the Haar type multiresolution analysis (MRA) to the problem of Monge-Kantorovich allows us to obtain a discretization scheme for this problem at each level of the MRA; moreover, this MRA is based on the symmetries of the underlying space. This is an advantage because it provided us a natural method of discretization based on the geometry. Each level of the MRA induces a soluble finite linear programming problem. So, we obtain a sequence of optimal solutions of these transport problems and this sequence converges weakly to the optimal solution of the original problem.



---

*Source: 1764175-2018-06-03.xml*