Estimation of Conformal Metrics

Let us now describe formally this construction. The polygonal approximation of $D_{M,f}$ is defined as the metric of an appropriate weighted graph on a point cloud $X$.

Ball graphs are more convenient to study whereas NN graphs are more practical, see Section 4.2. We define the polygonal metric in both contexts. The graph used is equipped with a weight function to approximate the conformal length of its edges.

The weight function $w_{f,q}$ is meant to approximate the conformal distance between the endpoints of an edge. Proposition 3.3 below shows that it is indeed the case when the endpoints are close, which is the reason why graphs with small edges are used. Recall that we have assumed without loss of generality that $f$ is defined over the whole space, allowing its evaluation outside $M$ when $q\ne 2$. As $q$ grows, the weight $w_{f,q}$ becomes more accurate and converges to the weight with infinite resolution $w_{f,\mathrm{\infty }}$, the latter being exactly the conformal length of the straight path. However, the computational cost is linear with $q$ and there is no closed-form formula for $w_{f,\mathrm{\infty }}$ in general. On the other hand,

is the simplest choice for the weights and may be more suitable if evaluating $f$ is possible only at points in $X$. Note that the weight $w_{f,q}$ is the optimal approximation of $w_{f,\mathrm{\infty }}$ using only $q$ samples of the Lipschitz function $f$. Under stronger assumptions on $f$ such as ${𝒞}^k$ regularity, other definitions would be better suited.

Proposition 3.3 shows that the conformal metric $D_{M,f}$ may be approximated locally by the weights $w_{f,q}$. Note that for fixed resolution $q$ in the $r$-ball graph, the distortion between the weights and the conformal distances is linear in $r$. However, by choosing $q$ to be inversely proportional to $r$, the distortion becomes quadratic in $r$. The proof for Proposition 3.3 is provided in [17, Appendix B.3]. We now introduce the polygonal approximation of the conformal metric as the metric of the weighted graph built on $X$.

The choice of a ball graph or a NN graph along with the threshold $r$ or $k$ and the resolution $q$ of the weights are left implicit when writing ${\widehat{D}}_{X,f}$ to avoid heavy notations. Note that when the endpoints $x$ and $y$ do not belong to the point cloud, the distance ${\widehat{D}}_{X,f}(x,y)$ is computed by adding them to the graph. As a result, ${\widehat{D}}_{X,f}$ induces a distance over $X$ but not over $M$. Indeed, when considering endpoints outside $X$, ${\widehat{D}}_{X,f}$ may not satisfy the triangular inequality due to the set of possible paths depending on the endpoints.

To evaluate how efficient is the approximation of a metric, the error between the true distances and their estimation may be measured using either of the multiplicative loss functions

In the case where $D^{\prime }$ takes infinite values – which happens for instance when $D^{\prime }$ is the metric of a non-connected graph – we let ${\mathrm{\ell }}_{\mathrm{\infty },M}(D^{\prime },D)=1$ and $l_{\mathrm{\infty },M}(D^{\prime }|D)=+\mathrm{\infty }$. The inequality

holds in general, so that both losses are equivalent. The loss ${\mathrm{\ell }}_{\mathrm{\infty },M}$ is however easier to manipulate in some situations as it is symmetric and upper bounded by $1$. Thanks to the regularity of geodesics stated by Proposition 2.4 and the local approximation of the conformal metric by the weights $w_{f,q}$ stated by Proposition 3.3, we are able to show that the conformal metric $D_{M,f}$ is approximated by the polygonal metric from Definition 3.4 using the $r$-ball graph.

Let us describe the reasoning behind Theorem 3.5. Given $x\ne y\in X$, paths in $G_r(X)$ cannot create significant shortcuts outside $M$ as $r\le {\tau }_{M,f}$. This is illustrated by Proposition 3.3 from which it can be deduced that

and, assuming that $\Vert x-y\Vert \le r$,

