Curve based approximation of measures on manifolds by discrepancy minimization [original]

Foundations of Computational Mathematics

https://doi.org/10.1007/s10208-021-09491-2

Curve Based Approximation of Measures on Manifolds by

Discrepancy Minimization

Martin Ehler1·Manuel Gräf2·Sebastian Neumayer3·Gabriele Steidl3

Received: 7 November 2019 / Revised: 1 July 2020 / Accepted: 15 December 2020

Abstract

The approximation of probability measures on compact metric spaces and in par-

ticular on Riemannian manifolds by atomic or empirical ones is a classical task in

approximation and complexity theory with a wide range of applications. Instead of

point measures we are concerned with the approximation by measures supported on

Lipschitz curves. Special attention is paid to push-forward measures of Lebesgue mea-

sures on the unit interval by such curves. Using the discrepancy as distance between

measures, we prove optimal approximation rates in terms of the curve’s length and

Lipschitz constant. Having established the theoretical convergence rates, we are inter-

ested in the numerical minimization of the discrepancy between a given probability

measure and the set of push-forward measures of Lebesgue measures on the unit inter-

val by Lipschitz curves. We present numerical examples for measures on the 2- and

3-dimensional torus, the 2-sphere, the rotation group on R3and the Grassmannian of

all 2-dimensional linear subspaces of R4. Our algorithm of choice is a conjugate gra-

dient method on these manifolds, which incorporates second-order information. For

efficient gradient and Hessian evaluations within the algorithm, we approximate the

given measures by truncated Fourier series and use fast Fourier transform techniques

on these manifolds.

Keywords Approximation of measures ·Curves ·Discrepancies ·Fourier methods ·

Manifolds ·Non-convex optimization ·Quadrature rules ·Sampling theory

Mathematics Subject Classification 28E99 ·49Q99 ·65D99

1 Introduction

The approximation of probability measures by atomic or empirical ones based on their

discrepancies is a well examined problem in approximation and complexity theory

Communicated by Alan Edelman.

Extended author information available on the last page of the article

123

Foundations of Computational Mathematics

[59,62,67] with a wide range of applications, e.g., in the derivation of quadrature rules

and in the construction of designs. Recently, discrepancies were also used in image

processing for dithering [46,72,77], i.e., for representing a gray-value image by a finite

number of black dots, and in generative adversarial networks [28].

Besides discrepancies, Optimal Transport (OT) and in particular Wasserstein dis-

tances have emerged as powerful tools to compare probability measures in recent

years, see [24,81] and the references therein. In fact, so-called Sinkhorn divergences,

which are computationally much easier to handle than OT, are known to interpolate

between OT and discrepancies [30]. For the sample complexity of Sinkhorn diver-

gences we refer to [37]. The rates for approximating probability measures by atomic

or empirical ones with respect to Wasserstein distances depend on the dimension of the

underlying spaces, see [21,58]. In contrast, approximation rates based on discrepan-

cies can be given independently of the dimension [67], i.e., they do not suffer from the

curse of dimensionality. Additionally, we should keep in mind that the computation

of discrepancies does not involve a minimization problem, which is a major drawback

of OT and Sinkhorn divergences. Moreover, discrepancies admit a simple description

in Fourier domain and hence the use of fast Fourier transforms is possible, leading to

better scalability than the aforementioned methods.

Instead of point measures, we are interested in approximations with respect to

measures supported on curves. More precisely, we consider push-forward measures

of probability measures ω∈P([0,1])by Lipschitz curves of bounded speed, with

special focus on absolutely continuous measures ω=ρλ and the Lebesgue measure

ω=λ. In this paper, we focus on approximation with respect to discrepancies. For

related results on quadrature and approximation on manifolds, we refer to [31,47,64,

65] and the references therein. An approximation model based on the 2-Wasserstein

distance was proposed in [61]. That work exploits completely different techniques

than ours both in the theoretical and numerical part. Finally, we want to point out

a relation to principal curves which are used in computer science and graphics for

approximating distributions approximately supported on curves [49,50,50,55,57]. For

the interested reader, we further comment on this direction of research in Remark 3and

in the conclusions. Next, we want to motivate our framework by numerous potential

applications:

– In MRI sampling [11,17], it is desirable to construct sampling curves with short

