Sunday, July 31, 2016

(Co)fibrations, suspensions, and loop spaces

 Seminar topic

Recall the exponential object $Z^Y$, which, in the category of topological spaces, is the set of all continuous functions $Y\to Z$. In general, the definition involves a commuting diagram and gives an isomorphism $\Hom(X\times Y,Z)\cong \Hom(X,Z^Y)$. The subspace $F(Y,Z)$ of $Z^Y$ consists of based functions $Y\to Z$.

Definition: Let $F,E,B,X$ be topological spaces. A map $i:F\to E$ is a cofibration if for every map $f:E\to X$ and every homotopy $h:F\times I\to X$, there exists a homotopy $\tilde h:E\times I\to X$ (extending $h$) making either of the equivalent diagrams below commute.

The horizontal maps on the left are the natural inclusion maps $x\mapsto (x,0)$ and the map on the right is the natural evaluation map $\varphi \mapsto \varphi(0)$. Similarly, a map $p:E\to B$ is a fibration if for every map $g:X\to E$ and every homotopy $h:X\times I\to B$, there exists a homotopy $\tilde h:X\times I\to E$ (lifting $h$) making either of the equivalent diagrams below commute.

The horizontal maps on the right are the natural evaluation maps and the map on the right is the natural inclusion map.

Instead of this terminology, often we say the pair $(F,E)$ has the homotopy extension property and the pair $(E,B)$ has the homotopy lifting property. Now, let let $(X,x)$ be a pointed topological space.

Definition: The (reduced) suspension $\Sigma X$ of $X$ is
\[
\Sigma X := X\times I/X\times \{0\} \cup X\times \{1\} \cup \{x\}\times I.
\] 
The unreduced suspension $SX$ of $X$ is
\[
S X := X\times I/X\times \{0\} \cup X\times \{1\}.
\]
The loop space $\Omega X$ of $X$ is
\[
\Omega X := F(S^1,X).
\]
Remark: If $X$ is well-pointed (the inclusion $i:\{x\}\hookrightarrow X$ is a cofibration), then the natural quotient map $SX\to \Sigma X$ is a homotopy equivalence. Moreover, there is an adjunction $F(\Sigma X,Y)\cong F(X,\Omega Y)$. In the fundamental group this gives the adjunction
\[
[\Sigma X,Y]\cong [X,\Omega Y],
\]
where $[A,B]$ is the set of based homotopy classes of maps $A\to B$.

References: May (A concise course in algebraic toplogy, Chapters 6, 7, 8), Aguilar, Gitler, and Prieto (Algebraic topology from a homotopical viewpoint, Chapter 2.10)

Monday, July 25, 2016

Connections, curvature, and Higgs bundles

Recall (from a previous post) that a Kähler manifold $M$ is a complex manifold (with natural complex structure $J$) with a Hermitian metic $g$ whose fundamental form $\omega$ is closed. In this context $M$ is Kähler. Previously we used upper-case letters $V,W$ to denote vector fields on $M$, but here we use lower-case letters $s,u,v$ and call them sections (to consider vector bundles more generally as sheaves).

Definition: A connection on $M$ is a $\C$-linear homomorphism $\nabla: A^0_M\to A^1_M$ satisfying the Leibniz rule $\nabla(fs) = (df)\wedge s + f\nabla (s)$, for $s$ a section of $TM$ and $f\in C^\infty(M)$.

For ease of notation, we often write $\nabla_us$ for $\nabla(s)(u)$, where $s,u$ are sections of $TM$. On Kähler manifolds there is a special connection that we will consider.

Proposition:
On $M$ there is a unique connection $\nabla$ that is (for any $u,v\in A^0_M$)
  1. Hermitian (satisfies $dg(u,v) = g(\nabla (u),v) + g(u,\nabla (v))$),
  2. torsion-free (satisfies $\nabla_uv - \nabla_vu-[u,v] = 0$), and
  3. compatible with the complex structure $J$ (satisfies $\nabla_uv = \nabla_{Ju}(Jv)$).

If $\nabla$ satisfies the first two conditions, it is called the Levi-Civita connection, and if it satisfies the first and third conditions, it is called the Chern connection. If $g$ is not necessarily Hermitian, $\nabla$ is called metric if it satisfies the first condition. From here on out $\nabla$ denotes the unique tensor described in the proposition above.

Definition: The curvature tensor of $M$ is defined by
\[
R(u,v) = \nabla_u\nabla_v - \nabla_v\nabla_u-\nabla_{[u,v]}.
\]
It may be viewed as a map $A^2 \to A^1$, or $A^3\to A^0$, or $A^0\to A^0$. The Ricci tensor of $M$ is defined by
\[
r(u,v) = \trace(w\mapsto R(u,v)w) = \sum_i g(R(a_i,u)v,a_i),
\]
for the $a_i$ a local orthonormal basis of $A^0 = TM$. This is a map $A^2\to A^0$. The Ricci curvature of $M$ is defined by
\[
\Ric(u,v) = r(Ju,v).
\]
This is a map $A^2\to A^0$.

Definition: An Einstein manifold is a pair $(M,g)$ that is Riemannian and for which the Ricci curvature is directly proportional to the Riemannian metric. That is, there exists a constant $\lambda\in \R$ such that $\Ric(u,v) = \lambda g(u,v)$ for any $u,v\in A^1$.