As for when $\Vert x-y\Vert >r$, consider a geodesic $\gamma \in {\mathrm{\Gamma }}_{M,f}^{\star }(x,y)$. Decompose $\gamma$ into sections of length at most $r-2d_{\text{H}}(M,X)$ and for each intermediate point select a point in $X$ at distance at most $d_{\text{H}}(M,X)$. This process draws a polygonal path in $G_r(X\cup \{x,y\})$ as it uses edges of length at most $r$. Summing the approximation error from Proposition 3.3 between each edge of this path and the corresponding section of $\gamma$ eventually yields the upper bound

when $\Vert x-y\Vert >r$ and where $c_1$ and $c_2$ are universal constants. The positive reach of $\gamma$ and Lemma 2.5 play a crucial role in obtaining terms of order $d_{\text{H}}(M,X)/{𝒯}_{M,f}$ and $d_{\text{H}}{(M,X)}^2/r^2$ instead of $d_{\text{H}}(M,X)/r$. Together, Equations 11, 12, and 13 eventually imply Equation 10. The details of this reasoning are provided in [17, Appendix B.4]. The upper bound in Equation 10 is made proportional to $d_{\text{H}}(M,X)$ by setting

In the case of the induced metric with $f=1$, the first term in the right-hand side of Equation 10 disappears, and the error is of order $r^2/{\tau }_M^2+d_{\text{H}}{(M,X)}^2/r^2$ similarly to the one obtained in [3]. In the general conformal case, we keep this magnitude of error by setting the resolution $q$ to be at least of order $1/r$. If it is not possible to evaluate $f$ outside the point cloud $X$, setting $q=2$ instead yields an error of order $r/{𝒯}_{M,f}+d_{\text{H}}{(M,X)}^2/r^2$ which is slightly worse. A similar upper bound was achieved in [2] for the induced metric and the term linear in $r$ was due to the geodesically smooth assumption used in the paper being slightly weaker than a positive reach assumption. In particular, the latter allows for an efficient local estimation in the form of Equation 12. The main takeaway of Theorem 3.5 is that the crucial assumption to achieve an approximation error proportional to $d_{\text{H}}(M,X)$ is the positive reach. In particular, the domain need not be ${𝒞}^2$, or even a submanifold.

In general, $f$ may not be known and needs to be estimated from the data. The polygonal metric ${\widehat{D}}_{X,g}$ from Definition 3.4 can be defined for any function $g:{ℝ}^N\to {ℝ}_{+}^{\ast }$ without the need of Lipschitz and lower bound assumptions. Then, the approximation error between ${\widehat{D}}_{X,g}$ and $D_{M,f}$ is upper bounded by the sum of the error w.r.t. the conformal factor and the error w.r.t. the domain.

The proof of Lemma 3.6 consists in straightforward computations and is deferred to [17, Appendix B.5]. As a consequence, in the context of estimation of the domain $M$ by a point cloud $X_n$ as in Section 4 and of the conformal factor $f$ by a function $f_n:{ℝ}^N\to {ℝ}_{+}$, the rate of convergence of ${\widehat{D}}_{X_n,f_n}$ towards $D_{M,f}$ is the slowest rate of convergence among that of ${\widehat{D}}_{X_n,f}$ towards $D_{M,f}$ and that of $f_n$ towards $f$. Recall that $f_n$ is not required to satisfy the Lipschitz and lower bounded assumptions for the polygonal metric ${\widehat{D}}_{X_n,f_n}$ to be defined and for Lemma 3.6 to hold. It may also be defined only over $X_n$ if the resolution is set to $q=2$.

We first discuss the case of a ball graph estimator. It is known that if $\mu$ is $d$-standard, then $d_{\text{H}}(M,X_n)$ is of order $L_{\mu }{(\log (n)/n)}^{1/d}$ at most, see [17, Appendix A.2]. This convergence combined with Theorem 3.5 allows to derive convergence rates for the estimation of $D_{M,f}$.