sampling times (short curve) and high reconstruction quality. Unfortunately, these

requirements usually contradict each other and finding a good trade-off is neces-

sary. Experiments demonstrating the power of this novel approach on a real-world

scanner are presented in [60].

– For laser engraving [61] and 3D printing [20], we require nozzle trajectories based

on our (continuous) input densities. Compared to the approach in [20], where

points given by Llyod’s method are connected as a solution of the TSP (traveling

salesman problem), our method jointly selects the points and the corresponding

curve. This avoids the necessity of solving a TSP, which can be quite costly,

although efficient approximations exist. Further, it is not obvious that the fixed

initial point approximation is a good starting point for constructing a curve.

123

Foundations of Computational Mathematics

– The model can be used for wire sculpture creation [2]. In view of this, our numerical

experiment presented in Fig. 5can be interpreted as a building plan for a wire

sculpture of the Spock head, namely of a 2D surface. Clearly, the approach can be

also used to create images similar to TSP Art [54], where images are created from

points by solving the corresponding TSP.

– In a more manifold related setting, the approach can be used for grand tour com-

putation on G2,4[5], see also our numerical experiment in Fig. 11. More technical

details are provided in the corresponding section.

Our contribution is two-fold. On the theoretical side, we provide estimates of the

approximation rates in terms of the maximal speed of the curve. First, we prove approx-

imation rates for general probability measures on compact Ahlfors d-regular length

spaces X. These spaces include many compact sets in the Euclidean space Rd, e.g.,

the unit ball or the unit cube as well as d-dimensional compact Riemannian manifolds

without boundary. The basic idea consists in combining the known convergence rates

for approximation by atomic measures with cost estimates for the traveling salesman

problem. As for point measures, the approximation rate Ld/(2d−2)≤L−1/2for general

ω∈P([0,1])and Ld/(3d−2)≤L−1/3for ω=λin terms of the maximal Lipschitz

constant (speed) Lof the curves does not crucially depend on the dimension of X.In

particular, the second estimate improves a result given in [18] for the torus.

If the measures fulfill additional smoothness properties, these estimates can be

improved on compact, connected, d-dimensional Riemannian manifolds without

boundary. Our results are formulated for absolutely continuous measures (with respect

to the Riemannian measure) having densities in the Sobolev space Hs(X),s>d/2. In

this setting, the optimal approximation rate becomes roughly speaking L−s/(d−1).Our

proofs rely on a general result of Brandolini et al. [13] on the quadrature error achiev-

able by integration with respect to a measure that exactly integrates all eigenfunctions

of the Laplace–Beltrami with eigenvalues smaller than a fixed number. Hence, we need

to construct measures supported on curves that fulfill the above exactness criterion.

More precisely, we construct such curves for the ddimensional torus Td, the spheres

Sd, the rotation group SO(3)and the Grassmannian G2,4.

On the numerical side, we are interested in finding (local) minimizers of discrep-

ancies between a given continuous measure and those from the set of push-forward

measures of the Lebesgue measure by bounded Lipschitz curves. This problem is tack-

led numerically on T2,T3,S2as well as SO(3)and G2,4by switching to the Fourier

domain. The minimizers are computed using the method of conjugate gradients (CG)

on manifolds, which incorporates second order information in form of a multipli-

cation by the Hessian. Thanks to the approach in the Fourier domain, the required

gradients and the calculations involving the Hessian can be performed efficiently by

fast Fourier transform techniques at arbitrary nodes on the respective manifolds. Note

that in contrast to our approach, semi-continuous OT minimization relies on Laguerre

tessellations [41], which are not available in the required form on the 2-sphere, SO(3)

or G2,4.

This paper is organized as follows: In Sect. 2we give the necessary preliminaries

on probability measures. In particular, we introduce the different sets of measures

supported on Lipschitz curves that are used for the approximation. Note that measures

123

Foundations of Computational Mathematics

supported on continuous curves of finite length can be equivalently characterized

by push-forward measures of probability measures by Lipschitz curves. Section 3

provides the notation on reproducing kernel Hilbert spaces and discrepancies including

their representation in the Fourier domain. Section 4contains our estimates of the

approximation rates for general given measures and different approximation spaces of

measures supported on curves. Following the usual lines in approximation theory, we

