\(p(x)=\sum_{i=1}^N \pi_x(x_i) x_i\): expectation of \(x_i\) over the finite probability distribution \(\pi_x(x_i)=a_i\exp(-\lVert x-x_i\rVert^2/2h^2)/f(x)\).
Statement of the theorem
Here is an image of the corresponding sublevel sets of \(\alpha^{-1}(-\infty,a]\) for a particular choice of \(h\) and \(a\), shown in dark gray:
Looking at this image, it appears that the dark gray region is contained in the density sublevel set, but is condensed somehow. Moreover, it appears to be topologically
equivalent to the original. In fact, this is true, and is proved in our theorem:
In the paper, we proved
Theorem We have
\(\alpha\) is a continuous function on the domain on which it is finite, which is the interior of the convex hull of the point cloud \(conv(D)\).
\(\alpha\) is the convex transform of \(F\), meaning \(F(x)=\inf_y \lVert x-y\rVert/2h^2+\alpha(y)\)
The map \(p\) is a homeomorphism of \(\mathbb{R}^d\) onto \(conv(D)\).
For each \(a\in \mathbb{R}\), the inclusion map of \(\alpha^{-1}(-\infty,a]\) into \(F^{-1} (-\infty,a]\) induces a homotopy equivalence
whose inverse is given by \(p\)
Notice that part 2 can be restated as writing the sublevel sets of \(F\) as the union of a covering by closed discs,
\begin{equation}
\label{eq:union}
F^{-1} (-\infty,a]=\bigcup_{y \in \alpha^{-1} (-\infty,a]} B\left(y; \sqrt{2h^2 (a-\alpha(y))}\right),
\end{equation}
where \(B(y;r)\) is the ball of radius \(r\) centered at \(y\). By selecting a finite subcover and taking the nerve, we obtain a family of
simplicial complexes filtered by density, which in fact can be computed as weighted alpha complexes.
The fact that \(\alpha^{-1}(-\infty,a]\) is contained in the convex hull is important for obtaining manageable sized complexes
from point clouds embedded in higher dimensions.
Explanation of the proof
Parts 1-3 are straightforward to check once they have been written down.
To check 2, one shows that \(F(x)+\lVert x-y\rVert^2/2h^2\) is a convex function for any \(y\),
which can be done by checking it is convex along any line. We may then apply the Fenchel-Moreau theorem,
which says that applying the Legendre transform twice recovers the original function.
The function \(p(x)\) is simply the one that maps \(x\) to the unique point
\(y\) which realizes the infimum in part 2. It is straightforward to see that it is a continuous bijection, by checking
that its Jacobian matrix is positive definite. Part 1 can be seen by taking the supremum defining \(\alpha\) along some particular rays. We note that these type of
calculations are the same sort that appear in a more general context in optimal transport. For a reference, see Cedric Villani's well-known
book.
The final statement about the homotopy equivalence has a reasonable argument as well, but it requires one trick: the restricted map
\(p:F^{-1} (-\infty,a]\rightarrow \alpha^{-1}(-\infty,a]\)
is not surjective (nor equal to the identity map on
\(\alpha^{-1}(-\infty,a]\)), ruling out a potential proof strategy which that would involve showing that is a deformation retract.
Instead, we take advantage of the statement that \(p\) is a homeomorphism, and produce a retract
of \(r:p^{-1} \alpha^{-1} (-\infty,a]\rightarrow F^{-1} (-\infty,a]\).
Here is a picture of the two regions:
The reason is turns out to be easier is that evaluating \(\alpha\) directly is not easy, but its composition with \(p\) has a closed formula
\begin{equation}
\label{eq:alphaofp}
\alpha(p(x))= F(x)-\lVert x-p(y)\rVert^2/2h^2
\end{equation}
by the statement that \(p(x)\) is the unique value \(y\) that attains the infimum in item 2. In fact, while the lightest gray region in the above
figure is straightforward to determine using \eqref{eq:alphaofp}, the illustration of the dark gray region from the previous section was
far more expensive to generate, and was computed using the
Linear time Legendre transform.
For this reason, you may have actually noticed some warping of the dark gray region near the boundary, where it is not contained in the convex hull.
This is not a contradiction of item 1 of the Theorem, but rather is due to
taking the
Legendre transform just over the image domain instead of all of \(\mathbb{R}^2\).
Definition of the deformation retract
The retract is given by defining \(r(x)\) to be the point on the ball \(B\left(y;\sqrt{2h^2 (a-\alpha(y))}\right)\) centered at \(y=p(x)\), which is closest to \(x\).
In particular, if \(x\) is in that ball, we would have \(r(x)=x\).
Then we have that
The radius is non-imaginary when \(x\in p^{-1} \alpha^{-1} (-\infty,a]\), which is precisely the light gray region, the domain of definition of \(r\).
By equation \eqref{eq:union} and the fact that \(p\) is bijective, the image \(r(x)\) is in the sublevel set \(F^{-1} (-\infty,a]\).
If \(x\in F^{-1} (-\infty,a]\), then it is already contained in the ball defining \(r(x)\). Therefore, we have \(r(x)=x\) on that region, as is required for \(r\) to be a retract.
Below is an animation which illustrates these statements, which is proved in Lemma 3 of the paper.
The blue open circle is a point \(x\) moving along a random
line, whereas the red point is image \(y=p(x)\), which lives in \(\alpha^{-1} (-\infty,a]\) shown in dark gray.
The retract \(r\) is shown by a blue arrow pointing to the nearest point in the ball,
which is defined whenever \(x\) is in the domain (light gray through dark gray). We have that
\(r(x)=x\) whenever \(x\in F^{-1} (-\infty,a]\), corresponding to medium gray.