The first case in Theorem 4.2 includes $q=\mathrm{\infty }$. There is no use setting $q$ to be greater than the indicated threshold of order ${𝒯}_{M,f}/r$, as the term in the upper bound depending on $q$ becomes negligible past this threshold. Note that the optimal choice for $r$ and $q$ requires the knowledge of $L_{\mu }$, ${𝒯}_{M,f}$ and most importantly $d$. Theorem 4.2 is stated with these choices of parameters to highlight the optimal theoretical dependency in these constants. For practical purposes, the knowledge of $L_{\mu }$ and ${𝒯}_{M,f}$ is not actually needed as, in general, any choice of $r\asymp {(\log (n)/n)}^{1/2d}$ and $q\gtrsim 1/r$ yields a convergence rate of ${(\log (n)/n)}^{1/d}$. Likewise, any choice of $r\asymp {(\log (n)/n)}^{2/3d}$ and $q=2$ yields a convergence rate of ${(\log (n)/n)}^{2/3d}$. It is not possible however to get rid of the dependency in $d$ for the range parameter $r$ without altering the convergence rate. To circumvent this issue, one may use the NN graph instead, for which the optimal choice of the parameter is shown in Section 4.2 to be $k=\sqrt{n}$ which does not depend on $d$. Theorem 4.2 is derived directly from Theorem 3.5 and the convergence of $X_n$ to $M$ in Hausdorff distance. The precise computations are deferred to [17, Appendix C.1]. In the case of the induced metric, the weight function $w_{f,q}$ becomes the Euclidean distance regardless of the resolution and ${𝒯}_{M,f}$ is replaced with ${\tau }_M$.

Recall that in the case of a submanifold of class ${𝒞}^k$ with $k\ge 2$ and dimension $d$, the optimal convergence rate for the estimation of the induced metric is $n^{-k/d}$ [1]. Corollary 4.3 extends the upper bound to any set of positive reach with the convergence rate $n^{-1/d}$.

We now treat the case of a NN graph estimator, by observing that for adequate choice of $r$ and $k$, the $r$-ball graph and $k$-NN graph are similar. Indeed, assuming that $\mu$ is $d$-Ahlfors regular, a ball of radius $r$ is expected to contain between $c_{\mu }n{r}^d$ and $C_{\mu }n{r}^d$ points from $X_n$.

Proposition 4.4 shows that if $r$ and $k$ are chosen such that $k\asymp n{r}^d$, the $k$-NN graph and the $r$-ball graph are very similar with high probability. This result stems from a common intuition and a detailed proof is provided in [17, Appendix A.3] for completeness. Theorem 4.2 is then extended to $k$-NN graphs by choosing $k\asymp \sqrt{n\log (n)}$, which does not depend on $d$.

Notice that in Theorem 4.5 the loss is over $X_n$ instead of $M$ like in Theorem 4.2. The same result could be stated over $M$, although the proof would be more tedious and is therefore omitted here. Recall that no knowledge on either $d$, $c_{\mu }$, $C_{\mu }$, ${\tau }_M$, $\kappa$ or $f_{\min }$ is necessary to compute the estimator, so that it can be used in practice. Setting the resolution $q$ to be ${(n/\log (n))}^{1/2d}$ would be sufficient to achieve the same upper bound, however this choice requires the knowledge of $d$. On the other hand, when setting the resolution to $q=2$ the optimal choice of $k$ can be shown similarly to be $k=n^{1/3}\log {(n)}^{2/3}$ and to yield a convergence rate of order ${(\log (n)/n)}^{2/3d}$. Theorem 4.5 is a direct consequence of Theorems 4.2 and 4.4 and the precise computations are provided in [17, Appendix C.2]. Regarding the case of the induced metric, the same statement as in Corollary 4.3 holds for NN graphs. Namely, the estimator ${\widehat{D}}_{X_n,1}$ defined over the $k$-NN graph with $k=\lceil \sqrt{n\log (n)}\rceil$ converges to $D_M$ at rate ${(\log (n)/n)}^{1/d}$.

