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:
- Data Fidelity: Measured by the Wasserstein distance ($W_p$), which quantifies how well the curve fits the data.
- 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.
- 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.
- 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.
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