Manifold Learning Note

Manifold Learning

Topological Space

Definition

Topological Space

$(X,\mathcal{T})$ A topological space is a set $X$ along with an additional structure called a Topology $\mathcal{T}$.

Link to original

Open Set

Definition

$U\in \mathcal{T}$

Consider a Topological Space $(X,\mathcal{T})$. The elements of the Topology $\mathcal{T}$ are called the open sets of $X$

Definition in Metric Topology

Consider a Metric Space $(X,{\mathcal{T}}_d,d)$ $U\in {\mathcal{T}}_d⟺\forall y\in U,\exists \delta >0\text{s.t.}{B}_d(y,\delta )\subset U$

Facts

Every point of $U\in \mathcal{T}$ is an interior point of $U$.

Consider a Topological Space $(X,\mathcal{T})$ and a subset $U\subset X$. Then, $U$ is open in $X$ if and only if for an arbitrary point $x$ in $U$, there exists an open subset $U_x\subset U$ containing $x$. $U\in \mathcal{T}⟺\forall x\in U,\exists U_x\ni x\text{s.t.}{U}_x\in \mathcal{T}\text{and}{U}_x\subset U$

$A$ is an open set if and only if it’s equal to its Interior $A=\mathrm{int}A$.

Link to original

Closed Set

Definition

Consider a Topological Space $(X,\mathcal{T})$. A set $C$ is closed if $X\setminus C\in \mathcal{T}$

The complement of an Open Set is called a closed set.

Facts

• $\varnothing$ and $X$ are closed
• $\forall \text{closed}\{C_i{\}}_{i\in I},\bigcap _{i\in I}{C}_i\text{is closed}$
• $\forall \text{closed}\{C_i{\}}_{i=1}^n,\bigcup _{i=1}^n{C}_i\text{is closed}$

Consider a Subspace Topology $(Y,{\mathcal{T}}_Y)$ of a Topological Space $(X,\mathcal{T})$ and a subset $A\subset Y$. Then, $(Y\setminus A)\in {\mathcal{T}}_Y⟺(\exists (X\setminus C)\in \mathcal{T}\text{s.t.}A=C\cap Y)$

Consider a Subspace Topology $(Y,{\mathcal{T}}_Y)$ of a Topological Space $(X,\mathcal{T})$ and a subset $A\subset Y$. Then, $((Y\setminus A)\in {\mathcal{T}}_Y\text{and}(X\setminus Y)\in \mathcal{T})⟹X\setminus A\in \mathcal{T}$

Consider a Topological Space $(X,\mathcal{T})$ and a subset $A\subset X$. Then, $(X\setminus A)\in \mathcal{T}⟺A^{\prime }\subset A$ where $A^{\prime }$ is the set of all limit points of $A$

Consider a Topological Space $(X,\mathcal{T})$ and a subset $A\subset X$. If the subset is equal to its Closure, it is closed. $(X\setminus A)\in \mathcal{T}⟺\bar{A}=A$

Link to original

Neighborhood

Definition

Consider a subset $A$ of a Topological Space $(X,\mathcal{T})$. A neighborhood ${\mathcal{N}}_x$ of a point $x\in X$ is a subset of $X$ including an open set $U\in \mathcal{T}$ containing $x$. $x\in U\subset {\mathcal{N}}_x\subset \mathcal{T}$

Link to original

Embedding

Definition

$f:(X,{\mathcal{T}}_X)\hookrightarrow (Y,{\mathcal{T}}_Y)$ Embedding is a function between two topological spaces has the following properties:

• $f:X\to f(X)$ is a Homeomorphism
• $X\subset Y$

Embedding preserves the structure of a topological structure.

Link to original

Homeomorphism

Definition

A function $f:(X,{\mathcal{T}}_X)\to (Y,{\mathcal{T}}_Y)$ between two topological spaces is a homeomorphism if it satisfies the following conditions:

• $f$ is Bijective
• $f$ and its inverse function $f^{-1}$ are continuous ($f,f^{-1}\in C^0$)
  • Equivalent: $U\in {\mathcal{T}}_X\iff f(U)\in {\mathcal{T}}_Y$

Homeomorphic

Consider the two topological spaces $(X,{\mathcal{T}}_X),(Y,{\mathcal{T}}_Y)$. If there exists a homeomorphism between $X$ and $Y$, then $X$ is homeomorphic to $Y$

Link to original

Compactness

Definition

Consider a Topological Space $(X,\mathcal{T})$. The space is compact if every open covering (a collection of open subsets $\{U_i{\}}_{i\in I}$ of $X$ whose union is $X$) of $X$ has a finite subcovering. $\forall \{U_i{\}}_{i\in I}\subset \mathcal{T}\text{s.t.}{\bigcup }_{i\in I}{U}_i=X,\exists J\subset I\text{s.t.}|J|<\infty \text{and}{\bigcup }_{j\in J}{U}_j=X$

Examples

Consider a Standard Topology on real numbers $(\mathbb{R},\mathcal{U})$. Then, the subspace Topologies

• $\{\frac{1}{n}|n\in \mathbb{N}\}\subset \mathbb{R}$ is not compact

• $\{0\}\cup \{\frac{1}{n}|n\in \mathbb{N}\}\subset \mathbb{R}$ is compact

• $(0,1]\subset \mathbb{R}$ is not compact

• $\mathbb{R}$ is not compact

• $[0,1]\subset \mathbb{R}$ is compact (closed and bounded)

Facts

Consider a Subspace Topology $(Y,{\mathcal{T}}_Y)$ of a Topological Space $(X,\mathcal{T})$. Then, $Y$ is compact if and only if every covering of $Y$ by open sets in $X$ has a finite subcollection covering $Y$. $\forall \{U_i{\}}_{i\in I}\subset {\mathcal{T}}_Y\text{s.t.}{\bigcup }_{i\in I}{U}_i=Y,\exists J\subset I\text{s.t.}|J|<\infty \text{and}{\bigcup }_{j\in J}{U}_j=Y⟺\forall \{U_i{\}}_{i\in I}\subset \mathcal{T}\text{s.t.}{\bigcup }_{i\in I}{U}_i=Y,\exists J\subset I\text{s.t.}|J|<\infty \text{and}{\bigcup }_{j\in J}{U}_j=Y$

A closed subspace of a compact space is compact.

A compact subspace of a Hausdorff Space is closed.

The image of a compact space under a continuous map is compact.

Consider a Bijective continuous function $f:(X,{\mathcal{T}}_X)\to (Y,{\mathcal{T}}_Y)$ between two topological spaces. If $X$ is a compact space and $Y$ is a Hausdorff Space, then $f$ is a Homeomorphism