Recall that a holomorphic vector bundle $\pi:E\to M$ has complex fibers and holomorphic projection map $\pi$. Here we consider two special vector bundles (as sheaves), defined on open sets $U\subset M$ by
\begin{align*}
\End(E)(U) & = \{f:\pi^{-1}(U)\to \pi^{-1}(U)\ :\ f|_{\pi^{-1}(x)}\text{\ is a homomorphism}\}, \\
\Omega_M(U) & = \left\{\sum_{i=0}^n f_idz_1\wedge\cdots \wedge dz_i\ :\ f_i\in C^\infty(U)\right\},
\end{align*}
where $z_1,\dots,z_n$ are local coordinates on $U$. The first is the endomorphism sheaf of $E$ and the second is the sheaf of differential forms of $M$, or the holomorphic cotangent sheaf. The cotangent sheaf as defined is a presheaf, so we sheafify to get $\Omega_M$.

Definition: A Higgs vector bundle over a complex manifold $M$ is a pair $(E,\theta)$, where $\pi:E\to M$ is a holomorphic vector bundle and $\theta$ is a holomorphic section of $\text{End}(E)\otimes \Omega_M$ with $\theta\wedge\theta = 0$, called the Higgs field.

References: Huybrechts (Complex Geometry, Chapters 4.2, 4.A), Kobayashi and Nomizu (Foundations of Differential Geometry, Volume 1, Chapter 6.5)

Saturday, July 2, 2016

On the separation of nearest neighbors

We work through Lemma 3 (called the "$A-B$ Lemma" or the "cleaning procedure") of [2], adopting a cleaner and more thorough approach.

Necessary tools

Definition: The inverse of the complex-valued function $f(z) = ze^z$ is called the Lambert $W$-function and denoted by $W = f^{-1}$. When restricted to the real numbers, it is multi-valued on part of its domain, so it is split up into two branches $W_0$ (for positive values) and $W_{-1}$ (for negative values).

Hoeffding's inequality gives an upper bound on how much we should expect a sum of random variables to deviate from their combined mean. The authors of [2] use a similar inequality called the Chernoff bound, but Hoeffding gives a tighter bound on the desired event.

Proposition:
(Hoeffding - Theorem 2 and Equation (1.4) of [1])
Let $X_1,\dots,X_n$ be independent random variables, with $X_i$ bounded on the interval $[a_i,b_i]$. Then
\[
P\left(\left| \frac1n\sum_{i=1}^n X_i - \frac 1n\sum_{i=1}^n E[X_i]\right|\geqslant t\right) \leqslant 2\exp\left(\frac{-2t^2n^2}{\sum_{i=1}^n(b_i-a_i)^2}\right).
\]

