These are notes from a talk given at the Stanford applied topology
seminar by Gunnar Carlsson from 9 Oct 2009. The main function of this
blog post is to get me an easily accessible point of access for the
ideas in that talk.
Topological coordinatization
The core question we're working with right now is this:
Given a space (point cloud) X, and a (persistent) view of
[tex]H_*(X)[/tex], can we use some map [tex]H_*(X)\to
H_*(Y)[/tex] to generate a map [tex]X\to Y[/tex] inducing that map?
In topology there are ways around to compute spaces of maps directly
from available homological information. The key phrase here is the
Eilenberg-Moore spectral sequence, by which we compute
[tex]H^*(\Omega X)[/tex] using [tex]H^*(X)[/tex]. We note that
[tex]\Omega X = Top_*(S^1,X)[/tex] with the compact open topology.
We fix a field k of coefficients. We can find a spectral sequence that
computes
[tex]Tor_{H^*(X)}(k,k)' \Rightarrow H^*(\Omega X)[/tex]
Variations of this spectral sequence allow us to compute
[tex]H^*(Map(X,Y))[/tex]. A homotopy class of maps thus corresponds to
a cohomology element from [tex]H^*(F(X,Y))[/tex].
Monad approximation
Define
[tex]Sp^2(X) = X \times_{\mathbb Z/2} X[/tex] (unordered pairs)
and similarily unordered tuples
[tex]Sp^n(X) = X^n/\Sigma_n[/tex]
we can get a map, for pointed spaces [tex](X,*)[/tex]
[tex]Sp^n(X) \to Sp^{n+1}(X)[/tex]
[tex](x_1,\dots,x_n)\mapsto(x_1,\dots,x_n,*)[/tex]
In the limit, we get the union [tex]Sp^\infty(X)[/tex].
The Dold-Thom theorem tells us:
[tex]\pi_i(Sp^\infty(X)) = H_i(X)[/tex]
Suppose we are really looking for maps [tex]Z\to Sp^\infty(X,*)
\supseteq X = Sp^1(X)[/tex].
We pick chain complexes [tex]C_*, D_*[/tex]. There is a hom chain
complex [tex]Hom(C_*,D_*)[/tex] consisting of graded maps
[tex]C_*\to D_*[/tex] with the homotopy/induced boundary
[tex]\Delta f = \partial_Df\pm f\partial_C[/tex]
For this complex, we get
[tex]H_0(Hom(C_*,D_*))[/tex] is the family of chain homotopy
classes of chain maps [tex]C_*\to D_*[/tex].
Recall: [tex]f,g[/tex] are chain homotopic if there is a family
[tex]h_i: C_i\to D_{i+1}[/tex] such that [tex]f-g = \partial_D
h_i + h_{i-1}\partial_C[/tex].
Homotopic space maps yield homotopic chain complex maps. And thus
[tex]Top_*(Z,Sp^\infty(X)) = H_*(Hom(C_*,D_*),\Delta)[/tex]
How, though, do we get from [tex][Z,Sp^\infty(X)][/tex] to
[tex][Z,X][/tex]?
Cosimplicial spaces
A simplicial space is a contravariant [tex]\Delta\to X[/tex]. It has
a total space or realization given by
[tex]\coprod X_n\times\Delta[n]/\sim[/tex]
In the dual setting of cosimplicial spaces, the total space is a
subspace of
[tex]X^0\times(X^1)^{\Delta[1]}\times(X^2)^{\Delta[2]}\times(X^3)^{\Delta[3]}\times\dots[/tex].
There is a cosimplicial space
[tex]Sp^\infty(X) \leftrightarrow Sp^\infty Sp^\infty(X)
\leftrightarrow \dots[/tex]
whose total space is [tex]X[/tex].
Furthermore, there is a spectral sequence starting at
[tex]H_*(Sp^\infty(X))[/tex] (well understood space!)
going through
[tex]\pi_*(Top_*(Z,Sp^\infty Sp^\infty Sp^\infty X))
\leftrightarrow \pi_*(Top_*(Z,Sp^\infty Sp^\infty X))
\leftrightarrow \pi_*(Top_*(Z,Sp^\infty X))[/tex]
which recovers [tex]\pi_*(Top_*(Z,X))[/tex] for us.
The mapping space [tex]Top_*(Z,X)[/tex] maps to
[tex]Top_*(Z,Sp^\infty X)[/tex], which sends
[tex]H_*(Hom(C_*Z,C_*X))[/tex] to chain maps. Differentials give
us conditions on chain maps to come from actual maps on the topological
level [tex]Z\to X[/tex].
Suppose now that [tex]X[/tex] is a simplicial complex, and
[tex]H_*X[/tex] is known, say isomorphic to [tex]H_*S^1[/tex].
We pick [tex]S^1[/tex] as a model space, and work in
[tex]Hom(C_*X,C_*S^1)[/tex]. We pick out conditions form the
spectral sequence above to pick out chain maps that might come from
topological maps.
Suppose we had some chain map
[tex]C_*X\overset{\varphi}{\to}C_*S^1[/tex] that sends
[tex]\sigma\mapsto\sum_{i=0}^n\eta_i[/tex].
We look for a chain homotopic map [tex]\hat\varphi[/tex] such that
[tex]\hat\varphi(\sigma)[/tex] is a simplex (this will be WAY too
optimistic, usually) or at least [tex]\hat\varphi(\sigma) =
\sum_{i=0}^n\eta_i[/tex] for small [tex]n[/tex] and
[tex]\eta_i[/tex] close together in graph distances.
Yi Ding: there are likely many simplicial maps [tex]X\to S^1[/tex]
inducing any given [tex]H_*X\to H_*S^1[/tex]. This makes
optimizations on quality of maps (as measured in smallness properties of
preimages of given simplices) troublesome, since we have a large search
space and are likely to get stuck in local minima.
The topological approach creates very many maps, but we just want ONE -
albeit with quality assurances. The big question is how to get there:
Shrinking the space? Homotopy collapses to reduce the number of
generators?
Ask for more side conditions? If so, which?
Minimize the size of preimages and kernels - smoothing the resulting
map?
Run with one condition until we reach a minimum, then change conditions
to get out of that particular sink, repeat until it all looks stable?
Thus we need to search for strategies to improve convergence to actually
good maps.
The questions we pose are similar to:
Jeff Ericksson, et al.: Given X, [tex]x\in H_n(X)[/tex], how do we
find a good representative [tex]\xi\in x[/tex]?
Finding good maps is really about finding good representatives in
[tex]Hom(C_*X,C_*Y)[/tex]. Given simplicial bases
[tex]\{\sigma_i\}\subseteq X, \{\eta_i\}\subseteq Y[/tex] we
can pick out a first basis
[tex]\varphi_{\sigma_i\eta_j}(\sigma_k)=\delta_{ik}\eta_j[/tex]
(Kronecker [tex]\delta[/tex]) for [tex]Hom(C_*X,C_*Y[/tex].
Finally: many problems in data analysis call for analyzing contractible
spaces. So if we pick out the notion of a boundary, doing all of this
relative to a boundary would give us increased power to use the
resulting methods in data analysis.