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, under some assumption on the original measure, a solution to the relaxed problem is a solution to the original one. Finally we prove that, whenever the original measure has a density in $L^{d/(d-1)}(\mathbb{R}^d)$, any optimal solution is supported by an Ahlfors regular set.
Introduction
Approximating complex probability distributions with lower-dimensional structures is a fundamental challenge in data science and geometric analysis. This paper introduces a novel variational method to approximate measures using 1D connected structures, such as curves or networks. By combining the Wasserstein distance—a metric from optimal transport—with a novel length functional, the authors bridge the gap between geometric shape optimization and transport theory.
Consider a cloud of data points in high-dimensional space. A common goal is to find a "skeleton" or 1D summary that captures the distribution's essence. While existing methods like principal curves focus on geometric proximity, they often neglect the underlying data density. This work seeks a 1D connected set $\Sigma$ such that the uniform distribution on $\Sigma$ is as close as possible to the target distribution in terms of Wasserstein distance.
The Challenge of Existence and Relaxation
A primary mathematical hurdle in this pursuit is that the space of uniform measures on 1D sets is not closed. Sequences of such measures may converge to structures that are neither uniform nor one-dimensional, making it difficult to prove the existence of an optimal solution. To address this, the authors employ a relaxation strategy:
- The Original Problem ($P_\Lambda$): Minimize the sum of the Wasserstein distance (fidelity) and the length of the set (regularization).
- The Relaxed Problem ($\overline{P}_\Lambda$): A new length functional $\mathcal{L}(\nu)$ is defined for any probability measure. This functional determines the minimum length of a 1D set required to support a measure, accounting for its density.
To analyze this relaxed formulation, the study utilizes advanced tools from Geometric Measure Theory, including rectifiability, blow-up analysis, and generalizations of Gołąb’s Theorem regarding the lower semi-continuity of length.
Key Theoretical Insights
The Concentration Effect
The interplay between length minimization and distance fidelity often causes measures to "pile up" on specific segments of the 1D set. The relaxed functional $\mathcal{L}(\nu)$ is essential because it explicitly accounts for this non-uniformity, which the original formulation could not handle.
Phase Transitions
The authors identify a critical threshold for the regularization parameter, $\Lambda_\star$. If the penalty on length is too high ($\Lambda > \Lambda_\star$), the optimal approximation for any data cloud collapses to a single point (the p-mean). This phase transition defines the regime where meaningful 1D structures can emerge. Analytical solutions for simple cases, such as two Dirac masses, demonstrate how the optimal solution transitions from a single point to a line segment as $\Lambda$ varies.
Density and Regularity
A significant result of the paper is the link between the smoothness of the original data and the regularity of the resulting skeleton. If the target measure possesses a density in the Lebesgue space $L^{d/(d-1)}$, the optimal solution is supported by an Ahlfors regular set. This ensures the skeleton is a well-behaved curve rather than a fragmented or infinitely complex structure.
Results and Future Directions
The authors rigorously prove that the relaxed problem always possesses a solution. Furthermore, they demonstrate that under reasonable conditions—specifically when the original measure is not already concentrated on a 1D curve—the solution to the relaxed problem coincides with the solution to the original, more intuitive problem. All optimal measures are shown to be 1D-rectifiable.
While this work provides a robust theoretical foundation, several avenues for future research remain. The topological properties of the optimal skeleton (e.g., whether it is always a tree) and higher-order regularity (such as $C^{1,\alpha}$ smoothness) are yet to be fully characterized. Additionally, translating these analytical proofs into efficient numerical algorithms, perhaps via phase-field approximations, represents a vital step toward practical applications in 3D reconstruction and data compression.
Summary updated