Let us now discuss the algorithmic complexity of the $k$-NN estimator with resolution $q$. In general, building the $k$-NN graph over a point cloud $X$ of size $n$ is done in $𝒪(n^{2}N)$ time when the ambient dimension $N$ is large. Now, consider two points $x,y\in {ℝ}^N$ and assume that $f$ can be evaluated at any point with cost $c_f$. Computing the edges of the graph ${𝒢}_k(X\cup \{x,y\})$ takes $𝒪(nkq{c}_f)$ time as the amount of edges in the graph is $𝒪(nk)$ and the weight of each edge uses $q$ evaluations of $f$. Finally, computing the infimum that defines $D_{X,f}(x,y)$ in Definition 3.4 using Dijkstra’s algorithm takes $𝒪(n\log (n)+nk)$ time. Overall, if $k=\lceil \sqrt{n\log (n)}\rceil$ and $q=\lceil n^{1/4}\rceil$, the time complexity is $𝒪(n^{2}N+n^{7/4}\log {(n)}^{1/2}{c}_f)$.

We now study the worst case performance of any estimator of the induced metric $D_M$.

Notice that Theorem 4.6 only addresses the case of the induced metric. This is not a loss of generality and in fact highlights the fact that the conformal change does not make the problem any harder, as we have established in Section 2 that geodesics have the same regularity as in the case of the induced metric. Given any other function $f$ satisfying the assumptions for a conformal metric, the same lower bound may be obtained with a similar reasoning as what follows, albeit with more technicalities. The rate $n^{-1/(d-1/2)}$ is faster than the rate $n^{1/d}$ obtained in Theorems 4.2 and 4.5, although the difference becomes negligible when $d$ is large. The nature of the minimax convergence rate remains therefore open. Under stronger assumptions on the domain, this question is already solved – see [1] – which we discuss in Section 4.4.

Theorem 4.6 is based on Le Cam’s method [19], for which a statement adapted to our setup is given in [17, Lemma C.1]. The method consists in finding two measures ${\mu }_1$ and ${\mu }_2$ in $ℳ(d,L,\tau )$ that are at most $1/n$ apart in total variation distance and such that the relative difference between $D_{M_1}$ and $D_{M_2}$ is of order at least $n^{-1/(d-1/2)}$.

Consider ${\mu }_1$ the uniform probability on the cube $M_1={[-\alpha L,\alpha L]}^d\times {\{0\}}^{N-d}\subset {ℝ}^N$ where $\alpha >0$. Let and consider $M_2$ the result of removing from $M_1$ its intersection with a ball of radius $\tau$ centered at $(0,t,t,\mathrm{\dots },t)$ for some $t>\alpha L$ such that the ball intersects the edge from $(-\alpha L,\alpha L,\alpha L,\mathrm{\dots },\alpha L)$ to $(\alpha L,\alpha L,\alpha L,\mathrm{\dots },\alpha L)$ at two points $x$ and $y$ that are $2\epsilon$ apart, as pictured in Figure 2. Denote ${\mu }_2$ the uniform probability over $M_2$, which has reach exactly $\tau$ due to the carved area. By choosing $\alpha$ small enough, which depends only on $d$, ${\mu }_1$ and ${\mu }_2$ are $d$-standard with lower constant $L^{-d}$. Then ${\mu }_1$ and ${\mu }_2$ both belong to $ℳ(d,L,\tau )$. The volume of the carved area is of order $\epsilon {({\epsilon }^2)}^{d-1}$ as it spans a length $2\epsilon$ between $x$ and $y$ and a length of order ${\epsilon }^2$ for every other dimension of the cube. This implies that the total variation distance between ${\mu }_1$ and ${\mu }_2$ is of order ${\epsilon }^{2d-1}$. Moreover, The distance from $x$ to $y$ goes from $2\epsilon$ in $M_1$ to $2\tau \arcsin (\epsilon /\tau )$ in $M_2$, following the red arc of radius $\tau$ in Figure 2. This implies that the relative difference between both distances is of order ${\epsilon }^2$. Choosing $\epsilon \asymp n^{-1/2d-1}$ so that the total variation distance is at most $1/n$ eventually yields the desired bound. This reasoning is detailed in [17, Appendix C.3] and the reason why it fails to achieve a bound of order $n^{-1/d}$ is discussed more in depth in the full version [17].