Tychonoff's Theorem

Definition

The Product Topology of any collection of compact topological spaces is compact.

Link to original

Consider a Topological Space $(X,\mathcal{T})$. $X$ is compact if and only if for every collection $\{C_i{\}}_{i\in I}\text{s.t.}(X\setminus C_i)\in \mathcal{T}$ of closed sets in $X$ that have the Finite Intersection Property, its entire intersection is a non-empty set $\bigcap _{i\in I}{C}_i\ne \varnothing$.

Every closed interval in Real Number $\mathbb{R}$ is compact.

Heine-Borel Theorem

Definition

Consider a Standard Topology on a Euclidean Space $({\mathbb{R}}^n,\mathcal{U})$ and a subset $A\subset {\mathbb{R}}^n$ Then, $A$ is closed and bounded if and only if $A$ is compact

Link to original

Consider a Topological Space $(X,\mathcal{T})$. If $X$ is compact then $X$ is Limit Point Compact

Consider a metrizable space $(X,\mathcal{T})$. Then, $X$ is compact if and only if $X$ is Limit Point Compact if and only if $X$ is Sequentially Compact

Every Compact metrizable space $(X,\mathcal{T})$ has a countable basis.

Link to original

A Compact Hausdorff Space is a normal space.

Link to original

Consider a Hausdorff Space $(X,\mathcal{T})$ and disjoint Compact subsets $A,B\subset X\text{s.t.}A\cap B=\varnothing$. Then, there exists disjoint open sets $U,V\in \mathcal{T}\text{s.t.}U\cap V=\varnothing$ satisfying $A\subset U$ and $B\subset V$.

Every compact space is Countably Compact.

Every Compact space has Bolzano–Weierstrass property.

Link to original

Every Compact space is locally compact.

Link to original

A Topological Space $(X,\mathcal{T})$ is Compact if $X$ has a basis $\mathcal{B}$ such that every open covering of $X$ by elements of $\mathcal{S}$ has a finite subcover.

Alexander Subbasis Theorem

Definition

A Topological Space $(X,\mathcal{T})$ is Compact if and only if $X$ has a Subbasis $\mathcal{S}$ such that every open covering of $X$ by elements of $\mathcal{S}$ has a finite subcover.

Link to original

Link to original

Heine-Borel Theorem

Definition

Consider a Standard Topology on a Euclidean Space $({\mathbb{R}}^n,\mathcal{U})$ and a subset $A\subset {\mathbb{R}}^n$ Then, $A$ is closed and bounded if and only if $A$ is compact

Link to original

Product Topology

Definition

A product topology is the Cartesian product of a family of topological spaces

Let $i\in I$ be an index set, and $X_i$ be a Topological Space. The product topology is defined as $X:={\prod }_{i\in I}{X}_i=\left\{x:I\to {\bigcup }_{i\in I}{X}_i|\forall i\in I,x_i\in X_i\right\}$ where $x_i$ is the $i$-th coordinate (component) of the function $x$.

Facts

Consider bases ${\mathcal{B}}_X,{\mathcal{B}}_Y$ for the topologies on $X,Y$. Then, ${\mathcal{B}}_{X\times Y}=\{B_X\times B_Y|B_X\in {\mathcal{B}}_Y,B_Y\in {\mathcal{B}}_Y\}$ is a basis for the topology on $X\times Y$.

The countably infinite product space ${\mathbb{R}}^{\omega }=\prod _{n\in \mathbb{Z}}\mathbb{R}$ of real numbers with the Product Topology is metrizable.

Consider a function $f:Y\to \prod _{i\in I}{X}_i$ between a Topological Space and a product space. Then, the function $f$ is continuous if and only if each Composite Function ${\pi }_i\circ f$ of the function $f$ and the Projection Map ${\pi }_i$ is continuous. $f\in C^0⟺\forall i\in I,{\pi }_i\circ f\in C^0$

The Product Space of any collection of Hausdorff spaces is a Hausdorff space.

Link to original

The Product Space of any collection of connected spaces is a connected space.

Link to original

The Product Space of two separable spaces is a separable space.

Link to original

The Product Space of two first-countable spaces is a first-countable space.

Link to original

The Product Space of two second-countable spaces is a second-countable space.

Link to original

Tychonoff's Theorem

Definition

The Product Topology of any collection of compact topological spaces is compact.

Link to original

Link to original

Tychonoff's Theorem

Definition

The Product Topology of any collection of compact topological spaces is compact.

Link to original

Connected Space

Definition

A Topological Space $(X,\mathcal{T})$ is connected if it can not be represented as the union of two disjoint, non-empty, open or closed subsets. $\nexists A,B\in \mathcal{T}\text{s.t.}A,B\ne \varnothing \text{and}A\uplus B=X⟺\nexists (X\setminus A),(X\setminus B)\in \mathcal{T}\text{s.t.}A,B\ne \varnothing \text{and}A\uplus B=X$ where $\uplus$ is a disjoint union.

Or, equivalently, if $\varnothing ,X$ are the only open and closed subsets.

Examples

Topologist’s sine curve

Consider a Subspace Topology $(X,{\mathcal{T}}_X)$, where $X=\{(x,\sin (\frac{1}{x}))|0<x\le 1\}\cup (0\times [-1,1])$, of a Standard Topology $({\mathbb{R}}^2,\mathcal{U})$ on real plane. The Topological Space $(X,{\mathcal{T}}_X)$ is connected, but not path connected.

Consider a set $\{a,b\}$.

