Forest Kobayashi

For a fixed, compactly supported probability measure $\mu$ on the $d$-dimensional space ${\mathbb{R}}^d$, we consider the problem of minimizing the $p^{\mathrm{th}}$-power average distance functional over all compact, connected $\mathrm{\Sigma }\subseteq {\mathbb{R}}^d$ with Hausdorff 1-measure ${\mathcal{H}}^1(\mathrm{\Sigma })\le l$. This problem, known as the average distance problem, was first studied by Buttazzo, Oudet, and Stepanov in 2002, and has undergone a considerable amount of research since. We will provide a novel approach to studying this problem by analyzing it using the so-called _barycentre field_ considered previously by Hayase and two of the authors. This allows us to provide a complete topological description of minimizers in arbitrary dimensions when $p=2$ and $p>\frac{1}{2}(3+\sqrt{5})\approx 2.618$, the first such result that includes the case when $d>2$.

Less-technical abstract: The average distance problem (ADP) basically gives a model for how to define the “best” 1d shape (of finite total length) that “fills” a given region, where we are given a weighting that tells us that some areas of the region are more/less important to fill than some of the others. With this setup, we proved (in general dimensions and for most values of a certain parameter $p$) that the optimal shapes have to be trees, thus mostly resolving a longstanding question in the literature.

Motivating example: Here you can think of the problem of trying to design the “most efficient” water pipe network for a city. Here, it’s instructive to think of two naïve solutions that both end up being inefficient. On one extreme, you could think about giving every client a direct water pipe that connects to the central pumping station and nowhere else. This manages to get every client water, but in most situations it ends up being super inefficient in terms of the amount of piping you have to use.

On the other extreme, you could try making your network one really long pipe that visits each client in sequence (e.g. a TSP tour). This is usually better than the first solution, but you can still end up doing some things inefficiently. For example, if you have three clients arranged at the vertices of an equilateral triangle of side length 1, and the pumping station is at the centroid of the triangle, then visiting the clients in sequential order ends up requiring $2+\frac{1}{\sqrt{3}}$ units of pipe length, while giving them each their own individual pipe ends up being better, requiring $\frac{3}{\sqrt{3}}$ units of pipe.

The optimal solution should probably instead be some sort of compromise between these two pictures: Maybe at a coarse scale you can “cluster” groups of points together (representing e.g. a single neighborhood in the city), send one big “artery” pipe out to each cluster, and then as you get close, you can split these “artery” pipes into smaller “capillary” pipes that branch out towards each individual client. In fact, the choice of terms “artery” and “capillary” here is evocative, since the ADP can also serve as a model for designing efficient vascular networks for oxygenating tissue!

What we did: Rather than considering the case of discrete “clients” (which would fall under the context of the Steiner problem; see e.g. Paolini’s papers on the Steiner problem), we consider the case where there are so many clients that it makes sense to model them via a continuous distribution (i.e. a probability measure). It turns out one can show that, like the Steiner problem, optimal solutions must be tree shapes.

Why we might care: The characterization of the topology of optimizers means we can create more-principled numerical approaches that explicitly account for branching etc., as will be detailed in a forthcoming work with Wenjun Zhao and Young-Heon Kim.