are then concerned with the approximation of absolutely continuous measures with

density functions lying in Sobolev spaces. Our main results on the approximation

rates of smoother measures are contained in Sect. 5, where we distinguish between

the approximation with respect to the push-forward of general measures ω∈P[0,1],

absolute continuous measures and the Lebesgue measure on [0,1]. In Sect. 6we

formulate our numerical minimization problem. Our numerical algorithms of choice

are briefly described in Sect. 7. For a comprehensive description of the algorithms on

the different manifolds, we refer to respective papers. Section 8contains numerical

results demonstrating the practical feasibility of our findings. Conclusions are drawn

in Sect. 9. Finally, Appendix A briefly introduces the different manifolds Xused in our

numerical examples together with the Fourier representation of probability measures

on X.

2 Probability Measures and Curves

In this section, the basic notation on measure spaces is provided, see [3,32], with focus

on probability measures supported on curves. At this point, let us assume that

Xis a compact metric space endowed with a bounded non-negative Borel mea-

sure σX∈M(X)such that supp(σX)=X. Further, we denote the metric by

distX.

Additional requirements on Xare added along the way and notations are explained

below. By B(X)we denote the Borel σ-algebra on Xand by M(X)the linear space of

all finite signed Borel measures on X, i.e., the space of all μ:B(X)→Rsatisfying

μ(X)<∞and for any sequence (Bk)k∈N⊂B(X)of pairwise disjoint sets the relation

μ(∞

k=1Bk)=∞

k=1μ(Bk).Thesupport of a measure μis the closed set

supp(μ) := x∈X:B⊂Xopen, x∈B⇒ μ(B)>0.

For μ∈M(X)the total variation measure is defined by

|μ|(B):= sup∞



k=1|μ(Bk)|: ∞



k=1

Bk=B,Bkpairwise disjoint.

With the norm μM=|μ|(X)the space M(X)becomes a Banach space. By C(X)

we denote the Banach space of continuous real-valued functions on Xequipped with

the norm ϕC(X):= maxx∈X|ϕ(x)|. The space M(X)can be identified via Riesz’

theorem with the dual space of C(X)and the weak-∗topology on M(X)gives rise to

123

Foundations of Computational Mathematics

the weak convergence of measures, i.e., a sequence (μk)k⊂M(X)converges weakly

to μand we write μkμ,if

lim

k→∞X

ϕdμk=X

ϕdμfor all ϕ∈C(X).

For a non-negative, finite measure μ,letLp(X,μ)be the Banach space (of equivalence

classes) of complex-valued functions with norm

fLp(X,μ) =X|f|pdμ1

<∞.

By P(X)we denote the space of Borel probability measures on X, i.e., non-negative

Borel measures with μ(X)=1. This space is weakly compact, i.e., compact with

respect to the topology of weak convergence. We are interested in the approximation

of measures in P(X)by probability measures supported on points and curves in X.To

this end, we associate with x∈Xa probability measure δxwith values δx(B)=1if

x∈Band δx(B)=0 otherwise.

The atomic probability measures at Npoints are defined by

Patom

N(X):= N



k=1

wkδxk:(xk)N

k=1∈XN,(w

k)N

k=1∈[0,1]N,



k=1

wk=1.

In other words, Patom

N(X)is the collection of probability measures, whose support

consists of at most Npoints. Further restriction to equal mass distribution leads to the

empirical probability measures at Npoints denoted by

Pemp

N(X):= 1



k=1

δxk:(xk)N

k=1∈XN.

In this work, we are interested in the approximation by measures having their

support on curves. Let C([a,b],X)denote the set of closed, continuous curves

γ:[a,b]→X. Although our presented experiments involve solely closed curves,

some applications might require open curves. Hence, we want to point out that all of

our approximation results still hold without this requirement. Upper bounds would not

get worse and we have not used the closedness for the lower bounds on the approxi-

mation rates. The length of a curve γ∈C([a,b],X)is given by

(γ ) := sup

a≤t0≤...≤tn≤b

n∈N



k=1

distXγ(tk), γ (tk−1).

If (γ ) < ∞, then γis called rectifiable. By reparametrization, see [48,Thm.3.2],

the image of any rectifiable curve in C([a,b],X)can be derived from the set of closed

123

Loading more pages...