Skip to Content »

Michi’s blog » Coordinatization with hom complexes

 Coordinatization with hom complexes

  • December 7th, 2009
  • 10:55 pm

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.

Coordinatization

First off, a few words on what we mean by coordinatization: as in algebraic geometry, we say that a coordinate function is some X\to\mathbb R or possibly some X\to\mathbb C, with all the niceness properties we’d expect to see in the context we’re working.

A particularly good example is Principal Component Analysis which yields a split linear automorphism on the ambient space that maximizes spread of the data points in the initial coordinates.

Topological coordinatization

The core question we’re working with right now is this:
Given a space (point cloud) X, and a (persistent) view of H_*(X), can we use some map H_*(X)\to H_*(Y) to generate a map X\to Y 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 H^*(\Omega X) using H^*(X). We note that \Omega X = Top_*(S^1,X) with the compact open topology.

We fix a field k of coefficients. We can find a spectral sequence that computes
Tor_{H^*(X)}(k,k)’ \Rightarrow H^*(\Omega X)

Variations of this spectral sequence allow us to compute H^*(Map(X,Y)). A homotopy class of maps thus corresponds to a cohomology element from H^*(F(X,Y)).

Monad approximation

Define
Sp^2(X) = X \times_{\mathbb Z/2} X (unordered pairs)
and similarily unordered tuples
Sp^n(X) = X^n/\Sigma_n
we can get a map, for pointed spaces (X,*)
Sp^n(X) \to Sp^{n+1}(X)
(x_1,\dots,x_n)\mapsto(x_1,\dots,x_n,*)

In the limit, we get the union Sp^\infty(X).

The Dold-Thom theorem tells us:
\pi_i(Sp^\infty(X)) = H_i(X)

Suppose we are really looking for maps Z\to Sp^\infty(X,*) \supseteq X = Sp^1(X).

We pick chain complexes C_*, D_*. There is a hom chain complex Hom(C_*,D_*) consisting of graded maps C_*\to D_* with the homotopy/induced boundary
\Delta f = \partial_Df\pm f\partial_C

For this complex, we get
H_0(Hom(C_*,D_*)) is the family of chain homotopy classes of chain maps C_*\to D_*.

Recall: f,g are chain homotopic if there is a family h_i: C_i\to D_{i+1} such that f-g = \partial_D h_i + h_{i-1}\partial_C.

Homotopic space maps yield homotopic chain complex maps. And thus
Top_*(Z,Sp^\infty(X)) = H_*(Hom(C_*,D_*),\Delta)

How, though, do we get from [Z,Sp^\infty(X)] to [Z,X]?

Cosimplicial spaces

A simplicial space is a contravariant \Delta\to X. It has a total space or realization given by
\coprod X_n\times\Delta[n]/\sim

In the dual setting of cosimplicial spaces, the total space is a subspace of X^0\times(X^1)^{\Delta[1]}\times(X^2)^{\Delta[2]}\times(X^3)^{\Delta[3]}\times\dots.

There is a cosimplicial space
Sp^\infty(X) \leftrightarrow Sp^\infty Sp^\infty(X) \leftrightarrow \dots
whose total space is X.

Furthermore, there is a spectral sequence starting at H_*(Sp^\infty(X)) (well understood space!)
going through
\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))
which recovers \pi_*(Top_*(Z,X)) for us.

The mapping space Top_*(Z,X) maps to Top_*(Z,Sp^\infty X), which sends H_*(Hom(C_*Z,C_*X)) to chain maps. Differentials give us conditions on chain maps to come from actual maps on the topological level Z\to X.

Suppose now that X is a simplicial complex, and H_*X is known, say isomorphic to H_*S^1.

We pick S^1 as a model space, and work in Hom(C_*X,C_*S^1). 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 C_*X\overset{\varphi}{\to}C_*S^1 that sends \sigma\mapsto\sum_{i=0}^n\eta_i.

We look for a chain homotopic map \hat\varphi such that \hat\varphi(\sigma) is a simplex (this will be WAY too optimistic, usually) or at least \hat\varphi(\sigma) = \sum_{i=0}^n\eta_i for small n and \eta_i close together in graph distances.

Yi Ding: there are likely many simplicial maps X\to S^1 inducing any given H_*X\to H_*S^1. 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, x\in H_n(X), how do we find a good representative \xi\in x?

Finding good maps is really about finding good representatives in Hom(C_*X,C_*Y). Given simplicial bases \{\sigma_i\}\subseteq X, \{\eta_i\}\subseteq Y we can pick out a first basis
\varphi_{\sigma_i\eta_j}(\sigma_k)=\delta_{ik}\eta_j (Kronecker \delta) for Hom(C_*X,C_*Y.

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.

2 People had this to say...

Gravatar
  • Andres Angel
  • December 7th, 2009
  • 23:57

Dold-Thom theorem?… interesting stuff…

Gravatar
  • Michi
  • December 8th, 2009
  • 0:10

Oh look. You’re right. *edits*

Want your say?

* Required fields. Your e-mail address will not be published on this site

You can use the following XHTML tags:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>