One-dimensional approximation of measures in Wasserstein distances

Antonin Chambolle, Vincent Duval, Joao Miguel Machado

Abstract: We propose a variational approach to approximate measures with measures uniformly distributed over a 1-dimensional set. The problem consists in minimizing a Wasserstein distance as a data term with a regularization given by the length of the support. As it is challenging to prove existence of solutions to this problem, we propose a relaxed formulation, which always admits a solution. In the sequel we show that if the ambient space is $\mathbb{R}^2$, under technical assumptions, any solution to the relaxed problem is a solution to the original one. Finally we manage to prove that any optimal solution to the relaxed problem, and hence also to the original, is Ahlfors regular.

Introduction: The Principal Curve Problem

In geometric data analysis, a fundamental task is summarizing high-dimensional data clouds using simpler, lower-dimensional structures. This paper addresses the "principal curve" problem: finding a one-dimensional curve or network that best approximates a probability distribution $\rho_0$.

Mathematically, this is framed as a shape optimization problem. We seek a connected 1D set $\Sigma$ that minimizes a cost function balancing two competing interests:

  1. Data Fidelity: Measured by the Wasserstein distance ($W_p$), which quantifies how well the curve fits the data.
  2. Regularization: Measured by the length ($\mathcal{H}^1$) of the curve, preventing it from becoming infinitely complex or "wiggly."

The major theoretical challenge is existence. In the standard topology of measures, a sequence of curves might converge to a limit that isn't a simple curve—it might "double back" or concentrate mass in non-uniform ways. This makes the original problem ill-posed, as a "best" curve might not exist within the class of standard sets.

A Relaxed Variational Approach

The authors' primary innovation is a relaxed formulation of the problem that guarantees the existence of a solution.

  1. The Length Functional: Instead of penalizing the raw length of a set, they define a functional $\mathcal{L}(\nu)$ for any probability measure $\nu$. This functional acts as the "lower semi-continuous envelope" of the length, allowing the optimization to consider limit measures that might have concentrated mass while still penalizing them based on their underlying 1D geometry.
  2. Variational Energy: They define a relaxed energy functional: $$E(\nu) = W_p^p(\rho_0, \nu) + \Lambda \mathcal{L}(\nu)$$ Because this energy is lower semi-continuous, the "direct method of the calculus of variations" can be applied to prove that a minimizer always exists (Theorem 3.11).

Key Insights and the Concentration Effect

A critical insight of the paper is why simple length is insufficient. A sequence of curves can converge to a measure that looks 1D but possesses "hidden" length due to overlapping or high-density regions.

Figure 1: Illustration of a sequence of curves $\Sigma_n$ converging to a limit $\Sigma$, where the limit measure captures 'hidden' length through density and Dirac masses.

As illustrated in Figure 1, a sequence of spirals or zigzags $\Sigma_n$ can converge to a limit $\Sigma$. The resulting measure $\mathcal{H}^1 \lfloor \Sigma_n$ does not simply converge to $\mathcal{H}^1 \lfloor \Sigma$; instead, it might converge to a measure with higher density (e.g., $2\mathcal{H}^1 \lfloor \Sigma$) or even include Dirac masses ($\delta_{x_0}$) at points of extreme concentration. The relaxed formulation $\mathcal{L}(\nu)$ is designed to account for these geometric limits.

Geometric Regularity

Beyond existence, the authors prove that these optimal solutions are well-behaved.

  • Equivalence: Theorem 6.4 shows that if the input data $\rho_0$ is sufficiently "diffuse" (e.g., it doesn't concentrate on 1D lines), the optimal relaxed measure $\nu$ is indeed a uniform measure on a 1D set, solving the original problem.
  • Ahlfors Regularity: Theorem 7.2 establishes that the support of the optimal solution is Ahlfors regular. This means the curve is not fractal; the amount of curve within a small ball is proportional to the ball's radius, a hallmark of "nice" geometric objects.
  • The Critical Parameter ($\Lambda_\star$): There exists a threshold for the regularization parameter $\Lambda$. If the penalty on length is too high ($\Lambda > \Lambda_\star$), the optimal approximation collapses to a single point (a Dirac mass).

Conclusion and Future Directions

This work provides a solid theoretical foundation for 1D measure approximation. However, several open questions remain:

  • Topology: Does the optimal set always form a tree, or can it contain loops?
  • Higher Regularity: Is the resulting set a smooth $C^{1,\alpha}$ curve?
  • Numerical Implementation: Translating these analytical functionals into efficient algorithms for manifold learning and 3D reconstruction is a key next step.

Reference: Chambolle, A., Duval, V., & Machado, J. M. (2024). One-dimensional approximation of measures in Wasserstein distances. arXiv:2304.14781v3 [math.AP].

Summary updated

Abstract

We propose a variational approach to approximate measures with measures uniformly distributed over a 1 dimentional set. The problem consists in minimizing a Wasserstein distance as a data term with a regularization given by the length of the support. As it is challenging to prove existence of solutions to this problem, we propose a relaxed formulation, which always admits a solution. In the sequel we show that if the ambient space is $\mathbb{R}^2$ , under techinical assumptions, any solution to the relaxed problem is a solution to the original one. Finally we manage to prove that any optimal solution to the relaxed problem, and hence also to the original, is Ahlfors regular.
BibTeX
@article{chambolle2024one,
  author = {Antonin Chambolle and Vincent Duval and Joao Miguel Machado},
  title = {{One-dimensional approximation of measures in Wasserstein distances}},
  journal = {Journal de l’École Polytechnique — Mathématiques},
  year = {2024},
  doi = {10.5802/jep.286},
}
Figure