The union bound (or Boole's inequality) says that the probability of one of a collection of events happening is no larger than the sum of the probabilities of each of the events happening.

Proposition:
Let $A_1,A_2,\dots$ be a countable collection of events. Then $P(\bigcup_i A_i) \leqslant \sum_i P(A_i)$.

The setup

Let $P$ be a probability distribution $P$ on $\R^n$ and $X=\{x_1,\dots,x_k\}\subseteq \R^n$ a finite set of points drawn according to $P$. These points may be considered as random variables $X_1,X_2,\dots,X_k$ on the sample space $\R^n$, with $X_i$ evaluating to 1 only on $x_i$, and 0 otherwise. Choose $s>0$ and construct the nearest neighbor graph $G$ on $X$, with parameter $s$. Write $X=A\cup B$ and set
\[
\eta := \inf_{a\in A,b\in B}\left\{|| a-b||\right\}
\hspace{1cm},\hspace{1cm}
\alpha_s := \inf_{a\in A}\left\{P(B^n(s,a))\right\}
\hspace{1cm},\hspace{1cm}
\beta_s \:= \sup_{b\in B}\left\{P(B^n(s,b))\right\},
\]
with $h = (\alpha_s-\beta_s)/2$. We assume that
  • $\eta>0$, so $A$ and $B$ are disjoint;
  • $s<\eta/2$, so $A$ and $B$ are in separate components of $G$; and
  • $\alpha_s >\beta_s$, so any point in $A$ is more likely to be chosen than every point in $B$.
Proposition: Choose $\delta\in (0,1)$. If $|X| >-W_{-1}(-\delta h^2e^{-2h^2})/(2h^2)$, then for all $a\in A$ and $b\in B$, with probability $1-\delta$,
\[
\frac{\deg_G(a)}{k - 1} > \frac{\alpha_s+\beta_s}2
\hspace{1cm}\text{and}\hspace{1cm}
\frac{\deg_G(b)}{k - 1} < \frac{\alpha_s+\beta_s}2.
\]
The statement holds also for $\alpha,\beta$ instead of $\alpha_s,\beta_s$, such that $\alpha_s\> \alpha >\beta \> \beta_s$, which may be useful to bound the degree of vertices in $G$.

The proof

For each $i=1,\dots,k$, define new random variables $Y_{ij}$ on the sample space $X$, with $Y_{ij}$ evaluating to 1 on $x_j$ iff $x_j\in B^n(s,x_i)$, and evaluating to 0 otherwise. The mean of $Y_{ij}$ is $P(B^n(s,x_i))$. Since the $Y_{ij}$ are independent with the same mean, Hoeffding's inequality gives that
\[
\left(\begin{array}{c}
\text{the probability that the sampled $x_j$}\\
\text{have clustered around a point more than} \\
\text{a distance $h$ away from $B^n(s,x_i)$}
\end{array}\right)
=
P\Bigg(\underbrace{\left|\frac{1}{k-1}\sum_{j\neq i} Y_{ij} - P(B^n(s,x_i))\right| \> h}_{\text{event}\ A_i}\Bigg)  \leqslant 2e^{-2h^2(k-1)}.
\]
The union bound gives that
\[
\left(\begin{array}{c}
\text{the probability that at}\\
\text{least one $A_i$ occurs}
\end{array}\right)
=
P\left(\bigcup_{i=1}^k A_i\right) < \sum_{i=1}^k P(A_i) \leqslant 2ke^{-2h^2(k-1)}.
\]
Note that $\sum_{j\neq i} Y_{ij} = \deg_G(x_i)$ for every $i$, so whenever $\delta>2ke^{-2h^2(k-1)}$, with probability $1-\delta$
\[
\left| \frac{\deg_G(x_i)}{k-1} - P(B^n(s,x_i))\right| < h
\hspace{1cm}\text{or}\hspace{1cm}
P(B^n(s,x_i)) -h < \frac{\deg_G(x_i)}{k-1} < P(B^n(s,x_i)) + h.
\]
When $x_i\in A$ ($x_i\in B$) we have a lower (upper) bound of $\alpha_s$ ($\beta_s$) on $P(B^n(s,x_i))$. Indeed:
\[
\frac{\deg_G(a)}{k-1} > \alpha_s- h =  \frac{\alpha_s+\beta_s}2
\hspace{1cm}\text{and}\hspace{1cm}
\frac{\deg_G(b)}{k-1} < \beta_s + h = \frac{\alpha_s+\beta_s}2.
\]
To find how many points we need to sample, we solve for $k$ in the inequality $ \delta > 2ke^{-2h^2(k-1)}$. With the aid of a computer algebra system, we find that
\[
k > \frac{-1}{2h^2}W_{-1}\left(-\delta h^2e^{-2h^2}\right),
\]
completing the proof.

References:
[1] Hoeffding (Probability inequalities for sums of bounded random variables)
[2] Niyogi, Smale, and Weinberger (A topological view of unsupervised learning from noisy data)

Tuesday, June 28, 2016

The conditioning number of a projective curve

Let $C$ be a smooth algebraic curve in $\P^2$. That is, for some homogeneous $f\in \C[x_0,x_1,x_2]$ we let $C = \{x\in \P^2\ :\ f(x)=0\}$. Describe $C$ as a manifold via the usual open sets $U_i = \{x\in \P^2\ :\ x_i\neq 0\}$ and charts
\[
\begin{array}{r c l}
\varphi_0\ :\ U_0 & \to & \C^2, \\\
[x_0:x_1:x_2] & \mapsto & (\frac{x_1}{x_0},\frac{x_2}{x_0}),
\end{array}
\hspace{1cm}
\begin{array}{r c l}
\varphi_1\ :\ U_1 & \to & \C^2, \\\
[x_0:x_1:x_2] & \mapsto & (\frac{x_0}{x_1},\frac{x_2}{x_1}),
\end{array}
\hspace{1cm}
\begin{array}{r c l}
\varphi_2\ :\ U_2 & \to & \C^2, \\\
[x_0:x_1:x_2] & \mapsto & (\frac{x_0}{x_2},\frac{x_1}{x_2}).
\end{array}
\]
Let $w=[w_0:w_1:w_2]\in \P^2$ for which $f(w)=0$. The Jacobian of $C$ at $w$ is then
\[
J_w = \left[
\left.\frac{\dy f}{\dy x_0}\right|_w \ :\  \left.\frac{\dy f}{\dy x_1}\right|_w \ :\  \left.\frac{\dy f}{\dy x_2}\right|_w
\right] \in \P^2.
\]
Assume that $\left.\frac{\dy f}{\dy x_0}\right|_w\neq 0$ and pass to $\varphi_0(U_0)$ to get the Jacobian to be
\[
J_w^0 = \left(
\frac{\dy f/\dy x_1|_w}{\dy f/\dy x_0|_w}\ ,\ \frac{\dy f/\dy x_2|_w}{\dy f/\dy x_0|_w}\right)  \in \C^2.
\]
Assume that $w_0\neq 0$, so the tangent line to $\varphi_0(C)\subset \C^2$ at $\varphi_0(w)=(w_1/w_0,w_2/w_0)$ is
\[
T_{\varphi_0(w)}= \{\varphi_0(w)+tJ_w^0\ :\ t\in \C\}\subset \C^2.
\]
A vector orthogonal to the Jacobian $J_w^0$ is
\[
\bar J_w^0 = \left(-\frac{\dy f/\dy x_2|_w}{\dy f/\dy x_0|_w}\ ,\ \frac{\dy f/\dy x_1|_w}{\dy f/\dy x_0|_w}\right) \in \C^2,
\]
so the space space normal to $T_{\varphi_0(w)}$ is given by
\[
T_{\varphi_0(w)}^\perp = \{\varphi_0(w)+t\bar J_w^0\ :\ t\in \C\}\subset \C^2.
\]

Example: Let $C\subset \P^2$ be the zero locus of $f(x_0,x_1,x_2) = x_0^2+x_1x_2-x_1x_0$. The Jacobian is $J = [2x_0-x_1:x_2-x_0:x_1]$, and as $J=0$ implies $x_0=x_1=x_2=0$, but $0\not\in\P^2$, the curve $C$ is smooth. Consider two points $w=[1:1:0],z=[2:1:-2]\in C$, at which the Jacobian is
\[
J_w = [1:-1:1]
\hspace{1cm},\hspace{1cm}
J_z = [3:-4:1].
\]
Both $w_0$ and $z_0$ are non-zero, with $\varphi_0(w)=(1,0)$ and $\varphi_0(z)=(1/2,-1)$, giving the tangent and normal spaces to be
\begin{align*}
T_{(1,0)} & = \{(1,0)+t(-1,1)\ :\ t\in \C\}, & T_{(1/2,-1)} & = \{(1/2,-1)+s(-4/3,1/3)\ :\ s\in \C\}, \\
T^\perp_{(1,0)} & = \{(1,0)+t(-1,-1)\ :\ t\in \C\}, & T_{(1/2,-1)}^\perp & = \{(1/2,-1)+s(-1/3,-4/3)\ :\ s\in \C\}.
\end{align*}
The two normal spaces intersect at $(t,s)=(1/3,-1/2)$ at distances of $1/3\cdot ||(-1,-1)|| = \sqrt 2/3\approx 0.471$ and $1/2\cdot||(-1/3,-4/3)|| = \sqrt{17}/3\approx 1.374$ from the points $\varphi_0(w),\varphi_0(z)$, respectively. Hence the conditioning number of $C$ is at most $\sqrt 2/3$.

Given a smooth projective curve and a finite set of points, this Sage code will calculate the conditioning number from that collection of points.

Thursday, June 16, 2016

Smooth projective varieties as Kähler manifolds

Definition: Let $k$ be a field and $\P^n$ projective $n$-space over $k$. An algebraic variety $X\subset \P^n$ is the zero locus of a collection of homogeneous polynomials $f_i\in k[x_0,\dots,x_n]$.

Here we let $k=\C$, the complex numbers. Complex projective space $\C\P^n$ may be described as a complex manifold, with open sets $U_i = \{(x_0:\cdots:x_n)\ :\ x_i\neq 0\}$ and maps
\[
\begin{array}{r c l}
\varphi_i\ :\ U_i & \to & \C^n, \\
(x_0:\cdots:x_n) & \mapsto & \left(\frac{x_0}{x_i},\dots,\widehat{\frac{x_i}{x_i}},\dots,\frac{x_n}{x_i}\right),
\end{array}
\]
which can be quickly checked to agree on overlaps. In this context we assume all varieties are smooth, so they are submanifolds of $\C\P^n$.

Definition: An almost complex manifold is a real manifold $M$ together with a vector bundle endomorphism $J:TM\to TM$ (called a complex structure) with $J^2=-\id$.

Note that every complex manifold admits an almost complex structure on its underlying real manifold. Indeed, given standard coordinates $z_i=x_i+y_i$ for $i=1,\dots,n$ on $\C^n$, we get a basis $\partial/\partial x_1, \dots, \partial /\partial x_n$, $\partial/\partial y_1, \dots, \partial/\partial y_n$ on the underlying real tangent space $T_pU$, for $p\in M$ and $U\owns p$ a neighborhood. Then $J$ is defined by
\[
J\left(\frac\partial{\partial x_i}\right) = \frac\partial{\partial y_i}
\hspace{1cm},\hspace{1cm}
J\left(\frac\partial{\partial y_i}\right) = -\frac\partial{\partial x_i}.
\]
Write $T_\C M=TM\otimes_\R\C$ for the complexification of the tangent bundle, which admits a canonical decomposition $T_\C M = T^{1,0}M\oplus T^{0,1}M$, where $J|_{T^{1,0}}=i\cdot \id$ and $J|_{T^{0,1}}=(-i)\cdot \id$. We call $T^{1,0}M$ the holomorphic tangent bundle of $M$ and $T^{0,1}M$ the antiholomorphic tangent bundle of $M$, even though it is extraneous to consider any related map here as holomorphic. Define vector bundles (or sheaves, to consider sections on open sets)
\[
A^k_M = \textstyle \bigwedge^k(T_\C M)^*,
\hspace{1cm}
A^{p,q}_M = \textstyle \bigwedge^p(T^{1,0}M)^* \otimes_\C \bigwedge^q(T^{0,1}M)^*,
\]
where we drop the subscript $M$ when the context makes it clear. There is a canonical decomposition $A^k = \bigoplus_{p+q=k} A^{p,q}$, which yields projection maps $\pi^{p,q}:A^k \to A^{p,q}$. The exterior differential $d$ on $T^*M$ may be extended $\C$-linearly to $(T_\C M)^*$, and hence also to $A^k$. Define two new maps
\begin{align*}
\partial = \pi^{p+1,q}\circ d|_{A^{p,q}}\ :\ &\ A^{p,q} \to A^{p+1,q}, \\
\bar\partial = \pi^{p,q+1}\circ d|_{A^{p,q}}\ :\ &\ A^{p,q} \to A^{p,q+1}.
\end{align*}
These satisfy the Leibniz rule and (under mild assumptions) $\partial^2 = \bar\partial^2 = 0$ and $\partial \bar \partial = -\bar \partial \partial$.

From now on, the manifold $M$ will be complex with the natural complex structure described above.

Definition: A Riemannian metric on $M$ is a function $g:TM\times TM \to C^\infty(M)$ such that for all $V,W\in TM$,
  • $g(V,W)=g(W,V)$, and
  • $g_p(V_p,V_p)\geqslant 0$ for all $p\in M$, with equality iff $V=0$.
A Riemannian manifold is a pair $(M,g)$ where $g$ is Riemannian.

Locally we write $g_p:T_pM\times T_pM \to \R$, defined as $g_p(V_p,W_p)=g(V,W)(p)$. If $x_1,\dots,x_n$ are local coordinates on some open set $U\subset M$, then $g=\sum_{i,j}g_{ij}dx_i\wedge dx_j\in A^2(M)$, for $g_{ij} = g(\frac\partial{\partial x_i},\frac \partial{\partial x_j})\in C^\infty(U)$. Writing $V = \sum_if_i\frac\partial{\partial x_i}$ and $W=\sum_jg_j\frac\partial{\partial x_j}$, we get the local expression
\[
g_p(V_p,W_p) = \sum_{i,j}g_{ij}(p)f_i(p)g_j(p).
\]

Definition: A Hermitian metric on a complex manifold $M$ is a Riemannian metric $g$ such that $g(JV,JW)=g(V,W)$ for all $V,W\in TM$. A Hermitian manifold is a pair $(M,g)$ where $g$ is Hermitian.

There is an induced form $\omega:TM \times TM\to C^\infty(M)$ given by $\omega (V,W)=g(JV,W)$, called the fundamental form. From $g$ being Hermitian it follows that $\omega\in A^{1,1}(M)\subset A^2(M)$. Note also that any two of the structures $J,g,\omega$ determine the remaining one.

Definition: A Kähler metric on a complex manifold $M$ is a Hermitian metric whose fundamental form is closed (that is, $d\omega = 0$). A Kähler manifold is a pair $(M,g)$ where $g$ is Kähler.

Example: Recall the atlas given to $\C\P^n$ above. There is a metric (canonical in some sense) on each $U_j$ given by
\[
\omega_j = \frac i{2\pi} (\partial \circ \bar\partial) \left(\log\left(\sum_{\ell=0}^n \left|\frac{x_\ell}{x_j}\right|^2 \right)\right),
\]
called the Fubini--Study metric. Each $\omega_j$ is a section of $A^{1,1}(U_j)$, and as a quick calculation shows that $\omega_j|_{U_j\cap U_k} = \omega_k|_{U_j\cap U_k}$, there is a global metric $\omega_{FS}\in A^{1,1}(\C\P^n)$ such that $\omega_{FS}|_{U_j} = \omega_j$ for all $j$.

Hence $\C\P^n$ is a Kähler manifold. If we have a smooth projective variety $X\subset \C\P^n$, then it is a submanifold of $\C\P^n$, so by restricting $\omega_{FS}$ to $X$, we get that $X$ is also a Kähler manifold. Therefore all smooth projective varieties are Kähler.

References: Huybrechts (Complex Geometry, Chapters 1.3, 2.6, 3.1), Lee (Riemannian manifolds, Chapter 3)

Thursday, May 26, 2016

Reconstructing a manifold from sample data, with noise

We follow the article [3] and add more background and clarifications. Some assumptions are made that are not explicitly mentioned in the article, to make calculations easier.

Background in probability, measure theory, topology

Let $X$ be a random variable over a space $A$. Recall that the expression $P(X)$ is a number in $[0,1]$ describing the probability of the event $X$ happening. This is called a probability distribution. Here we will consider continuous random variables, so $P(X=x)=0$ for any single element $x\in A$.

Definition: The probability density function of $X$ is the function $f:A\to \R$ satisfying
  • $f(x)\geqslant 0$ for all $x\in A$, and
  • $\int_B f(x)\ dx = P(X\in B)$ for any $B\subseteq A$.
The second condition implies $\int_A f(x)\ dx=1$.

Often authors use just $P$ instead of $f$, and write $P(x)$ instead of $P(X=x)$.

Definition: Let $Y=g(X)$ be another random variable. The expected value of $Y$ is
\[
E[Y] = E[g(X)] = \int_Ag(x)f(x)\ dx.
\]
The mean of $X$ is $\mu= E[X]$, and the variance of $X$ is $\sigma^2 = E[(X-\mu)^2]$. If $\vec X=(X_1\ \cdots\ X_n)^T$ is a multivariate random variable, then $\vec \mu=E[\vec X]$ is an $n$-vector, and the variance is an $(n\times n)$-matrix given as
\[
\Sigma = E[(\vec X-E[\vec X])(\vec X-E[\vec X])^T]
\hspace{1cm}
\text{or}
\hspace{1cm}
\Sigma_{ij} = E[(X_i-E[X_i])(X_j-E[X_j])].
\]
The covariance of $X$ and $Y$ is $E[(X-E[X])(Y-E[Y])]$. Note that the covariance of $X$ with itself is just the usual variance of $X$.

Example: One example of a probability distribution is the normal (or Gaussian) distribution, and we say a random variable with the normal distribution is normally distributed. If a random variable $X$ is normally distributed with mean $\mu$ and variance $\sigma^2$, then the probability density function of $X$ is
\[
f(x) = \frac{\exp\left(-\frac{(x-\mu)^2}{2\sigma^2}\right)}{\sigma\sqrt{2\pi}}.
\]
If $\vec X=(X_1\ \cdots\ X_n)^T$ is a normally distributed multivariate random variable, then $\vec \mu = (E[X_1]\ \cdots\ E[X_n])^T$ and the probability density function of $\vec X$ is
\[
f(\vec x) = \frac{\exp\left(-\frac 12 (\vec x-\vec \mu)^T\Sigma^{-1}(\vec x-\vec \mu)\right)}{\sqrt{(2\pi)^n\det(\Sigma)}}.
\]

Definition: A measure on $\R^D$ is a function $m:\{$subsets of $\R^D\}\to [0,\infty]$ such that $m(\emptyset) = 0$ and $m(\bigcup_{i\in I} E_i) = \sum_{i\in I} m(E_i)$ for $\{E_i\}_{i\in I}$ a countable sequence of disjoint subsets of $\R^D$. A probability measure on $\R^D$ is a measure $m$ on $\R^D$ with the added condition that $m(\R^D)=1$.

A probability distribution is an example of a probability measure.

Definition: Let $U= \{U_i\}_{i\in I}$ be a covering of a topological space $M$. The nerve of the covering $U$ is a set $N$ of subsets of $I$ given by
\[
N = \left\{J\subset I\ :\ \bigcap_{j\in J} U_j \neq\emptyset\right\}.
\]
Note that this makes $N$ into an abstract simplicial complex, as $J\in N$ implies $J'\in N$ for all $J'\subseteq J$.

Let $M$ be a smooth compact submanifold of $\R^d$. By the tubular neighborhood theorem (see Theorem 2.11.4 in [3]), every smooth compact submanifold $M$ of $\R^d$ has a tubular neighborhood for some $\epsilon>0$.

Definition: For a particular embedding of $M$, let the condition number of $M$ be $\tau=\sup\{\epsilon\ :$ $M$ has an $\epsilon-$tubular neighborhood$\}$.

Distributions on a manifold

Let $M$ be a $d$-dimensional manifold embedded in $\R^D$, with $D>d$. Recall that every element in $NM\subseteq \R^D$, the normal bundle of $M$, may be represented as a pair $(\vec x,\vec y)$, where $\vec x\in M$ and $\vec y\in T^\perp$ (since $M$ is a manifold, all the normal spaces are isomorphic). Hence we may consider a probability distribution $P$ on $NM$, with $\vec X$ the $d$-multivariate random variable representing points on $M$ and $\vec Y$ the $(D-d)$-multivariate random variable representing points on the space normal to $M$ at a point on $M$. We make the assumption that $\vec X$ and $\vec Y$ are independent, or that
\[
P(\vec X, \vec Y) = P_M(\vec X)P_{T^\perp}(\vec Y).
\]
That is, $P_{T^\perp}$ is a probability distribution that is the same at any point on the manifold.

Definition: Let $P$ be a probability distribution on $NM$ and $f_M$ the probability density function of $P_M$. In the context described above, $P$ satisfies the strong variance condition if
  • there exist $a,b>0$ such that $f_M(\vec x)\in [a,b]$ for all $\vec x\in M$, and
  • $P_{T^\perp}(\vec Y)$ is normally distributed with $\vec \mu = 0$ and $\Sigma = \sigma^2I$.
The second condition implies that the covariance of $Y_i$ with $Y_j$ is trivial iff $i\neq j$, and that the vairance of all the $Y_i$s is the same. From the normally distributed multivariate example above, this also tells us that the probability density function $f^\perp$ of $\vec Y$ is
\[
f^\perp(\vec y) = \frac{\exp\left(\displaystyle-\frac{\sigma^2}{2}\sum_{i=1}^{D-d}y_i^2\right)}{\sigma^{D-d}\sqrt{(2\pi)^{D-d}}}.
\]

Theorem:
In the context described above, let $P$ be a probability distribution on $NM$ satisfying the strong variance condition, and let $\delta>0$. If there is $c>1$ such that
\[
\sigma <\frac{c\tau(\sqrt9-\sqrt 8)}{9\sqrt{8(D-d)}},
\]
then there is an algorithm that computes the homology of $M$ from a random sample of $n$ points, with probability $1-\delta$. The number $n$ depends on $\tau,\delta,c,d,D$, and the diameter of $M$.

The homology computing algorithm

Below is a broad view of the algorithm described in sections 3, 4, and 5 of [1]. Let $M$ be a $d$-manifold embedded in $\R^D$, and $P$ a probability measure on $NM$ satisfying the strong variance condition.

1. Calculate the following numbers:
\begin{align*}
\tau & = \text{condition number of $M$}\\
\text{vol}(M) & = \text{volume of $M$}\\
\sigma^2 & = \text{variance of $P$}
\end{align*}
2. Define (or choose) the following numbers:
\begin{align*}
\delta & \in (0,1) \\
r & \in \left(2\sqrt{2(D-d)}\sigma,\textstyle\frac\tau9 (3-2\sqrt 2)\right) \\
n & > \text{function}(a,r,\tau,d,\delta,\text{vol}(M)) & (\max(A,B)\  \text{in Proposition 9 of [1])} \\
s & = 4r \\
deg & > \textstyle \frac{3a}4 \left(1-\left(\frac r{2\tau}\right)^2\right)^{d/2}\text{vol}\left(B^d(r,0)\right)\\
R & = (9r+\tau)/2
\end{align*}
3. Choose $n$ points randomly from $NM$ according to $P$.
4. From these $n$ points, construct the nearest neighbor graph $G$ with distance $s$.
5. Remove from $G$ all the vertices of degree $<deg$ to get a refined graph $G'$.
6. Set $U=\bigcup_{\vec x\in V(G')}B^D(R,\vec x)$ and construct the simplicial complex $K$ of its nerve.
7. Compute the homology of $K$, which is the homology of $M$, with probability $1-\delta$.

References:
[1] Niyogi, Smale, and Weinberger (A topological view of unsupervised learning from noisy data)
[2] Folland (Real analysis, Chapter 10.1)
[3] Bredon (Topology and Geometry, Chapter 2.11)

Thursday, May 19, 2016

Persistent homology (an example)

Here we follow the article "Persistent homology - a Survey," by Herbert Edelsbrunner and John Harer, published in 2008 in "Surveys on discrete and computational geometry," Volume 453.

Consider the sphere, which has known homology groups. Consider a slightly bent embedding of the sphere in $\R^3$, call it $M$, as in the diagram below (imagine it as a hollow blob, whose outline is drawn below). Let $f:M\to \R$ be the height function, measuring the distance from a point in $M$ to a plane just below $M$, coming out of the page. Then we have some critical values $t_0,t_1,t_2,t_3$, as indicated below. Note we have embedded the shape so that no two critical points of $f$ have the same value.
This is remniscent of Morse theory. Set $M_i = f^{-1}[0,t_i]$ and $b_i = \dim(H_i)$ the $i$th Betti number. Then we may easily calculate the Betti numbers of the $M_j$, as in the table below.
\[
\renewcommand\arraystretch{1.3}
\begin{array}{r|c|c|c|c|c}
& M_0 & M_1 & M_2 & M_3 & M \\\hline
b_0 & 1 & 2 & 1 & 1 & 1 \\\hline
b_1 & 0 & 0 & 0 & 0 & 0 \\\hline
b_2 & 0 & 0 & 0 & 1 & 1
\end{array}
\renewcommand\arraystretch{1}
\]
Definition: In the context above, suppose that there is some $p$ and $j>i$ such that:
  • $b_p(M_i)=b_p(M_{i-1})+1$,
  • $b_p(M_j)=b_p(M_{j-1})-1$, and
  •  the generator of $H_p$ introduced at $t_i$ is the same generator of $H_p$ that disappears at $t_j$.
Then $(i,j)$ (or ($t_i,t_j$)) is called a persistence pair and the persistence of $(i,j)$ is $j-i$ (or $f(j)-f(i)$).

For $i$ not in a persistence pair, we say that $i$ represents an essential cycle, or that the persistence of $i$ is infinite. In the example considered, the only persistence pair is $(1,2)$. This may be presented in a persistence diagram, with the indices of critical points on both axes, and the persistence measured as a vertical distance.
If we put a simplicial complex structure on $M$, we may also calculate the homology (and persistence pairs, although they may be different than the ones found above). To make calculations easier, we instead describe a CW structure on our embedded sphere $M$ (with $X_i$ the $i$-skeleton, and the ordering of the $i$-cells as indicated). The results will be the same as for a simplicial complex structure.
This gives one 0-cell, two 1-cells, and three 2-cells (with the obvious gluings), allowing us to construct the chain groups $C_p$ as well as maps between them. The map $d_p:C_p\to C_{p-1}$ as a matrix has size $\dim(C_{p-1})\times \dim(C_p)$, and has entry $(i,j)$ equal to the number of times, counting multiplicity, that the $i$th $(p-1)$-cell is a face of the $j$th $p$-cell. Calculations are done in $\Z/2\Z$.
\[
d_2\ :\ C_2\to C_1
\hspace{.5cm}\text{is}\hspace{.5cm}
\begin{bmatrix}
1 & 0 & 1 \\ 0 & 1 & 1
\end{bmatrix}
\hspace{2cm}
d_1\ :\ C_1\to C_0
\hspace{.5cm}\text{is}\hspace{.5cm}
\begin{bmatrix}
0 & 0
\end{bmatrix}
\]
The Betti numbers are then $b_p = \dim(C_p) - \text{rk}(d_p)-\text{rk}(d_{p+1})$. From above, it is immediate that $\text{rk}(d_1)=0$, $\text{rk}(d_2) = 2$, and $\text{rk}(d_p)=0$ for all other $p$. This tells us that
\begin{align*}
b_0 & = \dim(C_0) - \text{rk}(d_0) - \text{rk}(d_1) = 1 - 0 - 0 = 1, \\
b_1 & = \dim(C_1) - \text{rk}(d_1) - \text{rk}(d_2) = 2 - 0 - 2 = 0, \\
b_2 & = \dim(C_2) - \text{rk}(d_2) - \text{rk}(d_3) = 3 - 2 - 0 = 1, \\
\end{align*}
as expected. To find the persistence pairs, we introduce a filtration on the simplices (equivalently, on the cells) by always having the faces of a cell precede the cell, as well as lower-dimensional cells preceding higher-dimensional cells. Using the same ordering as described above, consider the following filtration:
\begin{align*}
K_0 & = \{\}, \\
K_1 & = \{e^0_1\}, \\
K_2 & = \{e^0_1,e^1_1,e^1_2\} ,\\
K_3 & = \{e^0_1,e^1_1,e^1_2,e^2_1,e^2_2,e^2_3\},
\end{align*}
so $\emptyset = K_0\subset K_1\subset K_2\subset K_3 = M$. This gives an ordering on all the cells of $M$, namely
\[
\sigma_1 = e^0_1,\
\sigma_2 = e^1_1,\
\sigma_3 = e^1_2,\
\sigma_4 = e^2_1,\
\sigma_5 = e^2_2,\
\sigma_6 = e^2_3.
\]
Construct the boundary matrix $D$, with the $(i,j)$ entry of $D$ equal to the number of times, counting multiplicity, modulo 2, that $\sigma_i$ is a codimension 1 face of $\sigma_j$. In the case of our example sphere, we get the matrix
\[
D = \begin{bmatrix}
0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 & 1 \\
0 & 0 & 0 & 0 & 1 & 1 \\
0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0
\end{bmatrix}
\ \ \sim\ \
\begin{bmatrix}
0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0
\end{bmatrix}
\]
in its reduced form (call it $\tilde D$). With respect to the matrix $\tilde D$, define the following numbers:
\begin{align*}
low(j) & = \text{the row number of the lowest non-zero entry in column $j$} ,\\
zero(p) & = \text{the number of zero columns that correspond to $p$-simplices} ,\\
one(p) & = \text{the number of 1s in rows that correspond to $p$-simplices}.
\end{align*}
We calculate all the relevant values of these expressions to be as below.
\begin{align*}
low(1) & = 0 & zero(0) & = 1 & one(0) & = 0 \\
low(2) & = 0 & zero(1) & = 2 & one(1) & = 2 \\
low(3) & = 0 & zero(2) & = 1 & one(2) & = 0 \\
low(4) & = 2 \\
low(5) & = 3 \\
low(6) & = 0
\end{align*}
For persistence, we have
  • if $low(j)=i\neq 0$, then $(i,j)$ is a persistence pair, 
  • if $low(j)=0$ and there is no $k$ such that $low(k)=j$, then $j$ is an essential cycle.
For our sphere example, we get two persistence pairs $(2,4)$ and $(3,5)$, and two essential cycles 1 and 6. Note that this is different from the persistence pairs found by the height function $f:M\to \R$ earlier (but there are still two essential cycles), because there we were comparing the homologies $H_p(M_j)$, but here we are comparing $H_p(K_\ell)$. The persistence diagram is as below.
As an added feature, from the numbers above we may calculate the homology and relative homology groups. Construct the relative chain groups $C_p(M,K_\ell) = C_p(M)/C_p(K_\ell)$ and set $zero(p,\ell)$ to be $zero(p)$ for the lower right submatrix of $\tilde D$ corresponding to the cells in $M-K_\ell$ (and similarly for $one(p,\ell)$). We find these numbers for the bent sphere to be as below.
\begin{align*}
zero(0,0) & = 1 & zero(0,1) & = 0 & zero(0,2) & = 0 & zero(0,3) & = 0 \\
zero(1,0) & = 2 & zero(1,1) & = 2 & zero(1,2) & = 0 & zero(1,3) & = 0 \\
zero(2,0) & = 1 & zero(2,1) & = 1 & zero(2,2) & = 1 & zero(2,3) & = 0 \\[10pt]
one(0,0) & = 0 & one(0,1) & = 0 & one(0,2) & = 0 & one(0,3) & = 0 \\
one(1,0) & = 2 & one(1,1) & = 2 & one(1,2) & = 0 & one(1,3) & = 0 \\
one(2,0) & = 0 & one(2,1) & = 0 & one(2,2) & = 0 & one(2,3) & = 0
\end{align*}
Note that $zero(p,0)=zero(p)$ and $one(p,0)=one(p)$, as well as $zero(p,3)=one(p,3)=0$. The above numbers are useful in calculating
\begin{align*}
\dim(H_p(M)) & = zero(p)-one(p), \\
\dim(H_p(M,K_\ell)) & = zero(p,\ell) - one(p,\ell).
\end{align*}

References: Edelsbrunner and Harer (Persistent homology - a Survey)