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 161–260 of 1055. Source text is displayed literally.
161\[ \sup_{x\in S^n}|d(e(x))-x|\ \ge\ 1, \]162and equality holds for $e$ the projection to the first $n$ coordinates and $d$ the inclusion.163\end{theorem}164\begin{proof}165By the Borsuk--Ulam theorem there is $x$ with $e(x)=e(-x)$. Let $y$ be the common reconstruction. Then166$|y-x|+|y+x|\ge|2x|=2$, so one of the two errors is at least $1$. For the projection the error is167$|x_{n+1}|\le1$.168\end{proof}169 170\begin{figure}[t]171\centering172\begin{tikzpicture}173\begin{scope}[shift={(1.5,2.0)}]174\draw[ink2,thick] (0,0) circle (1.25);175\draw[ink2,densely dotted] (-1,-0.75)--(-1,0.75);176\fill[ink2] (-1,-0.75) circle (0.9pt); \fill[ink2] (-1,0.75) circle (0.9pt);177\draw[ink2,densely dotted] (-0.5,-1.146)--(-0.5,1.146);178\fill[ink2] (-0.5,-1.146) circle (0.9pt); \fill[ink2] (-0.5,1.146) circle (0.9pt);179\draw[ink2,densely dotted] (0.5,-1.146)--(0.5,1.146);180\fill[ink2] (0.5,-1.146) circle (0.9pt); \fill[ink2] (0.5,1.146) circle (0.9pt);181\draw[ink2,densely dotted] (1,-0.75)--(1,0.75);182\fill[ink2] (1,-0.75) circle (0.9pt); \fill[ink2] (1,0.75) circle (0.9pt);183\draw[accent,thick] (0,-1.25)--(0,1.25);184\fill[accent] (0,1.25) circle (1.6pt) node[above,inner sep=2pt]{\scriptsize $x$}; \fill[accent] (0,-1.25) circle (1.6pt) node[below,inner sep=2pt]{\scriptsize $-x$};185\fill[bwd] (0,0.28) circle (1.6pt) node[right,inner sep=2pt]{\scriptsize $y$};186\draw[ink2,-{Stealth[length=3pt]}] (-1.35,-1.87)--(1.5,-1.87);187\node[right,inner sep=1pt] at (1.52,-1.87) {\scriptsize $\R$};188\fill[ink2] (-1,-1.87) circle (1.1pt);189\fill[ink2] (-0.5,-1.87) circle (1.1pt);190\fill[accent] (0,-1.87) circle (1.1pt);191\fill[ink2] (0.5,-1.87) circle (1.1pt);192\fill[ink2] (1,-1.87) circle (1.1pt);193\node[left,inner sep=1pt] at (-1.37,-1.87) {\scriptsize $e$};194\node at (0,-2.33) {\scriptsize (a)};195\end{scope}196\begin{scope}[shift={(4.3,0.75)}]197\draw[ink2] (0,2.7)--(0,0)--(3.6,0);198\draw[ink2] (0,0)--(0,-0.07) node[below,inner sep=1.5pt]{\scriptsize $0$};199\draw[ink2] (3.6,0)--(3.6,-0.07) node[below,inner sep=1.5pt]{\scriptsize $\pi$};200\node[below] at (1.8,-0.38) {\scriptsize $\theta$};201\draw[thick,fwd] plot coordinates {(0,1.488) (0.03,1.496) (0.06,1.499) (0.09,1.499) (0.12,1.494) (0.15,1.486) (0.18,1.474) (0.21,1.459) (0.24,1.44) (0.27,1.417) (0.3,1.392) (0.33,1.364) (0.36,1.333) (0.39,1.3) (0.42,1.264) (0.45,1.227) (0.48,1.188) (0.51,1.148) (0.54,1.107) (0.57,1.066) (0.6,1.024) (0.63,0.982) (0.66,0.941) (0.69,0.901) (0.72,0.861) (0.75,0.823) (0.78,0.787) (0.81,0.753) (0.84,0.721) (0.87,0.692) (0.9,0.665) (0.93,0.642) (0.96,0.622) (0.99,0.606) (1.02,0.594) (1.05,0.585) (1.08,0.581) (1.11,0.581) (1.14,0.585) (1.17,0.594) (1.2,0.607) (1.23,0.625) (1.26,0.647) (1.29,0.673) (1.32,0.704) (1.35,0.739) (1.38,0.778) (1.41,0.821) (1.44,0.868) (1.47,0.919) (1.5,0.973) (1.53,1.03) (1.56,1.09) (1.59,1.152) (1.62,1.217) (1.65,1.284) (1.68,1.352) (1.71,1.422) (1.74,1.492) (1.77,1.563) (1.8,1.635) (1.83,1.706) (1.86,1.777) (1.89,1.846) (1.92,1.915) (1.95,1.982) (1.98,2.047) (2.01,2.109) (2.04,2.169) (2.07,2.226) (2.1,2.28) (2.13,2.33) (2.16,2.376) (2.19,2.418) (2.22,2.456) (2.25,2.489) (2.28,2.518) (2.31,2.541) (2.34,2.56) (2.37,2.574) (2.4,2.582) (2.43,2.586) (2.46,2.584) (2.49,2.577) (2.52,2.565) (2.55,2.547) (2.58,2.525) (2.61,2.498) (2.64,2.467) (2.67,2.431) (2.7,2.39) (2.73,2.346) (2.76,2.297) (2.79,2.246) (2.82,2.191) (2.85,2.133) (2.88,2.072) (2.91,2.01) (2.94,1.945) (2.97,1.879) (3,1.811) (3.03,1.743) (3.06,1.674) (3.09,1.606) (3.12,1.537) (3.15,1.47) (3.18,1.403) (3.21,1.338) (3.24,1.274) (3.27,1.213) (3.3,1.153) (3.33,1.097) (3.36,1.044) (3.39,0.993) (3.42,0.947) (3.45,0.904) (3.48,0.865) (3.51,0.83) (3.54,0.799) (3.57,0.772) (3.6,0.75)};202\draw[thick,bwd,densely dashed] plot coordinates {(0,0.75) (0.03,0.733) (0.06,0.72) (0.09,0.711) (0.12,0.707) (0.15,0.708) (0.18,0.712) (0.21,0.722) (0.24,0.735) (0.27,0.752) (0.3,0.773) (0.33,0.798) (0.36,0.826) (0.39,0.857) (0.42,0.892) (0.45,0.928) (0.48,0.967) (0.51,1.009) (0.54,1.051) (0.57,1.095) (0.6,1.14) (0.63,1.186) (0.66,1.232) (0.69,1.278) (0.72,1.324) (0.75,1.369) (0.78,1.413) (0.81,1.455) (0.84,1.496) (0.87,1.535) (0.9,1.571) (0.93,1.605) (0.96,1.636) (0.99,1.664) (1.02,1.688) (1.05,1.709) (1.08,1.726) (1.11,1.74) (1.14,1.749) (1.17,1.754) (1.2,1.755) (1.23,1.751) (1.26,1.744) (1.29,1.732) (1.32,1.716) (1.35,1.695) (1.38,1.671) (1.41,1.643) (1.44,1.61) (1.47,1.574) (1.5,1.535) (1.53,1.492) (1.56,1.446) (1.59,1.397) (1.62,1.345) (1.65,1.291) (1.68,1.236) (1.71,1.178) (1.74,1.119) (1.77,1.059) (1.8,0.999) (1.83,0.938) (1.86,0.876) (1.89,0.816) (1.92,0.755) (1.95,0.696) (1.98,0.638) (2.01,0.582) (2.04,0.528) (2.07,0.476) (2.1,0.427) (2.13,0.38) (2.16,0.337) (2.19,0.297) (2.22,0.26) (2.25,0.227) (2.28,0.198) (2.31,0.174) (2.34,0.153) (2.37,0.137) (2.4,0.125) (2.43,0.117) (2.46,0.114) (2.49,0.116) (2.52,0.122) (2.55,0.132) (2.58,0.147) (2.61,0.165) (2.64,0.188) (2.67,0.215) (2.7,0.245) (2.73,0.279) (2.76,0.316) (2.79,0.356) (2.82,0.399) (2.85,0.444) (2.88,0.492) (2.91,0.542) (2.94,0.593) (2.97,0.645) (3,0.698) (3.03,0.752) (3.06,0.807) (3.09,0.861) (3.12,0.914) (3.15,0.968) (3.18,1.02) (3.21,1.07) (3.24,1.119) (3.27,1.166) (3.3,1.211) (3.33,1.253) (3.36,1.293) (3.39,1.329) (3.42,1.363) (3.45,1.393) (3.48,1.419) (3.51,1.442) (3.54,1.461) (3.57,1.477) (3.6,1.488)};203\fill[accent] (0.56,1.08) circle (2pt);204\fill[accent] (1.652,1.288) circle (2pt);205\fill[accent] (3.283,1.186) circle (2pt);206\draw[thick,fwd] (0.1,2.93)--(0.5,2.93) node[right,inner sep=2pt,black]{\scriptsize $e(\theta)$};207\draw[thick,bwd,densely dashed] (1.75,2.93)--(2.15,2.93) node[right,inner sep=2pt,black]{\scriptsize $e(\theta+\pi)$};208\node at (1.8,-0.83) {\scriptsize (b)};209\end{scope}210\end{tikzpicture}211\caption{The bottleneck bound for the circle. (a)~The fibres of the projection code; the fibre through the poles is an antipodal pair, and whatever point $y$ the decoder returns for it is at distance at least $1$ from one of the two. (b)~A random trigonometric encoder $e$ and its antipodal translate on a half-turn: since $e(\theta)-e(\theta+\pi)$ changes sign, the graphs cross (3 times here), and at a crossing the code identifies $x$ and $-x$.}\label{fig:bottleneck}212\end{figure}213 214\noindent For $n=1$ the collision was located for $200$ random trigonometric encoders, and for $n=2$ for $40$215random cubic encoders, to rounding (\cref{fig:bottleneck}). \chk{O1, O2} For each of $100$ random encoders of the216circle, some fibre of the code, taken to one percent of its range, is contained in no disc of radius less than217$1.0000$: no decoder can do better than error $1$ there. \chk{O3} The theorem is about the worst case. The mean error can be made small, by a code that is218injective except near one point; the bound says that the failure cannot be removed, only moved and made thin.219For a general closed $n$-manifold the qualitative statement survives: by Brouwer's invariance of domain, the220companion of the invariance of dimension \cite[Thm.~4.3]{ADTHC}, it has no continuous injective code in $\R^n$.221The constant is special to round spheres.222This is the topological reason for latent spaces that are themselves spheres, tori or groups223\cite{DFdC18,FdH18}.224 225\subsection{Rotations}226 227Let $\rho\colon S^3\to\SO(3)$ send a unit quaternion $q$ to the rotation $v\mapsto qvq^{-1}$. It is onto, and228$\rho(q)=\rho(-q)$.229 230\begin{theorem}[Naming a rotation]\label{thm:rotation}231\Sli[\cite{ZBLYL19}; \cite{ADTHC}, Thm.~10.1] \emph{(a)} $\rho$ has no continuous right inverse: for every choice232of a quaternion $s(R)$ with $\rho(s(R))=R$ there is, on every non-contractible loop of rotations, a point where233$s$ jumps by $|q-(-q)|=2$. \emph{(b)} More generally a family of rotations $X\to\SO(3)$ has a continuous234quaternion target if and only if it induces the zero map $\pi_1(X)\to\pi_1(\SO(3))=\Z/2$. \emph{(c)} There is no235continuous representation of $\SO(3)$ in $\R^m$ for $m\le4$. \emph{(d)} Two columns of the rotation matrix, with236Gram--Schmidt orthogonalization as decoder, give a continuous representation in $\R^6$.237\end{theorem}238\begin{proof}239(a), (b): $\rho$ is the universal covering, and a map lifts through a covering exactly when it kills the240fundamental group; a full turn about an axis lifts to a path from $q$ to $-q$. (c) is proved in \cite{ZBLYL19}241from the fact that $\SO(3)$, which is real projective $3$-space, does not embed in $\R^4$. (d) The two columns242determine the third by the cross product.243\end{proof}244 245\begin{figure}[t]246\centering247\begin{tikzpicture}248\begin{scope}[shift={(0,0)}]249\draw[ink2] (0,2.3)--(0,0)--(3.25,0);250\draw[ink2] (0,0)--(0,-0.07) node[below,inner sep=1.5pt]{\scriptsize $0$};251\draw[ink2] (1.625,0)--(1.625,-0.07) node[below,inner sep=1.5pt]{\scriptsize $\pi$};252\draw[ink2] (3.25,0)--(3.25,-0.07) node[below,inner sep=1.5pt]{\scriptsize $2\pi$};253\draw[ink2] (0,0.085)--(-0.07,0.085) node[left,inner sep=1.5pt]{\scriptsize $-1$};254\draw[ink2] (0,1.15)--(-0.07,1.15) node[left,inner sep=1.5pt]{\scriptsize $0$};255\draw[ink2] (0,2.215)--(-0.07,2.215) node[left,inner sep=1.5pt]{\scriptsize $1$};256\node[below] at (1.625,-0.38) {\scriptsize angle of the turn};257\draw[ink2,very thin] (0,1.15)--(3.25,1.15);258\draw[thick,fwd] plot coordinates {(0,2.215) (0.016,2.215) (0.033,2.214) (0.049,2.214) (0.065,2.213) (0.081,2.212) (0.098,2.21) (0.114,2.208) (0.13,2.206) (0.146,2.204) (0.163,2.202) (0.179,2.199) (0.195,2.196) (0.211,2.193) (0.228,2.189) (0.244,2.185) (0.26,2.181) (0.276,2.177) (0.292,2.173) (0.309,2.168) (0.325,2.163) (0.341,2.157) (0.357,2.152) (0.374,2.146) (0.39,2.14) (0.406,2.134) (0.422,2.127) (0.439,2.12) (0.455,2.113) (0.471,2.106) (0.487,2.099) (0.504,2.091) (0.52,2.083) (0.536,2.075) (0.553,2.067) (0.569,2.058) (0.585,2.049) (0.601,2.04) (0.617,2.031) (0.634,2.021) (0.65,2.011) (0.666,2.002) (0.683,1.991) (0.699,1.981) (0.715,1.97) (0.731,1.96) (0.747,1.949) (0.764,1.938) (0.78,1.926) (0.796,1.915) (0.813,1.903) (0.829,1.891) (0.845,1.879) (0.861,1.867) (0.877,1.854) (0.894,1.842) (0.91,1.829) (0.926,1.816) (0.943,1.803) (0.959,1.789) (0.975,1.776) (0.991,1.762) (1.008,1.749) (1.024,1.735) (1.04,1.721) (1.056,1.706) (1.073,1.692) (1.089,1.678) (1.105,1.663) (1.121,1.648) (1.137,1.633) (1.154,1.618) (1.17,1.603) (1.186,1.588) (1.203,1.573) (1.219,1.557) (1.235,1.542) (1.251,1.526) (1.267,1.511) (1.284,1.495) (1.3,1.479) (1.316,1.463) (1.333,1.447) (1.349,1.431) (1.365,1.415) (1.381,1.399) (1.397,1.382) (1.414,1.366) (1.43,1.35) (1.446,1.333) (1.463,1.317) (1.479,1.3) (1.495,1.283) (1.511,1.267) (1.528,1.25) (1.544,1.234) (1.56,1.217) (1.576,1.2) (1.592,1.183) (1.609,1.167) (1.625,1.15)};259\draw[thick,fwd] plot coordinates {(1.625,1.15) (1.641,1.167) (1.658,1.183) (1.674,1.2) (1.69,1.217) (1.706,1.234) (1.722,1.25) (1.739,1.267) (1.755,1.283) (1.771,1.3) (1.787,1.317) (1.804,1.333) (1.82,1.35) (1.836,1.366) (1.853,1.382) (1.869,1.399) (1.885,1.415) (1.901,1.431) (1.917,1.447) (1.934,1.463) (1.95,1.479) (1.966,1.495) (1.982,1.511) (1.999,1.526) (2.015,1.542) (2.031,1.557) (2.047,1.573) (2.064,1.588) (2.08,1.603) (2.096,1.618) (2.113,1.633) (2.129,1.648) (2.145,1.663) (2.161,1.678) (2.177,1.692) (2.194,1.706) (2.21,1.721) (2.226,1.735) (2.243,1.749) (2.259,1.762) (2.275,1.776) (2.291,1.789) (2.307,1.803) (2.324,1.816) (2.34,1.829) (2.356,1.842) (2.373,1.854) (2.389,1.867) (2.405,1.879) (2.421,1.891) (2.438,1.903) (2.454,1.915) (2.47,1.926) (2.486,1.938) (2.502,1.949) (2.519,1.96) (2.535,1.97) (2.551,1.981) (2.567,1.991) (2.584,2.002) (2.6,2.011) (2.616,2.021) (2.632,2.031) (2.649,2.04) (2.665,2.049) (2.681,2.058) (2.698,2.067) (2.714,2.075) (2.73,2.083) (2.746,2.091) (2.762,2.099) (2.779,2.106) (2.795,2.113) (2.811,2.12) (2.828,2.127) (2.844,2.134) (2.86,2.14) (2.876,2.146) (2.893,2.152) (2.909,2.157) (2.925,2.163) (2.941,2.168) (2.958,2.173) (2.974,2.177) (2.99,2.181) (3.006,2.185) (3.022,2.189) (3.039,2.193) (3.055,2.196) (3.071,2.199) (3.087,2.202) (3.104,2.204) (3.12,2.206) (3.136,2.208) (3.152,2.21) (3.169,2.212) (3.185,2.213) (3.201,2.214) (3.218,2.214) (3.234,2.215) (3.25,2.215)};260\draw[thick,bwd] plot coordinates {(0,1.15) (0.016,1.155) (0.033,1.16) (0.049,1.165) (0.065,1.17) (0.081,1.175) (0.098,1.18) (0.114,1.185) (0.13,1.19) (0.146,1.195) (0.163,1.2) (0.179,1.205) (0.195,1.21) (0.211,1.215) (0.228,1.22) (0.244,1.225) (0.26,1.23) (0.276,1.235) (0.292,1.24) (0.309,1.245) (0.325,1.25) (0.341,1.255) (0.357,1.259) (0.374,1.264) (0.39,1.269) (0.406,1.273) (0.422,1.278) (0.439,1.283) (0.455,1.287) (0.471,1.292) (0.487,1.296) (0.504,1.301) (0.52,1.305) (0.536,1.31) (0.553,1.314) (0.569,1.319) (0.585,1.323) (0.601,1.327) (0.617,1.331) (0.634,1.336) (0.65,1.34) (0.666,1.344) (0.683,1.348) (0.699,1.352) (0.715,1.356) (0.731,1.36) (0.747,1.363) (0.764,1.367) (0.78,1.371) (0.796,1.375) (0.813,1.378) (0.829,1.382) (0.845,1.385) (0.861,1.389) (0.877,1.392) (0.894,1.395) (0.91,1.399) (0.926,1.402) (0.943,1.405) (0.959,1.408) (0.975,1.411) (0.991,1.414) (1.008,1.417) (1.024,1.42) (1.04,1.422) (1.056,1.425) (1.073,1.428) (1.089,1.43) (1.105,1.433) (1.121,1.435) (1.137,1.438) (1.154,1.44) (1.17,1.442) (1.186,1.444) (1.203,1.446) (1.219,1.448) (1.235,1.45) (1.251,1.452) (1.267,1.454) (1.284,1.455) (1.3,1.457) (1.316,1.458) (1.333,1.46) (1.349,1.461) (1.365,1.463) (1.381,1.464) (1.397,1.465) (1.414,1.466) (1.43,1.467) (1.446,1.468) (1.463,1.469) (1.479,1.469) (1.495,1.47) (1.511,1.471) (1.528,1.471) (1.544,1.472) (1.56,1.472) (1.576,1.472) (1.592,1.473) (1.609,1.473) (1.625,1.473)};