Given a data distribution that is concentrated around a one-dimensional structure, can we infer that structure? We consider versions of this problem where the distribution resides in a metric space and the 1d structure is assumed to either be the range of an absolutely continuous curve, a connected set of finite 1d Hausdorff measure, or a general 1-rectifiable set. In each of these cases, we relate the inference task to solving a variational problem where there is a trade-off between data fidelity and simplicity of the inferred structure; the variational problems we consider are closely related to the so-called “principal curve” problem of Hastie and Steutzle as well as the “average-distance problem” of Buttazzo, Oudet, and Stepanov. For each of the variational problems under consideration, we establish existence of minimizers, stability with respect to the data distribution, and consistency of a discretization scheme which is amenable to Lloyd-type numerical methods. Lastly, we consider applications to estimation of stochastic processes from partial observation, as well as the lineage tracing problem from mathematical biology.

This is joint work with Anton Afanassiev, Forest Kobayashi, Young-Heon Kim, and Geoff Schiebinger.

Refreshments will be served preceding the talk, starting at 2:45.