Elementary topology and machine learning

The machine learning bubble may be overinflated, but it is not about to burst. Interdisciplinary research in this field is grounded in sound theory and has numerous empirical breakthroughs to show for. As it finds more and more applications and concentrates public research funding, many of us are still wondering: how can mathematics contribute?
Case study of an interaction between elementary topology and machine learning’s binary classification problem. Following classical theorems, we obtain a topologically accurate solution.

Correction: It should be \sup_{i,j}| E_{i,j}^n - (k+1)^2 \int_{R_{i,j}^n} f | = o(1/n) and k=k(n) grow correspondingly slower with n.

PDF note here.


Short proof: Critical points in invariant domains

Short proof: Critical points in invariant domains

When mixing coffee in your favorite mug, at every instant a particule is staying still.

Let f : \mathbb{R}^k \rightarrow \mathbb{R}^k be a {}\mathcal{C}^1 vector field and denote by \phi(x): t \mapsto \phi_t(x) its stream. That is, \phi_0(x) = x and \frac{d}{dt}\phi_t(x) = f(\phi_t(x)). A domain D \subset \mathbb{R}^k is said to be invariant (under the stream of f) if \phi_t(x) \in D for all x \in D and t \geq 0. The curve \{  \phi_t(x) \,|\, t \in \mathbb{R} \} is said to be a closed orbit of f if there exists T > 0 such that \phi_0(x) = \phi_T(x).

If D \subset \mathbb{R}^k is invariant and diffeomorphic to a closed ball of \mathbb{R}^k, then f has a zero in D.

If k=2, then any closed orbit of f encloses a zero of f.

Proof of the theorem.
Suppose that \|f(x)\| > \alpha > 0 for all x \in D and let M = \sup_{x \in D} \|f(x)\|. Since f is uniformly continuous on D, there exists \delta > 0 such that \|x-y\| < \delta implies \|f(x) - f(y)\| < \alpha. Also, by Brouwer’s fixed point theorem, there exists x_0 \in D such that \phi_{\delta / M}(x_0) = x_0. This yields a closed orbit \Gamma = \{\phi_t(x_0) \,|\, t \geq 0\} such that any two points on \Gamma are at distance at most \delta from each other. Since \Gamma is closed, there must exist a,b \in \Gamma such that \langle f(a), f(b) \rangle \leq 0. Hence we find that \|f(a) - f(b)\| > \|f(a)\| > \alpha, even though \|a-b\| < \delta. This is impossible. Thus \|f\| is not bounded away from zero and f must have a zero in the compact D. \Box

Proof of the corollary.
When k=2, the Jordan-Brouwer theorem implies that closed orbits separate the plane in two connected components, one of which is bounded. Schoenflies’ theorem, strengthening the above, ensures that the union of bounded component with the closed orbit is diffeomorphic to the closed disk. Invariance follows from the unicity of the solution to initial value problems when f is \mathcal{C}^1. \Box

This can be generalized as follows. For the sake of mixing things up, we state the result in topological terms.

Theorem (Particular case of the Poincaré-Hopf theorem).
Let M be a compact submanifold of \mathbb{R}^k with non-zero Euler characteristic \chi(M), and let \phi : [0,1] \times M \rightarrow M : (t,x) \mapsto \phi_t(x) be a smooth  isotopy. Then for all t \in [0,1], there exists distinct points x_1, x_2, \dots x_{|\chi(M)|} such that

\frac{d}{dt}\phi_t(x_i) = 0.

Constructive approximation of compact hypersurfaces

PDF text.

Let M \subset \mathbb{R}^k be a compact manifold of codimension 1. We show that M can be well approximated by a part of an algebraic manifold.

Theorem 1.
For all \varepsilon > 0, there exists c > 0 and a polynomial function P defined on \mathbb{R}^k such that N := P^{-1}(0) \cap (-c,c)^k is diffeomorphic to M and

\sup_{x \in N} \inf_{y \in M} \|x - y\| < \varepsilon.

This was proved by Seifert in a 1936 german language paper. It was later generalized to the Nash-Tognoli theorem which implies that non-singular real algebraic sets have precisely the same topological invariants as compact manifolds [1].

Here, however, our motivations are more elementary and practical. Our proof of theorem 1 points towards constructive approximation processes and shows the separability of the space of all compact hypersurfaces, under an appropriate topology. This is relevant in statistics and computer graphics, for smooth hypersurface regression and reconstruction. Growing sequences of finite dimensional search spaces of smooth manifolds are required in these applications.

In preparation for our proof, in section 2, we also discuss the Jordan-Brouwer theorem, the orientability of M and that M = f^{-1}(0) for some function f having regular value 0. We show that these three facts are essentially equivalent, in the sense that any one can be quite easily obtained from another.

Continue reading

Constructive approximation on compact manifolds

I presented this (pdf, in french) in a short talk for a differential topology course.

I also dabbled with (pdf, in french) the approximation of compact hypersurfaces. I wasn’t able to get a constructive result in time, so I left it as a very rough draft. [I posted a much improved follow up in April.] In the document, I sketch a proof of the following.

Theorem. Let M be a compact hypersuface of \mathbb{R}^n. There exists a sequence of polynomials \{P_n\} defined on a compact of \mathbb{R}^n such that for n sufficiently large, P_n^{-1}(0) is a hypersurface and

\text{dist}(P_n^{-1}(0), M) \rightarrow 0.

Tubular neighborhoods

A complete proof of the tubular neighborhood theorem for submanifolds of euclidean space is presented. I was unable to find it in the litterature.

Let me introduce some notations. A \mathcal{C}^l submanifold of dimension m of \mathbb{R}^k is a subset M that is locally \mathcal{C}^l-diffeomorphic to open balls of \mathbb{R}^m. Similarily, a \mathcal{C}^l manifold with boundary is locally diffeomorphic to open balls of the half space \mathbb{H}^k = \{(x_1, \dots, x_m)\in \mathbb{R}^m | x_m \geq 0\}.
If f : M \rightarrow N is a differentiable map between manifolds, we denote by df_x: T_x M \rightarrow T_{f(x)} N the differential of f at x. Each tangent space T_x M has an orthogonal complement N_x M in \mathbb{R}^k; the normal bundle of M is N(M) = \{(x, v) \in \mathbb{R}^{2k} | x \in M,\, v \in N_x M\}. In the following, we assume M is compact.

Given \varepsilon > 0, we let V_\varepsilon = \{(x, v) \in N(M) \,|\, |v| \le \varepsilon\} and P_\varepsilon = \{y \in \mathbb{R}^k | d(y, M) \le \varepsilon \}, where d is the euclidean distance. The set V_\varepsilon is an \varepsilon-neighborhood of the cross-section M \times \{0\} in N(M), and P_\varepsilon is a tubular neighborhood of M in \mathbb{R}^k. We will prove the following theorem.

Tubular neighborhood theorem. Let M be a compact submanifold of \mathbb{R}^k, without boundary. For \varepsilon > 0 sufficiently small, V_\varepsilon and P_\varepsilon are manifolds, diffeomorphic under the map F : V_\varepsilon \rightarrow P_\varepsilon : (x, v) \mapsto x+v.

Corollary 1. If \varepsilon > 0 is sufficiently small, then for each w \in P_\varepsilon there exists an unique closest point to w on M.

Note, however, that this corollary may not hold when M is only a \mathcal{C}^1 manifold. We will require M to be at least \mathcal{C}^2. The proof will make clear why this is necessary, but I also present a counter-example.

Continue reading