Indexed text attachment
algebraic-and-differential-topology-in-machine-learning-and-ai.tex
Source for Algebraic and Differential Topology in Machine Learning and AI: Obstructions, Invariants, and Counts
View paper · Download original file
Lines 555–654 of 1055. Source text is displayed literally.
555Let $K$ be a simplicial complex with boundary matrices $\pd_k$. The \term{Hodge Laplacian} on $k$-chains is556$L_k=\pd_k^{\T}\pd_k+\pd_{k+1}\pd_{k+1}^{\T}$; for $k=0$ it is the graph Laplacian. Networks on complexes pass557messages along $\pd_k$ and $\pd_{k+1}^{\T}$ \cite{EDS20,BFW21}.558 559\begin{theorem}[Hodge]\label{thm:hodge}560\Scl[\cite{Eck44,Lim20}] \emph{(a)} $\ker L_k\cong H_k(K;\R)$. \emph{(b)} The iteration $X\mapsto X-\tau L_kX$ with561$0<\tau\le1/\lambda_{\max}$ converges to the orthogonal projection of $X$ on $\ker L_k$, the error contracting by562$1-\tau\lambda_{\min}^+$ per layer, where $\lambda_{\min}^+$ is the smallest non-zero eigenvalue.563\end{theorem}564 565\noindent The kernels have dimensions $(1,0,1)$, $(1,2,1)$, $(1,0,0)$, $(1,1,0)$, $(1,1,0)$, $(1,0,0)$ for the566sphere, torus, projective plane, Klein bottle, M\"obius band and disc, which are the Betti numbers computed567independently by Smith normal form. \chk{V1} On the edges of the seven-vertex torus $\lambda_{\min}^+=1.5858$ and568$\lambda_{\max}=7$; after $99$ layers four random inputs have converged to $10^{-11}$, and their limits span a569space of dimension $2$. \chk{V3} Statement (b) is the oversmoothing of graph networks one dimension up, with a570difference: the limit is not a constant but a harmonic form, and it carries exactly the homology.571 572\begin{proposition}[Coefficients are a choice of what is visible]\label{prop:torsion}573\Sob The limit in \cref{thm:hodge}\emph{(b)} depends only on the real homology of $K$. The projective plane and574the disc have the same harmonic spaces in every degree, although $H_1$ of the projective plane is $\Z/2$. Over575the field $\Fp_2$ the Betti numbers are $(1,1,1)$ and $(1,0,0)$. Conversely the Klein bottle and the torus agree576over $\Fp_2$, with $(1,2,1)$, and differ over $\R$.577\end{proposition}578 579\noindent The Betti numbers quoted are recomputed by the script. \chk{V2} Integral homology sees both distinctions at once and is computed by integer row and column580operations \cite[Ch.~2]{ADTHC}, which are not differentiable. An architecture built from real boundary matrices581has made the choice of the first column of the table below.582 583\begin{center}\small584\begin{tabular}{lccc}585\toprule586 & over $\R$ & over $\Fp_2$ & over $\Z$\\587\midrule588disc & $1,0,0$ & $1,0,0$ & $\Z,0,0$\\589projective plane & $1,0,0$ & $1,1,1$ & $\Z,\Z/2,0$\\590torus & $1,2,1$ & $1,2,1$ & $\Z,\Z^2,\Z$\\591Klein bottle & $1,1,0$ & $1,2,1$ & $\Z,\Z\oplus\Z/2,0$\\592\bottomrule593\end{tabular}594\end{center}595 596\subsection{Complexes built from samples}597 598Topological data analysis replaces a point cloud by the \term{Vietoris--Rips complex} at scale $r$, whose599simplices are the sets of points of diameter at most $r$, and reads off homology as $r$ varies600\cite{Car09,EdHa10}. For small $r$ and dense samples this recovers the homology of the underlying manifold601\cite{NSW08}. For large $r$ it does not, and what it produces instead is known for the circle.602 603\begin{theorem}[Rips complexes of a circle]\label{thm:rips}604\Sli[\cite{Ada13,AdAd17}] As the scale increases, the Vietoris--Rips complex of the circle has the homotopy type of605$S^1$, then $S^3$, then $S^5$, and so on, the type $S^{2l+1}$ occurring for scales between $\frac l{2l+1}$ and606$\frac{l+1}{2l+3}$ of a turn, until it is contractible. For $n$ equally spaced points and scale $k$ steps the same607holds with $k/n$ in place of the scale, and at the transition $k/n=\frac l{2l+1}$ the complex is a wedge of608$n-2k-1$ spheres of dimension $2l$.609\end{theorem}610 611\begin{figure}[t]612\centering613\begin{tikzpicture}614\draw[ink2,very thin,fill=fwd!22] (1,0) rectangle (1.92,0.42);615\node at (1.46,0.21) {\scriptsize $1$};616\draw[ink2,very thin,fill=fwd!22] (1,0.42) rectangle (1.92,0.84);617\node at (1.46,0.63) {\scriptsize $1$};618\draw[ink2,very thin,fill=white] (1,0.84) rectangle (1.92,1.26);619\draw[ink2,very thin,fill=white] (1,1.26) rectangle (1.92,1.68);620\draw[ink2,very thin,fill=white] (1,1.68) rectangle (1.92,2.1);621\draw[ink2,very thin,fill=white] (1,2.1) rectangle (1.92,2.52);622\node at (1.46,-0.22) {\scriptsize $1$};623\draw[ink2,very thin,fill=fwd!22] (1.92,0) rectangle (2.84,0.42);624\node at (2.38,0.21) {\scriptsize $1$};625\draw[ink2,very thin,fill=fwd!22] (1.92,0.42) rectangle (2.84,0.84);626\node at (2.38,0.63) {\scriptsize $1$};627\draw[ink2,very thin,fill=white] (1.92,0.84) rectangle (2.84,1.26);628\draw[ink2,very thin,fill=white] (1.92,1.26) rectangle (2.84,1.68);629\draw[ink2,very thin,fill=white] (1.92,1.68) rectangle (2.84,2.1);630\draw[ink2,very thin,fill=white] (1.92,2.1) rectangle (2.84,2.52);631\node at (2.38,-0.22) {\scriptsize $2$};632\draw[ink2,very thin,fill=fwd!22] (2.84,0) rectangle (3.76,0.42);633\node at (3.3,0.21) {\scriptsize $1$};634\draw[ink2,very thin,fill=fwd!22] (2.84,0.42) rectangle (3.76,0.84);635\node at (3.3,0.63) {\scriptsize $1$};636\draw[ink2,very thin,fill=white] (2.84,0.84) rectangle (3.76,1.26);637\draw[ink2,very thin,fill=white] (2.84,1.26) rectangle (3.76,1.68);638\draw[ink2,very thin,fill=white] (2.84,1.68) rectangle (3.76,2.1);639\draw[ink2,very thin,fill=white] (2.84,2.1) rectangle (3.76,2.52);640\node at (3.3,-0.22) {\scriptsize $3$};641\draw[ink2,very thin,fill=fwd!22] (3.76,0) rectangle (4.68,0.42);642\node at (4.22,0.21) {\scriptsize $1$};643\draw[ink2,very thin,fill=white] (3.76,0.42) rectangle (4.68,0.84);644\draw[ink2,very thin,fill=accent!28] (3.76,0.84) rectangle (4.68,1.26);645\node at (4.22,1.05) {\scriptsize $3$};646\draw[ink2,very thin,fill=white] (3.76,1.26) rectangle (4.68,1.68);647\draw[ink2,very thin,fill=white] (3.76,1.68) rectangle (4.68,2.1);648\draw[ink2,very thin,fill=white] (3.76,2.1) rectangle (4.68,2.52);649\node at (4.22,-0.22) {\scriptsize $4$};650\draw[ink2,very thin,fill=fwd!22] (4.68,0) rectangle (5.6,0.42);651\node at (5.14,0.21) {\scriptsize $1$};652\draw[ink2,very thin,fill=white] (4.68,0.42) rectangle (5.6,0.84);653\draw[ink2,very thin,fill=white] (4.68,0.84) rectangle (5.6,1.26);654\draw[ink2,very thin,fill=white] (4.68,1.26) rectangle (5.6,1.68);