@article{O'Brien2025Mar,
author = {O'Brien, Lucas and Kobayashi, Forest and Kim, Young-Heon},
title = {{Structure of average distance minimizers in general dimensions}},
journal = {ArXiv e-prints},
year = {2025},
month = mar,
eprint = {2503.23256},
doi = {10.48550/arXiv.2503.23256}
}

Copy to Clipboard

We introduce principal curves in Wasserstein space, and in general compact metric spaces. Our motivation for the Wasserstein case comes from optimal-transport-based trajectory inference, where a developing population of cells traces out a curve in [Wasserstein space](https://en.wikipedia.org/wiki/Wasserstein_metric). Our framework enables new experimental procedures for collecting high-density time-courses of developing populations of cells: time-points can be processed in parallel (making it easier to collect more time-points). However, then the time of collection is unknown, and must be recovered by solving a _seriation problem_ (or one-dimensional manifold learning problem). We propose an estimator based on Wasserstein principal curves, and prove it is consistent for recovering a curve of probability measures in Wasserstein space from empirical samples. This consistency theorem is obtained via a series of results regarding principal curves in compact metric spaces. In particular, we establish the validity of certain numerical discretization schemes for principal curves, which is a new result even in the Euclidean setting.

Less-technical abstract: The principal curve problem is to find the “most efficient” curve that “fits” a point cloud. Here, “efficient” means that the curve should strike a good balance between being close (on average) to all the data points while also remaining relatively simple (i.e. not too long). We consider this problem in the context of geodesic metric spaces and establish existence and consistency results. We also do some numerical experiments for the particular case of principal curves in Wasserstein space, which finds applications in the context of single-cell RNA sequencing.

Motivating example: Suppose you’re given a collection of data that you think was generated from a 1d curve (possibly with some noise). Assume that the data is given as a point cloud, with no information ordering the points along the generating curve. The question is, given enough data, can you reconstruct a good guess for what the generating curve was? (Essentially, this is like a nonlinear, unsupervised version of the least-squares problem.) The principal curve problem gives one possible formulation of this question.

As it turns out, for the most part, the fundamental structure in this problem only depends on the distance metric axioms and the existence of geodesics. So, we can work in the general context of a geodesic metric space. This is useful because one of our motivating questions comes from single cell RNA sequencing data.

The idea is something like the following: Suppose we start out with a collection of cells of various types (some stem cells, some specialized cells, etc.). As time progresses, maybe some of the stem cells specialize, or some of the specialized cells change further. We want to understand how the distribution of cell types in the sample evolves over time. In order to do this, we want to observe the distribution of RNA in the cells in our sample at various points in time. However, there is a problem: The measurement process is necessarily destructive. In order to find out what the distribution of RNA inside a given cell is, we have to lyse the cell, thus killing it and preventing us from taking a measurement of it in the future. What can we do instead?

One option is to try and get a ton of data from starting configurations that we think should be similar (possibly with variations in how far along they’ve evolved in time), let them all sit for a bit, and then measure each of them. For example, we could take tissue samples from a bunch of cloned mouse embryos, measure all the RNA present in the cells from each embryo, and try and plot the distribution for each one. Due to experimental constraints, it might not be feasible to determine a priori which embryos are farther along in the development cycle at the time of measurement, so this is something we’d want to be able to figure out on our own.

To model this mathematically, we can represent the RNA distributions from each of our embryo samples as probability measures. In this way, the data from each embryo (which might consist of a complicated discrete measure representing each of the RNA reads we get from that embryo) ends up looking like a single point in Wasserstein space. (See figure 1 on page 3 of our paper for an illustration.) Since Wasserstein space is a geodesic metric space, we can then apply the results of our paper to say things about consistency and numerical approaches for recovering the proper time ordering.

What we did: We analyzed the principal curves problem in the general context of geodesic metric spaces, so that we could develop results that apply not only to the “simple” case of data in ${\mathbb{R}}^d$, but also to e.g. measure-valued data as in the mouse embryo example above.

Why we might care: The principal curve methods we introduced give an alternative to previous methods for computing time-ordering (called the seriation problem); namely, spectral seriation methods. See our discussion in Appendix E for details.

@article{Warren2025May,
  author = {Warren, Andrew and Afanassiev, Anton and Kobayashi, Forest and Kim, Young-Heon and Schiebinger, Geoffrey},
  title = {{Principal Curves In Metric Spaces And The Space Of Probability Measures}},
  journal = {ArXiv e-prints},
  year = {2025},
  month = may,
  eprint = {2505.04168},
  doi = {10.48550/arXiv.2505.04168}
}

Copy to Clipboard

Given $m<n$, we consider the problem of "best" approximating an $n\text{-d}$ probability measure $\rho$ via an $m\text{-d}$ measure $\nu$ such that $\mathrm{supp}\nu$ has bounded total "complexity." When $\rho$ is concentrated near an $m\text{-d}$ set we may interpret this as a \emph{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 $\rho$ via the Monge-Kantorovich (also called \emph{Wasserstein}) $p$-cost ${\mathbb{W}}_p^p(\rho ,\nu )$, and constrain the complexity by requiring $\mathrm{supp}\nu$ to be coverable by an $f:{\mathbb{R}}^m\to {\mathbb{R}}^n$ whose $W^{k,p}$ Sobolev norm is bounded by $\ell \ge 0$. This allows us to reformulate the problem as minimizing a functional ${\mathcal{J}}_p(f)$ under the Sobolev "budget" $\ell$. This problem is closely related to (but distinct from) \emph{principal curves with length constraints} when $m=1,k=1$ and an unsupervised analogue of \emph{smoothing splines} when $k>1$. New challenges arise from the higher-order differentiability condition.

We study the "gradient" of ${\mathcal{J}}_p$, which is given by a certain vector field that we call the {\em 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.

Less-technical abstract: Essentially, we consider the following question: Given an $n$-dimensional shape $\rho$, what’s the “most efficient” way to approximate it via a lower-dimensional $m$-d shape? Essentially, this is a principal manifold problem (see the summary of principal curves I gave for the “Principal curves in metric spaces and the space of probability measures” paper for an explanation of the curve case). For our context we consider the case in which the “complexity” of the manifold is constrained not only by its $m$-area, but also by things like the first and second derivatives, etc. of the paramerization. This is important because the $m$-area turns out to not be a good constraint when $m>1$; see the discussion in the second paragraph of page 4 of our preprint.

Anyways, it turns out this problem can serve as a model for certain generative machine learning problems. Very loosely, this makes some intuitive sense: If you think about feeding in a prompt to e.g. an image generation tool, you’re essentially giving a relatively “low-dimensional” input (a short string of text characters) and trying to get out a very “high-dimensional” output (an image). With this analogy, we are able to introduce a novel interpretation for the role regularization plays in improving training of certain generative networks. The idea is that it’s not just “avoidance of overfitting”—regularization can encourage the model to stick to parameter ranges that yield less extreme gradients, and thus better expressability within the model class.

Motivating example: Basically, imagine tying a balloon animal, or folding origami. In those cases, we start with plain 1-d/2-d objects (respectively, cylindrical balloons and sheets of paper), and want to “twist them up” in just the right way so as to approximate a familiar 3-d shape. Here, the material properties of the balloon/sheet of paper are important: Balloons can only be twisted so many times before popping, and paper famously can’t be folded too many times before becoming unworkable. These sorts of material limitations can be captured via restrictions on the smoothness of our approximating $m$-manifolds, and this is one of the reasons we chose the Sobolev norm as our complexity constraint.

There is a lot more to say on this paper, but it’s hard to capture all of the ideas in a summary box while remaining concise. We tried to make the introduction intuitive and thorough, so it might be a good idea to read that. Alternatively, see also the explanatory material in my PhD thesis, which contains this paper as one of the parts.

@article{Kobayashi2024Sep,
author = {Kobayashi, Forest and Hayase, Jonathan and Kim, Young-Heon},
title = {{Monge-Kantorovich Fitting With Sobolev Budgets}},
journal = {ArXiv e-prints},
year = {2024},
month = sep,
eprint = {2409.16541},
doi = {10.48550/arXiv.2409.16541}
}

Copy to Clipboard

Given a uniformly convergent sequence of ambient isotopies $({\mathcal{H}}_n{)}_{n\in \mathbb{N}}$, bijectivity of the limit function ${\mathcal{H}}_{\mathrm{\infty }}$ together with a minor compactness condition guarantees that ${\mathcal{H}}_{\mathrm{\infty }}$ is also an ambient isotopy. By offloading the uniform convergence hypothesis to a more diagrammatic condition, we obtain sufficient conditions for performing countably-many Reidemeister moves. We use this to construct examples of tame knots with countably-many crossings and discuss what distinguishes these from similar-looking wild curves.

Q: “Why hasn’t this been submitted to a journal yet?”

This project something I wrote based on my undergrad thesis. I have been meaning to go back and get it “submission-ready” for a while now, but that fell by the wayside when I started getting my PhD research up and running (I’m in a totally different field now).

I’m also slightly paranoid that the results are known already (though I was more or less unable to find a reference when I did my literature search back in 2020). It seems like something that should be folklore. My undergraduate advisors didn’t know of existing work in this direction, but then again, neither of them had worked with wild knots before.

What’s in the paper?

The executive summary is that the paper addresses certain cases where you can vs. can’t perform countably-many Reidemeister moves.

As motivation, I present two different curves whose diagrams both look like they “should” be unknots. However, only one of them is (this can be shown using a sort of “invariant” for tame knots).

This is strange, because it really looks like you should be able to unknot them both using Reidemeister moves. The problem is subtle, but maybe obvious once you see it. Essentially, for the wild knot, when you perform all the Reidemeister moves you end up “dragging” points in the ambient space along in such a way that as you undo the crossings you pull more and more points of the ambient space down toward a wild point. In the limit, you end up losing bijectivity of your ambient isotopy because at least a countable sequence of points from the ambient space get mapped to the wild point.

In the end, I state a conjecture about how for a certain class of diagrams, adding a fourth Reidemeister move that was suggested by Kye Shi might recover “diagrams equivalent by moves $⟺$ ambient isotopic” in the case where countably-many moves are performed.

It would be cool to see further work on this, since as far as I can tell the theory of wild knots has gone largely untouched for the past half-century-or-more. It would also be nice to know if there are some obscure references for this sort of thing that I didn’t find during my literature review.

@article{Kobayashi2021Jan,
author = {Kobayashi, Forest},
title = {{Uniform Convergence and Knot Equivalence}},
journal = {ArXiv e-prints},
year = {2021},
month = jan,
eprint = {2101.04106},
doi = {10.48550/arXiv.2101.04106}
}

Copy to Clipboard

We introduce Kaestner brackets, a generalization of biquandle brackets to the case of parity biquandles. This infinite set of quantum enhancements of the biquandle counting invariant for oriented virtual knots and links includes the classical quantum invariants, the quandle and biquandle 2-cocycle invariants and the classical biquandle brackets as special cases, coinciding with them for oriented classical knots and links but defining generally stronger invariants for oriented virtual knots and links. We provide examples to illustrate the computation of the new invariant and to show that it is stronger than the classical biquandle bracket invariant for virtual knots.

@article{Kobayashi2020Aug,
author = {Kobayashi, Forest and Nelson, Sam},
title = {{Kaestner brackets}},
journal = {Topology and its Applications},
volume = {282},
pages = {107324},
year = {2020},
month = aug,
issn = {0166-8641},
publisher = {North-Holland},
doi = {10.1016/j.topol.2020.107324},
url = {https://www.sciencedirect.com/science/article/pii/S0166864120302674},
keywords = {Biquandle brackets, Quantum enhancements, Skein invariants, Parity biquandles, Virtual knots and links}
}

Copy to Clipboard

We study two variational problems encoding the idea of optimally approximating a probability measure $\rho$ via a lower-dimensional set $\mathrm{\Sigma }$ of bounded complexity.

In both problems we quantify the performance of $\mathrm{\Sigma }$ in approximating $\rho$ via the average of the $p$\textsuperscript{th}-power of the distance to $\mathrm{\Sigma }$, ${\mathbb{E}}_{\omega \sim \rho }[d^p(\omega ,\mathrm{\Sigma })]$. This yields an optimal transport (OT) interpretation in terms of minimizing the \emph{Monge-Kantorovich $p$-cost} (also called the \emph{Wasserstein $p$-cost}) over measures $\nu$ supported on $\mathrm{\Sigma }$. This perspective is essential in framing some of the applications of our work. However, for the theory, it turns out that we can eschew the language of OT in favor of more geometric perspectives.

The two problems differ in the way we quantify the ``complexity'' of the approximating sets. In the first problem (Part I) we consider a class of constraints defined in terms of parametrizations $f$ of $\mathrm{\Sigma }$. The particular class we choose is the set of $W^{k,q}({\mathbb{R}}^m;{\mathbb{R}}^n)$ Sobolev norms, where $kq>m$ and $n>m$. We build up general theory with these assumptions plus a few technical hypotheses. The generality of the framework allows us to make connections to manifold learning problems with noisy data and certain generative machine learning problems with regularization.

One of the key concepts we develop along the way is the ``gradient'' of ${\mathbb{E}}_{\omega \sim \rho }[d^p(\omega ,\mathrm{\Sigma })]$; it has the form of a vector field that we call the \emph{barycenter field}. We use this to develop nontrivial numerical methods for simulating the problem. The barycenter field does not rely on the Sobolev structure, so we can use it in studying the second problem as well.

In the second problem (Part II) we restrict ourselves to $(m=1)$-dimensional approximations $\mathrm{\Sigma }$ and use a fully parametrization-independent constraint, the Hausdorff 1-measure ${\mathcal{H}}^1(\mathrm{\Sigma })$. This yields optimizers with richer topological structure than those of the Sobolev problem. Via analysis of the barycenter field, we are able to mostly resolve an open problem regarding the topological characterization of optimizers, proving that for general target dimension $n\ge 2$ and objective exponent $p\in \{2\}\cup (\frac{3+\sqrt{5}}{2},\mathrm{\infty })$ optimizers are finite binary trees. We expect the result also holds for $p\in (2,\frac{3+\sqrt{5}}{2}]$ but were unable to show it with our methods.

Lay summary (page iii; equiv. 4 of 252): The ideas in this thesis are, roughly, a mathematical version of balloon modeling. In tying a balloon model, one begins with a rather uniform, featureless object: a cylindrical balloon. But, by twisting it in just the right ways, we can represent complicated 3-d objects: a swan, a dog, a flower, or a sword! Naturally, there is a limit to the balloon’s expressiveness: Add one too many fancy twists and it could pop. Judiciousness is essential; one must select only the most important features to represent (e.g. the ears/tail of the dog, or the petals of the flower). Origami works similarly, but using a 2-d object—a sheet of paper—rather than a 1-d balloon.

Analogously, this thesis considers a family of problems in approximating complicated n-d shapes by twisting up contiguous m-d ones. The goal is to represent the object’s essential features while remaining as simple as possible

Additional content over constituent papers: This is described in the preface on page iv (5 of 252). The main highlight is the much more thorough treatment of the numerical routines for the Sobolev principal manifolds. However, there are also some important additions over the “Monge-Kantorovich Fitting With Sobolev Budgets” paper; namely, more explanatory text and diagrams, a more thorough explanation of the differences between the soft penalty and hard constraint formulations (page 24-28 == 48 of 252 to 52 of 252), expanded discussion of nonuniqueness of optimizers (Counterexample 3.2.5), a detailed explanation of a certain pathological ridge set (Example 3.3.1), some discussion of the second variation in $\mathrm{\S }3.3.5$, and various meta-organizational material.

@phdthesis{Kobayashi_2025,
series={Electronic Theses and Dissertations (ETDs) 2008+},
title={Optimal transport approximation of measures via lower-dimensional structures : principal manifolds and the average distance problem},
url={https://open.library.ubc.ca/collections/ubctheses/24/items/1.0449621},
DOI={10.14288/1.0449621},
school={University of British Columbia},
author={Kobayashi, Forest},
year={2025},
collection={Electronic Theses and Dissertations (ETDs) 2008+}
}

Copy to Clipboard