Recall that the minimax convergence rate for the induced metric of a ${𝒞}^k$ manifold of dimension $d$ is $n^{-k/d}$ [1]. The methods that achieve such rates are however not computationally feasible in practice as they rely on manifold reconstruction via non-discrete sets. For instance, the optimal convergence rate in the ${𝒞}^2$ case was achieved by [3] using the tangential Delaunay complex. Precisely, these methods build a $n^{-k/d}$-approximation of the manifold w.r.t. the Hausdorff distance, then state that the induced metric over this reconstruction is an estimation of the original metric with an error proportional to the Hausdorff distance.

In order to get a concrete estimator, one may use such manifold reconstruction, then sample a fine $n^{-k/d}$-net over it which approximates the original domain with the same Hausdorff error. Our work then implies that the polygonal metric over this net would be an estimation of the original metric with minimax optimal error of order $n^{-k/d}$. Such construction would however be very costly as the point cloud size would grow from $n$ to $n^k$.

If $\mu$ is a measure with density $\rho$ w.r.t. the volume measure over a submanifold $M$, the conformal change via $f={\rho }^{-\beta }$ for some parameter $\beta >0$ is sometimes referred to as the Fermat distance due to the parallel with the Fermat principle in optics – that may however be observed with any conformal change. This metric has been applied to various topological data analysis and learning problems, e.g., in [11, 12], as it tends to accentuate features and disparities in the data. Moreover, the metric can be estimated in a simple fashion by using the same overall reasoning as ours but using weights of the form $w(x,y)={\Vert x-y\Vert }^{\alpha }$ where $\alpha >1$ is a parameter depending on $\beta$ and $d$ [13, 14]. However, this kind of estimation does not feature any known convergence rate. Using our estimator instead provides an alternative method with quantitative guarantees, granted that an estimator of the density is available. To this extent, density estimation is a well-studied problem with many propositions in the literature. For instance, [4] provides a kernel density estimator ${\rho }_n$ that converges in $L^p$ norm towards $\rho$ at a rate of $n^{-1/d+1}$ under our assumptions and provided that $M$ is a ${𝒞}^1$ submanifold and that $\rho$ is also ${𝒞}^1$. Under these assumptions, setting $f_n={\rho }_n^{-\beta }$ yields a convergence rate of $n^{-1/d}$ according to Lemma 3.6, at the cost of a more complex computation than the usual discrete Fermat distance studied in [13].

In general, given a parameter $m\in (0,1)$, the distance-to-measure $d_{\mu ,m}:{ℝ}^N\to {ℝ}_{+}$ introduced in [8] is defined for any measure $\mu$ over ${ℝ}^N$. It is $1$-Lipschitz and lower bounded by a positive value as long as $\mu$ has no atom, hence satisfies the assumption for our work. A slightly different setup where paths are allowed to leave the domain under a specific constraint is studied in [18], where it is argued that this metric should behave similarly to the conformal metric associated with the density but with more stability w.r.t. the measure. The distance-to-measure is shown [9] to be estimated from $n$ i.i.d. samples of the underlying measure with convergence rate $n^{-1/2}$, which is faster than $n^{-1/d}$ hence does not impact the convergence speed of the estimator of the conformal metric according to Lemma 3.6.