ADTDA, lecture 1

\(\def\Real{\mathbb{R}}
\)

Refresher on topology

We recall what a topological space is, the notions of homomorphism, homotopy and homotopy equivalence.

Simplicial complexes: abstract; their geometric realizations. Poset of a simplical complex; simplicial complex associated to a poset. Barycentric subdivisions.

Simplicial complexes can be embedded into Euclidean spaces of any dimension exceeding twice the dimension of the complex.

Connecting combinatorial and geometric worlds: if \(f:|K|\to|L|\) is a continuous mapping, we say that \(\phi:K\to L\) is simplical approximation of \(f\) if for any point in \(|K|\), its image is in the simplex whose interior contains \(f(x)\). Simplical approximations are homotopy equivalent to the maps they approximate, and, luckily, they do exist – if one subdivides the domain finely enough (say, by barycentric subdivisions).

Manifolds: charts and atlases. Embeddings (to be discussed later).

We will be using several times the Nerve lemma; perhaps best understood it in the context of diagrams of spaces and their homotopy limits.

Homologies of a relation: given a relation (say, on a pair of finite space), one can construct a pair of simplicial complexes. Dowker’s theorem ensures they match. One can use this to reason about both of the complexes: one example deals with the representation of the terrain via the neuronal activity traces. Other examples include describing the structure of social preferences for a collection of artifacts (Netflix matrix).

Topological inference

Given a sample from a manifold, how we can reconstruct it (or recognize its topology)?

Naive example: a sample is either \((n+1)\)-dimensional unit sphere, or a manifold close to its equator. Can one distinguish these two cases? One can easily see that one needs an exponential in the dimension sample size (essentially, due to measure concentration).

If one is willing to accept this, an algorithm to reconstruct the homotopy type of was offered by Niyogi-Smale-Weinberger: sample a lot of points from a Riemannian manifold \(M\subset\Real^N\) and take some offset, – i.e. union of balls around the sample:
\[
X_\epsilon=\{x\in\Real^N:\mathtt{dist}(x,X)\leq \epsilon\}.
\]

Then one has:

  • If \(\epsilon\lt (7/9)\tau\), where \(\tau\) is the “feature size”, the size of the vicinity of the zero section of the normal bundle on which the exponential map is an immersion, and the sample forms an \(\epsilon/2\)-net in \(M\),  then \(X_\epsilon\) retracts on \(M\) and is therefore homotopy equivalent to it.
  • If the sample size is bigger than
    \[c_1 K\log K+ c_2\log(1/\delta)\]
    where \(K\) is the ratio of the volume of \(M\) over the volume of \(\epsilon\)-ball in \(M\), then the sample will form an  \(\epsilon/2\)-net in \(M\) with probability at least \(1-\delta\).

The proof of the first argument is an elementary geometric computation; the second one is essentially a reformulation of the well-known bounds on covering problem.

References

Refresher on topology: plenty of good books to brush it up:

Projects:

  • Construct Dowker complexes for (a selection of) movies/books your circle of friends are reading.
  • For a planar domain, scatter points and form the nerve complex for the visibility neighborhood. Experiment with Čech complex; estimate probability that a sample of size \(n\) produces a contractible visibility covering.
No comments yet.

Leave a Reply