• The Topological Space with discrete topology $(X,\{\varnothing ,a,b,X\})$ is not connected.
• The Topological Space with trivial topology $(X,\{\varnothing X\})$ is connected and path connected by a path $f=\{\begin{array}{ll}a& [0,1)\\ b& 1\end{array}$.

Consider a Subspace Topology $(\mathbb{Q},{\mathcal{T}}^{\prime })$ of a Standard Topology $(\mathbb{R},\mathcal{U})$ on real number. The Topological Space $(\mathbb{Q},{\mathcal{T}}^{\prime })$ is not connected by a separation $\{(\mathbb{Q}\cap (-\infty ,\sqrt{2})),(\mathbb{Q}\cap (\sqrt{2},\infty ))\}$

Consider a Subspace Topology $(X,{\mathcal{T}}_X)$, where $X=\{(x,y)|y=0\}\cup \{(x,\frac{1}{x}|x>0\}$, of a Standard Topology $({\mathbb{R}}^2,\mathcal{U})$ on real plane. The Topological Space $(X,{\mathcal{T}}_X)$ is not connected by a separation $\{U,V\}$.

Facts

Every path connected space is a Connected Space.

Link to original

Consider a Subspace Topology $(Y,{\mathcal{T}}_Y)$ of a Topological Space $(X,\mathcal{T})$. Then, $A,B\in {\mathcal{T}}_Y\text{s.t.}A,B\ne \varnothing \text{and}A\uplus B=Y$ is a separation of $Y$ if and only if $A\uplus B=Y\text{and}{A}^{\prime }\cap B=A\cap B^{\prime }=\varnothing$. where $\uplus$ is a disjoint union, $A^{\prime }$ is the set of all limit points of $A$.

Consider a Subspace Topology $(Y,{\mathcal{T}}_Y)$ of a Topological Space $(X,\mathcal{T})$ and a separation $\{C,D\}$ of $X$. If $(Y,{\mathcal{T}}_Y)$ is a connected subspace, then $Y\subset C\text{or}Y\subset D$.

Consider a collection of connected subspaces $\{U_i{\}}_{i\in I}\text{s.t.}{U}_i\subset X$ of a Topological Space $(X,\mathcal{T})$. If the subspaces have a point in common $\exists x\in X,\text{s.t.}x\in \bigcap _{i\in I}{U}_i\iff \bigcap _{i\in I}{U}_i\ne \varnothing$, then the union of the collection $\bigcup _{i\in I}{U}_i$ is connected.

Consider a collection of connected subspaces $\{U_i{\}}_{i\in I}\text{s.t.}{U}_i\subset X$ of a Topological Space $(X,\mathcal{T})$, and a connected subspace $B$. If $\forall i\in I,U_i\cap B\ne \varnothing$, then $B\cup \left(\bigcup _{i\in I}{U}_i\right)$ is connected.

Consider a connected Subspace Topology $(A,{\mathcal{T}}_A)$ of a Topological Space $(X,\mathcal{T})$. For some Subspace Topology $B$, if $A\subseteq B\subseteq A^{\prime }$, then $B$ is connected.

Consider two topological spaces $(X,{\mathcal{T}}_X),(Y,{\mathcal{T}}_Y)$. If $(X,{\mathcal{T}}_X)$ is connected and there exists a Continuous Function $f:X\to Y$, then $Y$ is a connected space.

Consider a continuous function $f:(X,{\mathcal{T}}_X)\to (Y,{\mathcal{T}}_Y)$ between two topological spaces. If $(X,{\mathcal{T}}_X)$ is connected, then $f(X)$ is a connected subspace in $(Y,{\mathcal{T}}_Y)$.

Consider a Topological Space $(X,\mathcal{T})$ and a subspace $Y\subset X$. If $Y$ is connected, then its Closure $\bar{Y}$ is also connected.

The Product Space of any collection of connected spaces is a connected space.

Link to original

Topological Manifold

Definition

$(M,\mathcal{T})$ A Locally Euclidean second-countable Hausdorff Space Topological Space $(M,\mathcal{T})$ is a topological manifold.

A one-dimensional manifold is called a curve, and a two-dimensional manifold is called a surface.

Facts

The Product Space of an $n$-dimensional manifold and an $m$-dimensional manifold is an $(n+m)$-dimensional manifold.

Consider an $n$-dimensional manifold without boundary $X$ and an $m$-dimensional manifold with boundary $Y$. Then, $\partial (X\times Y)=X\times \partial Y$

Link to original

Second-Countable Space

Definition

A second-countable space is a Topological Space whose Topology has a countable basis.

Facts

Every second-countable space is a Separable Space.

$n$-dimension Euclidean Space ${\mathbb{R}}^2$ where $n\in \mathbb{N}$, is a second-countable space.

Hilbert Space $H$ is a second-countable space.

The Product Space of two second-countable spaces is a second-countable space.

Every Second-Countable Space is a Lindelof space.

Link to original

Link to original

Hausdorff Space

Definition

A Topological Space $(X,\mathcal{T})$ is Hausdorff space if $\forall x,y\in X\text{s.t.}x\ne y,\exists {\mathcal{N}}_x,{\mathcal{N}}_y\text{s.t.}{\mathcal{N}}_x\cap {\mathcal{N}}_y=\varnothing$ where ${\mathcal{N}}_x$ and ${\mathcal{N}}_y$ are the neighbourhoods of $x$ and $y$ respectively.

Facts

Every finite point set in Hausdorff space is closed ($\because$ T1 Axiom).

Consider a Topological Space $(X,\mathcal{T})$ satisfying $T_2$ axiom. Then, $X\setminus {\bigcup }_{i=1}^n{x}_i\in \mathcal{T}$ where $x_i\in X$

Consider a $T_2$ Topological Space $(X,\mathcal{T})$. Then, a Sequence of points of $X$ converges to at most one point of $X$. $\forall (x_n{)}_{i=1}^{\infty }\subset X\text{and}\forall x,y\in X,(x_n\to x\text{and}{x}_n\to y)\Rightarrow x=y$

Every totally ordered set is a Hausdorff space in the Order Topology.

A Subspace Topology of a Hausdorff space is a Hausdorff space (Hereditary Property).

The Product Space of any collection of Hausdorff spaces is a Hausdorff space.

A Compact Hausdorff Space is a normal space.

Link to original

Link to original

Whitney Embedding Theorem

Definition

Any $m$-dimensional smooth manifold $\mathcal{M}$ can be embedded in ${\mathbb{R}}^{2m+1}$

Link to original

Riemannian Manifold

Definition

A Riemannian manifold is a smooth Topological Manifold together with a Riemannian metric. Many geometric notions such as distance, angles, length, volume, and curvature are defined on a Riemannian manifold.

Let $\mathcal{M}$ be a Smooth Manifold. For each point $p\in \mathcal{M}$, there is an associated vector space $T_p(\mathcal{M})$ called Tangent Space of $\mathcal{M}$ at $p$. Each Tangent Space $T_p(\mathcal{M})$ equipped with an Inner product $g_p:T_p(\mathcal{M})\times T_p(\mathcal{M})\to \mathbb{R}$ defined by the basis of the tangent space. $g_{n\times n}=(g_{ij}),g_{ij}{|}_p:=⟨{\partial }_i,{\partial }_j⟩$ Where $⟨\cdot ,\cdot ⟩$ is a standard inner product of the ambient space (Euclidean inner product).

The collection of inner products $g=\{g_p|p\in \mathcal{M}\}$ is a Riemannian metric on $\mathcal{M}$, and the pair of the manifold $\mathcal{M}$ and the Riemannian metric $g$ defines a Riemannian manifold. $(\mathcal{M},g)$

Link to original

Atlas

Definition

Atlas

An atlas on a Topological Manifold $\mathcal{M}$ is a collection of charts which covers $\mathcal{M}$. $\{(U_{\alpha },{\phi }_{\alpha })|\alpha \in I\},\text{s.t.}{\bigcup }_{\alpha \in I}{U}_{\alpha }=M$

Link to original

Chart

Definition

Let $\mathcal{M}$ be a Topological Manifold. A chart for the manifold is a Homeomorphism $\phi :U\subset \mathcal{M}\to V\subset {\mathbb{R}}^n$, where $U$ is an open subset of the manifold, and $V$ is an open subset of the Euclidean Space. $(U,\phi )$

Link to original

Differentiable Manifold

Definition

Let $\mathcal{M}$ be a Topological Manifold. It is $k$-times differentiable if the following condition holds: $\forall (U_1,{\phi }_1),(U_2,{\phi }_2),U_1\cap U_2\ne \varnothing ,{\phi }_2\circ {\phi }_1^{-1}\in C^k$ where $C^k$ is Differentiability Class.

Link to original

Smooth Manifold

Definition

A smooth manifold is an infinitely Differentiable Manifold ($C^{\infty }$).

Facts

The Product Space of an $n$-dimensional smooth manifold and an $m$-dimensional smooth manifold is an $(n+m)$-dimensional smooth manifold.

Consider an $n$-dimensional smooth manifold without boundary $X$ and an $m$-dimensional smooth manifold with boundary $Y$. Then, $\partial (X\times Y)=X\times \partial Y$

Link to original

Diffeomorphism

Definition

Given two differentiable manifolds $M$ and $N$, a differentiable map $f:M\to N$ is a diffeomorphism if it is a Bijective and its inverse $f^{-1}$ is differentiable as well.

If these functions are $r$ times continuously differentiable, $f$ is called $C^r$-diffeomorphism

If there is a diffeomorphism $f:M\to N$ between two manifolds $M$ and $N$, we call these two manifolds are diffeomorphic and denote as $M\simeq N$

Link to original

Tangent Space

Definition

Suppose that $\mathcal{M}$ is a Differentiable Manifold and that $x\in \mathcal{M}$. Pick a coordinate Chart $\phi :U\to {\mathbb{R}}^n,\phi (p)=(x_1(p),x_2(p),\dots ,x_n(p))$, where $U$ is an open subset of $\mathcal{M}$ containing $x$. The tangent space $T_p(\mathcal{M})$ is the set of all tangent vectors at $p$ on the manifold $\mathcal{M}$.

The basis of the tangent plane is given by the partial derivatives ${\partial }_i=\frac{\partial {\phi }^{-1}}{\partial x_i},i=1,\dots ,n$

Link to original

Integration of a Function over a Manifold

Definition

Consider a scalar function $f:\mathcal{M}\to \mathbb{R}$ and a Riemannian Manifold $(\mathcal{M},g)$ with a local Chart $\phi :\mathcal{M}\to {\mathbb{R}}^n$. The integral of $f$ over manifold $\mathcal{M}$ can be calculated in a local coordinate space. ${\int }_{\mathcal{M}}fds={\int }_U\tilde{f}\sqrt{|g|}dx$ where $\tilde{f}:=f\circ {\phi }^{-1}$, $U=\phi (\mathcal{M})$, and $|g|$ is the absolute value of the Determinant of the inner product at ${\phi }^{-1}(x)$

Link to original

Isometry

Definition

Let two Riemannian manifolds $(M,g^M)$ and $(N,g^N)$, and a Diffeomorphism $f:M\to N$. Then $f$ is called an isometry if the following condition holds: $\forall p\in M,\mathbf{u},\mathbf{v}\in T_p(M),g^M(\mathbf{u},\mathbf{v})=g^N(f(\mathbf{u}),f(\mathbf{v}))$

Link to original

Geodesic

Definition

A geodesic is a curve representing the shortest path between two points in a Riemannian Manifold.

Suppose a Riemannian Manifold $(\mathcal{M},g)$. A differentiable curve in $\mathcal{M}$ is defined as a smooth mapping $\gamma :\mathbb{R}\to \mathcal{M}$ from an open interval $({\lambda }_0,{\lambda }_1)\subset \mathbb{R}$ into $\mathcal{M}$. The distance of a smooth curve is given by Arc Length $L(\gamma )={\int }_{{\lambda }_0}^{{\lambda }_1}\sqrt{g_{\gamma (t)}({\gamma }^{\prime }(t),{\gamma }^{\prime }(t))}dt$ The distance between two points $p$ and $q$ on $\mathcal{M}$ is defined as the Infimum of the length taken over all differentiable curves $\gamma :({\lambda }_0,{\lambda }_1)\to \mathcal{M}$ such that $\gamma ({\lambda }_0)=p$ and $\gamma ({\lambda }_1)=q$. $d^{\mathcal{M}(p,q)}={\inf }_{\gamma \in C(p,q)}L(\gamma )$ where $C(p,q)$ is the set of all differentiable curves in $\mathcal{M}$ that join up the points $p$ and $q$.

Link to original

Laplace-Beltrami Operator

Definition

The Laplace–Beltrami operator is the Divergence of the Gradient. $\mathcal{L}(f)=\mathrm{div}(\nabla f)=\frac{1}{\sqrt{|g|}}\sum _{i=1}^n\sum _{j=1}^n\frac{\partial }{\partial x_i}(\sqrt{|g|}\cdot g^{ij}\cdot \frac{\partial \tilde{f}}{\partial x_j})$ where $\tilde{f}=(f\circ {\phi }^{-1})$, and $|g|$ is the absolute value of the Determinant of the inner product $g$ at ${\phi }^{-1}(x)$

Calculations

Calculation of Gradient

Consider an $n$-dimensional Riemannian Manifold $(\mathcal{M},g)$ with a local Chart $\phi :\mathcal{M}\to {\mathbb{R}}^n$, and a function $f:\mathcal{M}\to \mathbb{R}$.

By the definition of the Gradient, ${\nabla }_{\mathbf{v}}f(p)=g_p(\mathbf{v},\nabla f(p))=\sum _{i=1}^n\sum _{j=1}^n{g}_{ij}{v}_i{a}_j$ where $g_p$ is the inner product at $p$, and $v_i$ and $a_j$ are the $i$-th and $j$-th element of the vector $\mathbf{v}$ and gradient vector $\nabla f(p)$ respectively.

By Chain Rule, The directional derivative of $f$ at a point $p\in \mathcal{M}$ in the direction of $\mathbf{v}$ is given by ${\nabla }_{\mathbf{v}}f(p)=\sum _{i=1}^n{v}_i\frac{\partial \tilde{f}}{\partial x_i}$ where $\tilde{f}=(f\circ {\phi }^{-1})$

By combining these two equations, we can obtain the following equality. $\sum _{j=1}^n{g}_{ij}{a}_j=\frac{\partial \tilde{f}}{\partial x_i},\forall i=1,\dots ,n$ $g\mathbf{a}=\nabla \tilde{f}$ Let $g^{ij}$ be the inverse matrix of $g$, then $\mathbf{a}=g^{ij}\nabla \tilde{f}$ The gradient vector is $\nabla f(p)=\sum _{i=1}^n\sum _{j=1}^n{g}^{ij}\frac{\partial \tilde{f}}{\partial x_j}{\partial }_i$ where ${\partial }_i=\frac{\partial {\phi }^{-1}}{\partial x_i}$

Calculation of Divergence

Consider an $n$-dimensional Riemannian Manifold $(\mathcal{M},g)$ with a local Chart $\phi :\mathcal{M}\to {\mathbb{R}}^n$, and a function $f:\mathcal{M}\to \mathbb{R}$.

By the Divergence Theorem, for a function $f$ with a compact support and a vector field $V$, $⟨V,\nabla f⟩=-⟨\mathrm{div}V,f⟩$ In a Euclidean Space, the integration of both sides are ${\int }_{{\mathbb{R}}^n}f\cdot \mathrm{div}Vdx=-{\int }_{{\mathbb{R}}^n}⟨\nabla f,V⟩$ The integration can be performed over a coordinate Chart of the manifold.^[Integration of a Function over a Manifold] By the Integration by Parts,

\int_{\mathbb{R}^{n}} \tilde{f} \cdot \operatorname{div}V \sqrt{|g|} dx &= - \int_{\mathbb{R}^{n}} g(\nabla f, V) \sqrt{|g|} dx\\ &= - \int_{\mathbb{R}^{n}} \sum\limits_{i=1}^{n} V_{i} \frac{\partial\tilde{f}}{\partial x_{i}} \sqrt{|g|} dx\\ &= - \int_{\mathbb{R}^{n}} \tilde{f} \sum\limits_{i=1}^{n} \frac{\partial}{\partial x_{i}} (V_{i} \sqrt{|g|}) dx \end{aligned}$$ where $\tilde{f} := f \circ \varphi^{-1}$, $U = \varphi(\mathcal{M})$, $|g|$ is the absolute value of the [[Determinant]] of the inner product $g$ at $\varphi^{-1}(x)$, and $V_{i}$ is the $i$-th element of the vector $V$. Therefore, we have $$\operatorname{div}V = \frac{1}{\sqrt{|g|}} \sum\limits_{i=1}^{n} \frac{\partial}{\partial x_{i}} (V_{i} \sqrt{|g|})$$Link to original

Linear Manifold Learning

Principal Component Analysis

Definition

PCA is a linear dimensionality reduction technique. The correlated variables are linearly transformed onto a new coordinate system such that the directions capturing the largest variance in the data.

Population Version

Given a random vector $\mathbf{x}$, we find a $\mathbf{\alpha }$ such that $\mathrm{Var}({\mathbf{\alpha }}^{⊺}\mathbf{x})$ is maximized: $\underset{\mathbf{\alpha }}{\mathrm{argmax}}\mathrm{Var}({\mathbf{\alpha }}^{⊺}\mathbf{x})\text{s.t.}{\mathbf{\alpha }}^{⊺}\mathbf{\alpha }=1$ Equivalently, by the Method of Lagrange Multipliers with ${\mathbf{\alpha }}^{⊺}\mathbf{\alpha }=1$, $\underset{\mathbf{\alpha }}{\mathrm{argmax}}{\mathbf{\alpha }}^{⊺}\Sigma \mathbf{\alpha }-\lambda ({\mathbf{\alpha }}^{⊺}\mathbf{\alpha }-1)$ By differentiation, the $\mathbf{\alpha }$ is given by the eigen value problem $\Sigma \mathbf{\alpha }=\lambda \mathbf{\alpha }$ Thus the $\mathbf{\alpha }$ maximizing the variance of ${\mathbf{\alpha }}^{⊺}\mathbf{x}$ is the eigenvector corresponding to the largest Eigenvalue.

Sample Version

Given a data matrix $\mathbf{X}$, by Singular Value Decomposition, A matrix $\mathbf{X}$ can be factorized as $\mathbf{X}=\mathbf{UD}{\mathbf{V}}^{⊺}$. By algebra, $\mathbf{XV}=\mathbf{UD}=:\mathbf{Z}\Rightarrow \mathbf{X}{\mathbf{v}}_i=d_i{\mathbf{u}}_i=:{\mathbf{z}}_i$, where we call ${\mathbf{z}}_i$ the $i$-th principal component.

Facts

Since $\mathrm{Var}({\mathbf{z}}_i)=\mathrm{Var}(\mathbf{X}{\mathbf{v}}_i)=\frac{d_i^2}{n}$ and $d_1\ge d_2\ge \cdots \ge d_p\ge 0$ $\mathrm{Var}({\mathbf{z}}_1)\ge \mathrm{Var}({\mathbf{z}}_2)\ge \cdots \ge \mathrm{Var}({\mathbf{z}}_p)\ge 0$

Link to original

Robust Principal Component Analysis

Definition

PCA doesn’t work well when there are noises in the input data. The goal of Robust PCA is to find a matrix decomposition to a low rank matrix and a sparse matrix.

The optimization problem of Robust PCA is set up as $\underset{L,S}{\mathrm{argmin}}\mathrm{rank}(L)+\lambda ||S|{|}_0\text{s.t.}X=L+S$ where $L$ is a low-rank matrix, $S$ is a sparse matrix, and $||\cdot |{|}_0$ is the number of non-zero elements in the matrix.

However, the optimization problem is infeasible because it is neither continuous nor convex. So, we solve the relaxed problem $\underset{L,S}{\mathrm{argmin}}||L|{|}_{\ast }+\lambda ||S|{|}_1\text{s.t.}X=L+S$ where $||\cdot |{|}_{\ast }$ is the Nuclear Norm of the matrix, and $||\cdot |{|}_1$ is the matrix L1 norm.

Applications

• Video Surveillance
• Face Recognition
• Latent Semantic Indexing
• Collaborative Filtering (Matrix Completion)

Link to original

Nonlinear Manifold Learning

Kernel Principal Component Analysis

Definition

Consider an $n\times p$ demeaned matrix $\mathbf{X}$ By SVD $\mathbf{X}=\mathbf{UD}{\mathbf{V}}^{⊺}$, where $\mathbf{U},\mathbf{V}$ are orthonormal matrices and $\mathbf{D}$ is a Diagonal Matrix. Then, $\mathbf{X}{\mathbf{X}}^{⊺}=\mathbf{UD}{\mathbf{V}}^{⊺}(\mathbf{UD}{\mathbf{V}}^{⊺}{)}^{⊺}=\mathbf{U}{\mathbf{D}}^2{\mathbf{U}}^{⊺}$ By PCA $\mathbf{Z}:=\mathbf{XV}=\mathbf{UD}$. For a linear kernel $\mathbf{K}=\mathbf{X}{\mathbf{X}}^{⊺}$, $\mathbf{K}=\mathbf{Z}D{\mathbf{U}}^{⊺}\Rightarrow K(D{\mathbf{U}}^{⊺}{)}^{-1}=\mathbf{Z}$. $\because \mathbf{U}$ is an Orthonormal Matrix, $\mathbf{Z}=\mathbf{KU}{\mathbf{D}}^{-1}\iff {\mathbf{z}}_{im}=\sum _{j=1}^n\frac{{\mathbf{u}}_{jm}}{d_m}K({\mathbf{x}}_i,{\mathbf{x}}_j)$ The kernel principal components are given by solution of the optimization problem. $\underset{g_i\in {\mathcal{H}}_K}{\max }\mathrm{Var}{g}_i(\mathbf{X})\text{subject to}||g_i|{|}_{{\mathcal{H}}_K}=1,\forall j<i,⟨g_i,g_j{⟩}_{{\mathcal{H}}_K}=0$ where $g_i(\mathbf{x})=\sum _{j=1}^n\frac{{\mathbf{u}}_{ji}}{d_i}K(\mathbf{x},{\mathbf{x}}_j)$

Link to original

Self-Organizing Map

Definition

A self-organizing map (SOM) is a clustering method that produces a low-dimensional representation of a higher-dimensional data set while preserving the Topological Manifold structure of the data.

The algorithm fits a grid to high-dimensional data and assigns the data to the fitted nodes (prototypes) of the grid.

Link to original

Isomap

Definition

Isomapis a non-linear dimensional reduction method that aims to preserve the intrinsic geometry of high-dimensional data in a lower-dimensional space. The main idea of isomap is to approximate the geodesic distances between data points on a manifold, rather than just using straight-line Euclidean distances.

Algorithm

1. Determine the neighbors of each point
   • All points in some fixed radius
   • k-nearest neighbors
2. Construct a neighborhood distnace graph
3. Compute the shortest path between two nodes with Dijkstra’s algorithm.

Link to original

Locally Linear Embedding

Definition

Locally linear embedding (LLE) is a non-linear dimensional reduction method that aims to preserve the intrinsic geometry of high-dimensional data in a lower-dimensional space.

Algorithm

1. Determine the k-nearest neighbors of each point

2. Compute a set of weights for each point that best approximates the point as a linear combination of its neighbors. $\underset{W}{\mathrm{argmin}}\sum _{i=1}^n[x_i-\sum _{j:x_i\in N_{x_i}}{W}_{ij}{x}_j{]}^2\text{subject to}\sum _{j:x_i\in N_{x_i}}{W}_{ij}=1,\forall i=1,\dots ,n$ where $x_i$ is a data point vector, $W$ is $n\times k$ matrix, and $N_{x_i}$ is the set of the neighbors of $x_i$

3. Find the low-dimensional embedding of points by solving Eigenvalue problem. Where each point is still described with the same linear combination of its neighbors. $\underset{\mathbf{y}}{\mathrm{argmin}}\sum _{i=1}^n[y_i-\sum _{j:x_i\in N_{x_i}}{W}_{ij}{y}_j{]}^2\text{subject to}\frac{1}{n}{\mathbf{y}}^{⊺}\mathbf{y}=I$ where $y_i$ is a vector has lower dimension than $x_i$, and $W$ is the matrix obtained by the step 2.

   In a matrix notation, the problem is written as $\underset{\mathbf{y}}{\mathrm{argmin}}{\mathbf{y}}^{⊺}M\mathbf{y}\text{subject to}\frac{1}{n}{\mathbf{y}}^{⊺}\mathbf{y}=I$ where $M=(I-W{)}^{⊺}(I-W)$

   By the Method of Lagrange Multipliers, the solution of the optimization problem is given as $M\mathbf{y}=\mathbf{y}\Lambda$ Therefore, $\mathbf{y}$ consists of eigenvectors corresponding to the $p$-smallest eigenvalues.

Link to original

Multidimensional Scaling

Definition

Multidimensional Scaling (MDS) is a non-linear dimensional reduction method. It aims to represent high-dimensional data in a lower-dimensional space while preserving the pairwise distances

Algorithm

MDS

1. Find a low-dimensional $\mathbf{y}$ that minimizes the difference in the pairwise distance of points. $\underset{\mathbf{y}}{\mathrm{argmin}}\sum _{i=1}^n\sum _{j\ne i=1}^n[d(x_i,x_j)-d(y_i,y_j){]}^2$ where $x_i$ is a data point vector,$d(\cdot ,\cdot )$ is a distance function.

Local MDS

1. Build a set of nearby pairs $N=\{(i,j)|x_j\in N_i\text{or}{x}_i\in N_j\}$ where $N_i$ is the set of the k-nearest neighbors of $x_i$
2. Find a low-dimensional $\mathbf{y}$ that minimizes the difference in the local pairwise distance of points. $\underset{\mathbf{y}}{\mathrm{argmin}}\sum _{(i,j)\in N}[d(x_i,x_j)-d(y_i,y_j){]}^2+\sum _{(i,j)\notin N}\lambda [D-d(y_i,y_j){]}^2$ where $x_i$ is a data point vector,$d(\cdot ,\cdot )$ is a distance function, $D$ is a matrix with very large value, and $\lambda$ is a small value weight often $\frac{1}{D}$.

Link to original

Adjacency Matrix

Definition

Consider a Graph with $n$ nodes $X_1,X_2,\dots ,X_n$.

Unweighted Adjacency Matrix

An unweighted adjacency matrix $A$ is $n\times n$ matrix such that its element $a_{ij}$ is one when there is edge from node $X_i$ to $X_j$ and zero when there is no edge.

Weighted Adjacency Matrix

An unweighted adjacency matrix $A$ is $n\times n$ matrix such that its element $a_{ij}$ is the weight of the edge between $X_i$ and $X_j$, and is zero when there is no edge.

Examples

Given graph

Adjacency matrix $A=\left(\begin{array}{cccccc}2& 1& 0& 0& 1& 0\\ 1& 0& 1& 0& 1& 0\\ 0& 1& 0& 1& 0& 0\\ 0& 0& 1& 0& 1& 1\\ 1& 1& 0& 1& 0& 0\\ 0& 0& 0& 1& 0& 0\end{array}\right)$

Facts

If a graph is undirected, then the adjacency matrix is Symmetric Matrix

Link to original

Degree Matrix

Definition

The degree matrix of an undirected Graph is a Diagonal Matrix representing the sum of the weight of edges connected to each node. It is used together with the Adjacency Matrix to construct the Laplacian Matrix of a graph.

Given a graph $G$ and the corresponding Adjacency Matrix $A=(a_{ij})$. The degree matrix is defined as $\mathbf{D}:=\mathrm{diag}(d_1,d_2,\dots ,d_n)$ where $d_i:=\sum _{j=1}^n{a}_{ij}$,

Examples

Given graph

Degree matrix $D=\left(\begin{array}{cccccc}4& 0& 0& 0& 0& 0\\ 0& 3& 0& 0& 0& 0\\ 0& 0& 2& 0& 0& 0\\ 0& 0& 0& 3& 0& 0\\ 0& 0& 0& 0& 3& 0\\ 0& 0& 0& 0& 0& 1\end{array}\right)$

Link to original

Laplacian Matrix

Definition

The Laplacian matrix is a matrix representation of a Graph. $L=D-A$ where $D$ is the Degree Matrix, and $A$ is the Adjacency Matrix of the graph.

Random Walk Normalized Laplacian Matrix

${\mathbf{L}}^{\text{rw}}={\mathbf{D}}^{-1}\mathbf{L}$

Symmetrically Normalized Laplacian Matrix

${\mathbf{L}}^{\text{sym}}={\mathbf{D}}^{-1/2}\mathbf{L}{\mathbf{D}}^{-1/2}$

Examples

Laplacian Matrix for Simple Graph

Adjacency Matrix and Degree Matrix $A=\left(\begin{array}{cccccc}0& 1& 0& 0& 1& 0\\ 1& 0& 1& 0& 1& 0\\ 0& 1& 0& 1& 0& 0\\ 0& 0& 1& 0& 1& 1\\ 1& 1& 0& 1& 0& 0\\ 0& 0& 0& 1& 0& 0\end{array}\right),D=\left(\begin{array}{cccccc}2& 0& 0& 0& 0& 0\\ 0& 3& 0& 0& 0& 0\\ 0& 0& 2& 0& 0& 0\\ 0& 0& 0& 3& 0& 0\\ 0& 0& 0& 0& 3& 0\\ 0& 0& 0& 0& 0& 1\end{array}\right)$

Laplacian matrix $L=D-A=\left(\begin{array}{cccccc}2& -1& 0& 0& -1& 0\\ -1& 3& -1& 0& -1& 0\\ 0& -1& 2& -1& 0& 0\\ 0& 0& -1& 3& -1& -1\\ -1& -1& 0& -1& 3& 0\\ 0& 0& 0& -1& 0& 1\end{array}\right)$

Laplacian Matrix for Graph with Weighted Edges

Adjacency Matrix and Degree Matrix $A=\left(\begin{array}{cccc}0& 1& 2& 3\\ 1& 0& 0& 0\\ 2& 0& 0& 4\\ 3& 0& 4& 0\end{array}\right),D=\left(\begin{array}{cccc}6& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 6& 0\\ 0& 0& 0& 7\end{array}\right),$

Laplacian matrix $L=D-A=\left(\begin{array}{cccc}6& -1& -2& -3\\ -1& 1& 0& 0\\ -2& 0& 6& -4\\ -3& 0& -4& 7\end{array}\right)$

Facts

The number of zero-eigenvalues of the Laplacian matrix equals the number of connected clusters in the graph.

Analogousness to the Laplace-Beltrami Operator

The Laplacian matrix on a graph, $\mathbf{L}$ can be ragarded as a discrete approximation to the Laplace-Beltrami Operator on a manifold.

The quadratic form of the Laplacian Matrix can be seen as a discretization of squared gradient on manifold.

${\mathbf{z}}^{⊺}\mathbf{Lz}=\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{a}_{ij}({\mathbf{z}}_i-{\mathbf{z}}_j{)}^2=\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n\left(\frac{{\mathbf{z}}_i-{\mathbf{z}}_j}{d_{ij}}\right)\approx {\int }_{\mathcal{M}}||\nabla f(x)|{|}^2={\int }_{\mathcal{M}}\mathcal{L}(f)\cdot f$ where $d_{ij}^2:=\frac{1}{a_{ij}}$ is a distance between two points ${\mathbf{x}}_i$ and ${\mathbf{x}}_j$ defined by the Adjacency Matrix.

Link to original

Laplacian Eigenmap

Definition

The Laplacian eigenmap is an embedding preserving local information optimally.

Algorithm

Consider a set of data points ${\mathbf{x}}_1,{\mathbf{x}}_2,\dots ,{\mathbf{x}}_n\in {\mathbb{R}}^l$. Make an Adjacency Matrix with Gaussian Radial Basis Function Kernel $\mathbf{A}=(a_{ij}):=\exp (-||{\mathbf{x}}_i-{\mathbf{x}}_j|{|}^2/c)$ where $c>0$ is a scale parameter.

Construct a Laplacian Matrix using the Adjacency Matrix. The following options are available.

• Unnormalized Laplacian Matrix $L=D-A$
• Random Walk Normalized Laplacian Matrix ${\mathbf{L}}^{\text{rw}}={\mathbf{D}}^{-1}\mathbf{L}$
• Symmetrically Normalized Laplacian Matrix ${\mathbf{L}}^{\text{sym}}={\mathbf{D}}^{-1/2}\mathbf{L}{\mathbf{D}}^{-1/2}$

Construct the matrix $\mathbf{Z}=[{\mathbf{z}}_1,{\mathbf{z}}_2,\dots ,{\mathbf{z}}_m]$ whose columns are eigenvectors corresponding to the $m$-smallest eigenvalues of the Laplacian Matrix. It is the result of Laplacian eigenmap ${\mathbf{x}}_i\in {\mathbb{R}}^l\to [{\mathbf{z}}_2,{\mathbf{z}}_3,\dots ,{\mathbf{z}}_m{]}_i\in {\mathbb{R}}^m$ where $m\le l$, and ${\mathbf{z}}_1$ is intentionally omitted because it corresponds to the trivial solution (constant vector).

Link to original

Spectral Clustering

Definition

Spectral clustering technique make use of spectrum of the similarity matrix of the data to perform dimensionality reduction before clustering.

Algorithms

Apply Laplacian Eigenmap to the given data ${\mathbf{x}}_1,{\mathbf{x}}_2,\dots ,{\mathbf{x}}_n\in {\mathbb{R}}^l$. ${\mathbf{x}}_i\in {\mathbb{R}}^l\to [{\mathbf{z}}_2,{\mathbf{z}}_3,\dots ,{\mathbf{z}}_m{]}_i\in {\mathbb{R}}^m$

Form an $n\times k$ sub matrix $\mathbf{T}$ using the first $k$-columns of the embedded matrix $\mathbf{Z}$, and normalize each row to norm $1$. $\mathbf{T}=[{\mathbf{z}}_1,{\mathbf{z}}_2,\dots ,{\mathbf{z}}_k]$

Apply clustering algorithm (e.g. K-Means Clustering) to ${\mathbf{t}}_1,{\mathbf{t}}_2,\dots ,{\mathbf{t}}_n$, where ${\mathbf{t}}_i$ is the $i$-th row of $\mathbf{T}$.

Mathematical Background

Consider a cluster assignment vector ${\mathbf{z}}_i$ for each data point. Then, clustering $n$ observations is corresponding to estimating ${\mathbf{z}}_i$‘s The entries $a_{ij}$ of the Adjacency Matrix represents the similarity between points $i$ and $j$.

Under the assumption that the close data points (large $a_{ij}$) have a similar label (${\mathbf{z}}_i\approx {\mathbf{z}}_j$), the optimization problem is set up that minimizing the difference between assignments for similar points. $\underset{\mathbf{Z}}{\mathrm{argmin}}\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{a}_{ij}({\mathbf{z}}_i-{\mathbf{z}}_j{)}^2\text{subject to}{\mathbf{Z}}^{⊺}\mathbf{Z}=I$ where the constraint is imposed to avoid the trivial solution ${\mathbf{z}}_i=0$.

In a matrix notation, the problem is $\underset{\mathbf{Z}}{\mathrm{argmin}}\mathrm{tr}({\mathbf{Z}}^{⊺}\mathbf{LZ})\text{subject to}{\mathbf{Z}}^{⊺}\mathbf{Z}=I$

When ${\mathbf{z}}_i\approx {\mathbf{z}}_j$, $a_{ij}$ is large and when ${\mathbf{z}}_i\ne {\mathbf{z}}_j$, $a_{ij}$ is small. So, $a_{ij}$ works as the weight for each pair in the optimization.

The Lagrangian function is defined as $L_P={\mathbf{Z}}^{⊺}\mathbf{LZ}-\Lambda ({\mathbf{Z}}^{⊺}\mathbf{Z}-1)$ And the solution of the problem is given by an Eigenvalue problem. $\frac{\partial L_p}{\partial \mathbf{Z}}=2\mathbf{LZ}-2\Lambda \mathbf{Z}=0\Rightarrow \mathbf{LZ}=\Lambda \mathbf{Z}\Rightarrow {\mathbf{Z}}^{⊺}\mathbf{LZ}=\Lambda$ The solution $\mathbf{Z}$ is an $n\times n$ matrix of eigenvectors sorted in ascending by their corresponding eigenvalues.

Link to original

t-Distributed Stochastic Neighbor Embedding

Definition

The t-distributed stochastic neighbor embedding (t-SNE) is a statistical method for visualizing high-dimensional data. It models each high-dimensional object by a two- or three-dimensional point in such a way that similar objects are modeled by nearby points and dissimilar objects are modeled by distant points with high probability.

Algorithm

1. Constructs a probability distribution over pairs of high-dimensional objects in such a way that similar objects are assigned a higher probability while dissimilar points are assigned a lower probability.

Define the conditional probability by Normal Distribution $p_{j|i}=\frac{\exp (-||{\mathbf{x}}_i-{\mathbf{x}}_j|{|}^2/2{\sigma }_i^2)}{\sum _{k\ne i}\exp (-||{\mathbf{x}}_i-{\mathbf{x}}_k|{|}^2/2{\sigma }_i^2)},\forall i\ne j$ where ${\sigma }_i$ acts as an adaptive bandwidth parameter for each point $i$, and is indirectly determined by the given hyperparameter (perplexity).

And define the probability $p_{ij}=\frac{p_{j|i}+p_{i|j}}{2N}$ where $n$ is the number of data set

2. Defines a similar probability distribution over the points in the low-dimensional map,

Define the similarities between two points in the low-dimensional map. $q_{ij}=\frac{(1+||{\mathbf{y}}_i-{\mathbf{y}}_j|{|}^2{)}^{-1}}{\sum _{k\ne i}(1+||{\mathbf{y}}_k-{\mathbf{y}}_l|{|}^2{)}^{-1}},\forall i\ne j$

3. Minimizes the Kullback-Leibler Divergence between the two distributions with respect to the locations of the points in the low-dimensional map.

$\underset{\mathbf{y}}{\mathrm{argmin}}KL(P||Q)=\sum _{i\ne j}{p}_{ij}\ln \left(\frac{p_{ij}}{q_{ij}}\right)$

Link to original

UMAP

Definition

Uniform manifold approximation and projection (UMAP) is a nonlinear dimensionality reduction algorithm similar to t-SNE. However, unlike to t-SNE, UMAP uses spectral embedding to initialize the low-dimensional graph, and uses a graph that only connected to each points’ nearest neighbors.

Algorithm

1. For each point in high-dimensional space, find its nearest neighbors.

2. Compute the distances between the nearest neighbors for each point.

$d(x_i,x_j)$

3. Calculate the local connectivity parameter ${\sigma }_i$ for each point using the equation $\sum _{j=1}^k\exp \left(-\frac{\max (0,d(x_i,x_j)-{\rho }_i)}{{\sigma }_i}\right)={\log }_2(k)$ where $k$ is the number of nearest neighbors, and ${\rho }_i$ is the minimum distance among the nearest neighbors

4. Calculate the edge weights to the nearest neighbors and symmetrize the graph

$v_{i|j}=\exp \left(-\frac{\max (0,d(x_i,x_j)-{\rho }_i)}{{\sigma }_i}\right)$ $v_{ij}=v_{ji}=v_{i|j}+v_{j|i}-v_{i|j}{v}_{j|i}$

5. Initialize the low-dimensional representation using spectral embedding.

6. optimize the low-dimensional representation by minimizing both the attractive and the repulsive force using SGD.

The cost function is defined as ${\sum }_{e\in E}\left[\underset{\text{attractive force}}{\underbrace{w_h(e)\log \left(\frac{w_h(e)}{w_l(e)}\right)}}+\underset{\text{repulsive force}}{\underbrace{(1-w_h(e))\log \left(\frac{1-w_h(e)}{1-w_l(e)}\right)}}\right]$ where $E$ is the set of edges, and $w_h(e)$ and $w_l(e)$ are the weights of the edge of the high-dimensional and low-dimensional graph respectively.

Link to original