Monge-Kantorovich Fitting With Sobolev Budgets

Given m < n, we consider the problem of ``best'' approximating an n-d probability measure ρ via an m-d measure nu such that supp nu has bounded total ``complexity.'' When ρ is concentrated near an m-d set we may interpret this as a manifold learning problem with noisy data. However, we do not restrict our analysis to this case, as the more general formulation has broader applications. We quantify nu's performance in approximating ρ via the Monge-Kantorovich (also called Wasserstein) p-cost mathbbWpp(ρ, nu), and constrain the complexity by requiring supp nu to be coverable by an f : ℝm → ℝn whose Wk,q Sobolev norm is bounded by ℓ ≥ 0. This allows us to reformulate the problem as minimizing a functional mathscr Jp(f) under the Sobolev ``budget'' ℓ. This problem is closely related to (but distinct from) principal curves with length constraints when m=1, k = 1 and an unsupervised analogue of smoothing splines when k > 1. New challenges arise from the higher-order differentiability condition. We study the ``gradient'' of mathscr Jp, which is given by a certain vector field that we call the barycenter field, and use it to prove a nontrivial (almost) strict monotonicity result. We also provide a natural discretization scheme and establish its consistency. We use this scheme as a toy model for a generative learning task, and by analogy, propose novel interpretations for the role regularization plays in improving training.