The Hierarchy of Manifolds in a Stratification of the Set of Equivalent Linear Neural Networks

In its simplest form, a linear neural network is a sequence of matrices whose product is a matrix.¹¹1To a practitioner, a linear neural network is a neural network in which all the activation functions are the identity function. In this paper’s neural networks, every layer of edges is fully-connected. The network takes an input vector $x$ and produces an output vector $y=W_L{W}_{L-1}\mathrm{\cdots }{W}_2{W}_{1}x$. We number the matrices in the order they are applied. The matrix $W_1$ linearly transforms $x$, producing a vector that $W_2$ linearly transforms, and so on. The composition of those transformations is also a linear transformation, represented by

where $\mu$ is called the matrix multiplication map. Each matrix $W_j$ is interpreted as a layer of edges (connections) in the network, edge layer number $j$, and each component of $W_j$ is interpreted as the weight of an edge. For brevity, we omit added terms, which do not appreciably affect our results (but we address them in the full-length manuscript [20]).

We wish to study ${\mu }^{-1}(W)$, the set of all factorizations of a matrix $W$ into a product of matrices of specified sizes. Said differently, we study the set of all choices of linear neural network weights such that the network computes the linear transformation $W$. This set is infinite (unless $L=1$) and it is a real algebraic variety – the set of all real-valued solutions of a system of polynomial equations (specifically, multilinear equations). Trager, Kohn, and Bruna [23], whose paper inspired ours, call ${\mu }^{-1}(W)$ the fiber of $W$ under the map $\mu$. Understanding the fiber has applications in understanding gradient descent algorithms for training neural networks – but it is also a beautiful mathematical problem in its own right.

Sometimes the fiber is a manifold – see Figure 1 for an example – but usually not. Always it can be partitioned into smooth manifolds of various dimensions, called strata. The set of strata is called a stratification of the fiber. Figure 2 graphs the solutions of $[{\theta }_2][{\theta }_1{\theta }_1^{\prime }]=[\mathrm{0\; 0}]$ (an instantiation of $W_2{W}_1=W$). The set of solutions can be partitioned into three strata: $S_{00}$ is the origin, $S_{10}$ is the ${\theta }_2$-axis with the origin removed, and $S_{01}$ is the ${\theta }_1$-${\theta }_1^{\prime }$ plane with the origin removed. The two subscripts of $S_{\ast \ast }$ are the ranks of $W_2$ and $W_1$, respectively. The stratum $S_{00}$ lies in the closures of both $S_{10}$ and $S_{01}$; $S_{00}$ serves to connect $S_{10}$ to $S_{01}$.

Figure 2 illustrates what we call a rank stratification of the fiber ${\mu }^{-1}(W)$, which has one stratum for each rank list defined in Section 2; it is the most natural way to stratify a fiber of the matrix multiplication map. In the full-length manuscript [20], we show that the strata in a rank stratification are analytic manifolds (hence of class $C^{\mathrm{\infty }}$), derive their dimensions, and derive the tangent and normal spaces at each point of each stratum.

This paper characterizes how the strata are connected to each other. The strata satisfy the frontier condition: if a stratum intersects the closure of another stratum, then the former stratum is a subset of the closure of the latter stratum. This subset relationship induces a partial order with a single minimal element, a stratum that is included in the closure of every other stratum (in Figure 2, $S_{00}$). Our main result describes the relationship between this partial order and the ranks of certain matrices in the network. What makes it interesting is that each stratum represents a different pattern of information flow through the network.

In 1957, Hassler Whitney [24, 25, 26] proved that every real algebraic variety can be partitioned into a finite set of analytic manifolds. Łojasiewicz [16] generalized the result to semi-algebraic and semi-analytic sets. Mather [18] showed that Whitney’s stratifications satisfy the frontier condition (but there exist stratifications that do not, hence we prove that rank stratifications do). Thom [22] introduced the terms stratum and stratification.

Linear neural networks compute only linear transformations; they are far less powerful than networks with nonlinear activation functions such as rectified linear units (ReLUs, also called ramp functions) and sigmoid functions (also called logistic functions). Yet linear networks have become a popular object of study [1, 2, 4, 5, 11, 12, 13, 14, 17, 19, 23, 27]. Why? We cannot fully understand the training of ReLU-based networks – or probably any neural networks – if we do not understand linear networks. Researchers have studied linear neural networks to understand phenomena observed in ReLU networks such as implicit regularization in optimizing the training algorithm’s cost function [10, 2, 5], implicit acceleration of training by gradient descent [1], and the success of residual networks [11]. Close to our hearts, Trager, Kohn, and Bruna [23] show that the fiber ${\mu }^{-1}(W)$ is crucial for understanding the critical points of the cost functions minimized by neural network training algorithms. We aspire to build a related theory for ReLU networks, and we hope insights in this paper will help.

Let $L$ be the number of matrices – that is, the number of layers of edges (connections) in the network. Alternating with the edge layers are $L+1$ layers of units, numbered from $0$ to $L$, in which layer $j$ has $d_j$ real-valued units that represent a vector in ${ℝ}^{d_j}$. Unit layer $0$ is the input layer, unit layer $L$ is the output layer, and between them are $L-1$ hidden layers. The layers of edges are numbered from $1$ to $L$, and the edge weights in edge layer $j$ are represented by a real-valued $d_j\times d_{j-1}$ matrix $W_j$.

We collect all the network’s weights in a weight vector $\theta =(W_L,W_{L-1},\mathrm{\dots },W_1)\in {ℝ}^{d_{\theta }}$, where $d_{\theta }=d_L{d}_{L-1}+d_{L-1}{d}_{L-2}+\mathrm{\dots }+d_1{d}_0$ is the number of real-valued weights in the network (i.e., the number of connections). Recall the matrix multiplication map $\mu (W_L,W_{L-1},\mathrm{\dots },W_2,W_1)$; we can abbreviate it to $\mu (\theta )=W_L{W}_{L-1}\mathrm{\cdots }{W}_2{W}_1$. Given a fixed weight vector $\theta$, the linear neural network takes an input vector $x\in {ℝ}^{d_0}$ and returns an output vector $y=W_L{W}_{L-1}\mathrm{\cdots }{W}_2{W}_{1}x$, with $y\in {ℝ}^{d_L}$. Hence, the network implicitly applies a linear transformation specified by the $d_L\times d_0$ matrix $W=\mu (\theta )$, yielding $y=Wx$.

The map $\mu$ is not bijective (unless $L=1$), so it has a preimage set, not an inverse. Given $W\in {ℝ}^{d_L\times d_0}$, let

be the set of all factorizations of $W$ for some fixed $d_L,d_{L-1},\mathrm{\dots },d_0$. Call ${\mu }^{-1}(W)$ the fiber of $W$ under $\mu$; it is a real algebraic variety in the weight space ${ℝ}^{d_{\theta }}$. With respect to ${ℝ}^{d_{\theta }}$, ${\mu }^{-1}(W)$ is a closed point set. Note that ${\mu }^{-1}(W)$ is empty if and only if $\mathrm{rk}W>{\min }_{j=1}^{L-1}{d}_j$.

Given a weight vector $\theta =(W_L,W_{L-1},\mathrm{\dots },W_1)$, its subsequence matrices are all the matrices of the form $W_{k◀i}=W_k{W}_{k-1}\mathrm{\cdots }{W}_{i+1}$. The notation $W_{k◀i}$ indicates that this matrix transforms a vector at unit layer $i$ to produce a vector at unit layer $k$. Note that $W=W_{L◀0}$ and $W_j=W_{j◀j-1}$. We use the convention that $W_{k◀k}=I_{d_k\times d_k}$, the $d_k\times d_k$ identity matrix. Assume that every $W_{k◀i}$ in this paper is a function of $\theta$. We call each $W_j$ a factor matrix.

The rank list $\underset{¯}{r}$ for a weight vector $\theta \in {ℝ}^{d_{\theta }}$ is a sequence that lists the rank of every subsequence matrix $W_{k◀i}$ such that $L\ge k\ge i\ge 0$. The list includes the unit layer sizes $\mathrm{rk}{W}_{k◀k}=d_k$. For example, for a network with $L=3$ layers of edges, the rank list of $\theta$ is

We will use rank lists to partition a fiber into strata. Sometimes we do not want to specify a particular $\theta$, but rather we wish to specify some target ranks. In that case, we let $r_{k◀i}$ denote the target value of $\mathrm{rk}{W}_{k◀i}$ and we write $\underset{¯}{r}={⟨r_{k◀i}⟩}_{L\ge k\ge i\ge 0}$. For example, if we set $r_{3◀1}=2$, we select weight vectors for which $\mathrm{rk}{W}_3{W}_2=2$. If $L=2$ and we set $\underset{¯}{r}=⟨9,8,7,2,3,1⟩$, we select weight vectors for which $W_2$ is a $9\times 8$ matrix of rank $2$, $W_1$ is an $8\times 7$ matrix of rank $3$, and $W=W_2{W}_1$ has rank $1$.

Let $S_{\underset{¯}{r}}^W$ denote the set of points in $W$’s fiber having rank list $\underset{¯}{r}$. That is,

If it is nonempty, we call $S_{\underset{¯}{r}}^W$ a stratum in the rank stratification of $W$’s fiber. When $W$ is clear from context, we just write $S_{\underset{¯}{r}}$. Each $S_{\underset{¯}{r}}$ is an analytic manifold [20] (but not necessarily closed nor connected nor bounded). The rank stratification of ${\mu }^{-1}(W)$ is

The members of $𝕊$ are disjoint and ${\mu }^{-1}(W)={\bigcup }_{S\in 𝕊}S$ – that is, $𝕊$ is a partition of ${\mu }^{-1}(W)$.

A rank list $\underset{¯}{r}$ is valid if there exists some weight vector $\theta \in {ℝ}^{d_{\theta }}$ that has rank list $\underset{¯}{r}$. We show in the full-length manuscript [20] that if $W\in {ℝ}^{d_L\times d_0}$ and $\underset{¯}{r}$ is a valid rank list with $r_{L◀0}=\mathrm{rk}W$, then there exists some $\theta \in {\mu }^{-1}(W)$ that has rank list $\underset{¯}{r}$, so $S_{\underset{¯}{r}}$ is nonempty.

Given two rank lists $\underset{¯}{r}$ and $\underset{¯}{z}$, we write $\underset{¯}{r}\le \underset{¯}{z}$ to mean that $r_{k◀i}\le z_{k◀i}$ for all $L\ge k\ge i\ge 0$. We write to mean that $\underset{¯}{r}\le \underset{¯}{z}$ and $\underset{¯}{r}\ne \underset{¯}{z}$ (at least one of the inequalities holds strictly).

Given a set $S\subseteq {ℝ}^{d_{\theta }}$, let $\overline{S}$ denote the closure of $S$ (with respect to the weight space ${ℝ}^{d_{\theta }}$).

We have not yet defined the terminology in statement D. A stratum dag is a directed acyclic graph (dag) with one vertex for each stratum in $𝕊$ and one directed edge for each rank-one abstract barcode move; see Figure 2, right. For now, just know that these moves are the central new concept in this paper, which organize the strata in $𝕊$ in a natural hierarchy. Read statement D as “there is a directed path in the stratum dag from $S_{\underset{¯}{r}}$ to $S_{\underset{¯}{z}}$.” The stratum dag encodes the partial order of the strata induced by $\le$, but it is not necessarily the simplest dag that does so (sometimes called a Hasse diagram or transitive reduction), for reasons we explain in the full-length manuscript [20].

Figures 3 and 4 depict two more examples of stratum dags. Notable in Figure 3 is that we arrange the stratum dag in a three-dimensional table, indexed by $\mathrm{rk}{W}_3$, $\mathrm{rk}{W}_2$, and $\mathrm{rk}{W}_1$. Ordinarily, three-matrix fibers ($L=3$) require five indices to index the strata, as $\mathrm{rk}{W}_3{W}_2$ and $\mathrm{rk}{W}_2{W}_1$ can vary as well; but in this example every matrix is $1\times 1$, so those two ranks are uniquely determined by the first three. Notable in Figure 4 is that the fiber has dimension as high as $35$ at some points, and it is embedded in a $54$-dimensional weight space. Unfortunately, we cannot visualize the fiber, but its strata are curved, like in Figure 1. In both dags, there is a unique minimal stratum – $S_{000}$ and $S_{11}$, respectively – that is a subset of the closure of every other stratum. In all rank stratifications, the minimal stratum is the one in which every subsequence matrix’s rank is $\mathrm{rk}W$, except the layer sizes $\mathrm{rk}{W}_{j◀j}=d_j$. (In the full-length manuscript [20], we give an algorithm for computing stratum dags.)

Most important in Theorem 1 is the equivalence of statements A and C: $S_{\underset{¯}{r}}\subseteq {\overline{S}}_{\underset{¯}{z}}$ if and only if $\underset{¯}{r}\le \underset{¯}{z}$. The rank lists tell you which strata’s closures include (or intersect) which strata.

The fact that B implies A means that rank stratifications satisfy the frontier condition defined in the Introduction: for every pair of strata $S,T\in 𝕊$, either $S\cap \overline{T}=\mathrm{\varnothing }$ or $S\subseteq \overline{T}$. (The two possibilities are mutually exclusive, because $S\ne \mathrm{\varnothing }$.) That is, the inclusion of points of $S$ in $\overline{T}$ is all or nothing, which helps us to understand how strata are connected to each other. For example, if $S\subseteq \overline{T}$ and $S\ne T$, then and from any point on $S$ there is an infinitesimal perturbation that takes us onto $T$.

As the fiber is a closed point set, Theorem 1 implies that ${\overline{S}}_{\underset{¯}{z}}={\bigcup }_{\underset{¯}{r}\le \underset{¯}{z}}{S}_{\underset{¯}{r}}$. In Figure 3, ${\overline{S}}_{011}=S_{011}\cup S_{010}\cup S_{001}\cup S_{000}$, whereas $S_{100}\cap {\overline{S}}_{011}=\mathrm{\varnothing }$ and $S_{011}\cap {\overline{S}}_{100}=\mathrm{\varnothing }$.

Our proof of Theorem 1 shows the four implications A $\to$ B $\to$ C $\to$ D $\to$ A. Clearly A implies B, as we assume $S_{\underset{¯}{r}}\ne \mathrm{\varnothing }$. To see that B implies C, observe that an infinitesimal perturbation of a weight vector $\theta \in S_{\underset{¯}{r}}$ may increase the ranks of some subsequence matrices but it cannot decrease any of their ranks, so a stratum $S_{\underset{¯}{z}}$ can have $\theta$ in its closure only if $\underset{¯}{r}\le \underset{¯}{z}$. Showing that D implies A is not difficult (an abstract move implies arbitrarily small geometric moves). The fact that C implies D was by far the hardest of the four implications to prove; for many months we did not know if C implies any of the other statements.

While statements A and B are statements about geometry, statements C and D are purely combinatorial. Our proof that C implies D is also purely combinatorial. Space is limited, so we give only part of that proof, including an algorithm that finds a suitable sequence of barcode moves (thereby showing one exists). The rest of this paper relates the geometry to the combinatorics, introduces barcode moves, and constructs the sequence of moves.

In this section, we show how to decompose each unit layer’s space ${ℝ}^{d_j}$ into a prebasis of subspaces of ${ℝ}^{d_j}$; then decompose each edge layer’s space ${ℝ}^{d_j\times d_{j-1}}$ into a prebasis of subspaces of ${ℝ}^{d_j\times d_{j-1}}$; then decompose the weight space ${ℝ}^{d_{\theta }}$ into a prebasis of subspaces of ${ℝ}^{d_{\theta }}$, which will illuminate the connections among strata. We assume the reader is familiar with the standard idea from linear algebra of a basis for ${ℝ}^d$, comprising $d$ linearly independent basis vectors. A prebasis is like a basis, but it is made up of subspaces rather than vectors.

Given two subspaces $P,Q\subseteq {ℝ}^d$, their vector sum is $P+Q=\{p+q:p\in P$ and $q\in Q\}$. If $P$ and $Q$ are linearly independent – that is, if $P\cap Q=\{\mathrm{𝟎}\}$ – then $P+Q$ is called a direct sum, sometimes written²²2The notation $P\oplus Q$ is unconventional, because as an operator it produces $P+Q$, but it also implies a constraint on the subspaces $P$ and $Q$: that $P\cap Q=\{\mathrm{𝟎}\}$. If $P\cap Q\ne \{\mathrm{𝟎}\}$, then $P\oplus Q$ is undefined. $P\oplus Q$. Likewise, given a set of subspaces $𝒫=\{P_1,P_2,\mathrm{\dots },P_m\}$, the direct sum notation $P_1\oplus P_2\oplus \mathrm{\dots }\oplus P_m$ implies that the subspaces in $𝒫$ are linearly independent – meaning that for every $i\in [1,m]$, $P_i\cap {\sum }_{j\ne i}{P}_j=\{\mathrm{𝟎}\}$.

If ${ℝ}^d=P_1\oplus P_2\oplus \mathrm{\dots }\oplus P_m$, then $𝒫=\{P_1,P_2,\mathrm{\dots },P_m\}$ is known as a direct sum decomposition of ${ℝ}^d$. For brevity, we call $𝒫$ a prebasis for ${ℝ}^d$, and we say that $𝒫$ spans ${ℝ}^d$. We call each $P_i$ a prebasis subspace – a multidimensional analogue of a basis vector. The linear independence of the prebasis subspaces implies that for every vector $v\in {ℝ}^d$, there is one and only one way to express $v$ as a sum of vectors $v={\sum }_{i=1}^m{v}_i$ such that $v_i\in P_i$. It also implies that $d={\sum }_{i=1}^{m}dim{P}_i$. If desired, it is conceptually easy to convert a prebasis into a traditional vector basis: just choose a basis for each $P_i$, then pool the $d$ vectors together to form a basis for ${ℝ}^d$ – hence the name “prebasis.” Why don’t we do that here? Because details like the choice of basis for each prebasis subspace and the length of each basis vector are irrelevant and would make our presentation more complicated.

The following theorem identifies “fundamental” subspaces in a linear neural network’s hidden layers analogous to the four fundamental subspaces [21] of a matrix $M$: the rowspace (denoted $\mathrm{row}M$), the nullspace ($\mathrm{null}M$), the columnspace ($\mathrm{col}M$), and the left nullspace ($\mathrm{null}{M}^{\top }$). The theorem originates in the study of persistent homology [8, 7] (for entirely different reasons) where it is used to analyze persistence modules [28, 29, 9, 3, 15], which are essentially linear neural networks – but usually over the field $\mathbb{Z}/2\mathbb{Z}$, in contrast to our real-valued weights. Given a matrix $M$ and a subspace $P\subseteq {ℝ}^d$, define $MP=\{Mv:v\in P\}$.

The prebases ${𝒜}_j$ describe information flow through the network. As illustrated in Figure 5 (top), we interpret $a_{kii}$ as an ${\omega }_{ki}$-dimensional subspace that appears at unit layer $i$ (its birth layer), being linearly independent of (but not necessarily orthogonal to) $\mathrm{col}{W}_i$, then flows through the weight layers $W_{i+1},W_{i+2},\mathrm{\dots },W_k$ being linearly transformed into a sequence of subspaces $a_{k,i+1,i},a_{k,i+2,i},\mathrm{\dots }$, all of dimension ${\omega }_{ki}$, reaches layer $k$ (its death layer) in the form $a_{kki}$, still having ${\omega }_{ki}$ dimensions, and proceeds no farther – because either $a_{kki}\subseteq \mathrm{null}{W}_{k+1}$ or layer $k$ is the output layer. These subspaces carry information from the input layer only if $i=0$ and reach the output layer only if $k=L$; otherwise, they represent unused potential.

Symmetrically, the prebases ${ℬ}_j$ govern the transpose network $W^{\top }=W_1^{\top }{W}_2^{\top }\mathrm{\cdots }{W}_{L-1}^{\top }{W}_L^{\top }$. We interpret $b_{kki}$ as an ${\omega }_{ki}$-dimensional subspace that appears at layer $k$, being linearly independent of $\mathrm{row}{W}_{k+1}$, then flows through the weight layers $W_k^{\top },W_{k-1}^{\top },\mathrm{\dots },W_{i+1}^{\top }$ being linearly transformed into a sequence of ${\omega }_{ki}$-dimensional subspaces $b_{k,k-1,i},b_{k,k-2,i},\mathrm{\dots }$, and stops at layer $i$ in the form $b_{kii}$ – either because $b_{kii}\subseteq \mathrm{null}{W}_i^{\top }$ or because $i=0$.

We call each ${\omega }_{ki}$ an interval count. An interval is a set of consecutive integers $[i,k]=\{i,i+1,\mathrm{\dots },k-1,k\}$ that signifies consecutive unit layers, with $i$ being the birth layer and $k$ being the death layer for the information that the interval represents. The barcode for $\theta$ – an idea originating in persistent homology [9] – is a multiset of intervals that contains ${\omega }_{ki}$ copies of $[i,k]$ for all $0\le i\le k\le L$. The top half of Figure 5 depicts a barcode annotated with prebasis subspaces. Barcodes show visually how information flows in linear networks.

The identities (1) and (2) express a bijection between rank lists and barcodes. The bottom half of Figure 5 depicts those identities visually.

We will see in Section 6 that we can understand the hierarchy of strata in terms of simple transformations of the barcode. (We can also understand it in terms of transformations of the rank list, but those transformations are not as simple.)

Now, we construct prebases for the factor matrix spaces ${ℝ}^{d_j\times d_{j-1}}$ and the weight space ${ℝ}^{d_{\theta }}$. Like the $a_{kji}$’s and $b_{kji}$’s, these prebases are defined at a specific weight vector $\theta$. For indices satisfying $L\ge l\ge j\ge i\ge 0$ and $L\ge k\ge j-1\ge h\ge 0$, define the prebasis subspace

Then $dim{o}_{lkjih}=dim{a}_{lji}\cdot dim{b}_{k,j-1,h}={\omega }_{li}{\omega }_{kh}$. For each $j\in [1,L]$, define the prebasis

${𝒪}_j$ is a prebasis for the weight layer ${ℝ}^{d_j\times d_{j-1}}$, as it pairs every subspace in the prebasis ${𝒜}_j$ (spanning ${ℝ}^{d_j}$) with every subspace in the prebasis ${ℬ}_{j-1}$ (spanning ${ℝ}^{d_{j-1}}$).

Now we construct a prebasis ${\mathrm{\Theta }}_{\mathrm{O}}$ for the weight space ${ℝ}^{d_{\theta }}$ that we call the one-matrix prebasis. The subspaces in ${\mathrm{\Theta }}_{\mathrm{O}}$ are called the one-matrix subspaces and have the form

with $M$ in position $j$ from the right (the position of $W_j$ in $\theta$). The one-matrix prebasis is

Imagine you are standing at a point $\theta$ on a fiber ${\mu }^{-1}(W)$. A move $(\theta ,{\theta }^{\prime })$ is a step you take from $\theta$ to another point ${\theta }^{\prime }$, which may or may not be on the fiber. Let $\mathrm{\Delta }\theta ={\theta }^{\prime }-\theta$ be the displacement of the move. We write

We use analogous notation for the product $W^{\prime }=\mu ({\theta }^{\prime })$, its displacement $\mathrm{\Delta }W=W^{\prime }-W$, the modified subsequence matrices $W_{t◀s}^{\prime }=W_t^{\prime }{W}_{t-1}^{\prime }\mathrm{\cdots }{W}_{s+1}^{\prime }$, and their displacements $\mathrm{\Delta }{W}_{t◀s}=W_{t◀s}^{\prime }-W_{t◀s}$. All prebasis subspaces below are defined at $\theta$. (They are different at ${\theta }^{\prime }$!)

Moves on the fiber replace a linear neural network with another that computes the same function. Here, we are interested in basic one-matrix moves, for which $\mathrm{\Delta }\theta \in {\varphi }_{lkjih}$ for some ${\varphi }_{lkjih}\in {\mathrm{\Theta }}_{\mathrm{O}}$. (“Basic” means “from the prebasis,” not “simple.”) Equivalently, a basic move replaces $W_j$ with $W_j^{\prime }=W_j+\mathrm{\Delta }{W}_j$, where $\mathrm{\Delta }{W}_j\in o_{lkjih}$ and $o_{lkjih}\in {𝒪}_j$. Once we understand basic moves, other moves can be understood as sequences of basic moves. We are particularly interested in basic moves that change the rank list and move from one stratum to another.

For each subspace $o_{lkjih}\in {𝒪}_j$, we ask: does a move with displacement $\mathrm{\Delta }{W}_j\in o_{lkjih}$ change $W$? Which subsequence matrices change? Which subsequence matrices change rank? Which subsequence matrices undergo a change in rowspace or columnspace? The three lemmas below answer these questions, and Figure 6 summarizes the answers. (Figure 6 assumes the displacement $\mathrm{\Delta }{W}_j$ is nonzero; the lemmas do not.) These answers explain why we chose subspaces of the form $o_{lkjih}=a_{lji}\otimes b_{k,j-1,h}$.

As $W=W_{L◀0}$, Lemma 3 tells us that a basic move moves off the fiber ${\mu }^{-1}(W)$ if and only if $\mathrm{\Delta }\theta$ is a nonzero displacement from a subspace ${\varphi }_{lkjih}$ with $l=L$ and $h=0$. This motivates us to define a set of one-matrix subspaces that signify basic moves that stay on the fiber.

A discrete move is a move that changes the ranks of one or more subsequence matrices. If a discrete move stays on the fiber, it moves from one stratum to a different stratum. Lemma 5 tells us two ways a basic move can be discrete. Every subsequence matrix $W_{t◀s}$ with $t\in [k+1,l]$ and $s\in [h,i-1]$ increases in rank, and their ranks all increase by the same amount: the rank of $\mathrm{\Delta }{W}_j$. A subsequence matrix $W_{t◀s}$ with $t\in [j,k]$ and $s\in [i,j-1]$ might decrease in rank, but not if $\Vert \mathrm{\Delta }{W}_j\Vert$ is sufficiently small.

A small move is a move that does not decrease the rank of any subsequence matrix. (Rather than fuss over “is $\Vert \mathrm{\Delta }{W}_j\Vert$ small enough?”, we define “small move” to meet our needs.) If a small, discrete move stays on the fiber, it moves to a stratum of higher dimension.

By Lemma 5, a small, basic move with displacement $\mathrm{\Delta }\theta \in {\varphi }_{lkjih}$ is discrete if and only if $\mathrm{\Delta }\theta \ne \mathrm{𝟎}$, $l>k$, and $i>h$ (so $[k+1,l]\ne \mathrm{\varnothing }$ and $[h,i-1]\ne \mathrm{\varnothing }$). We define a set of one-matrix subspaces that signify basic moves that increase the rank of some subsequence matrix.

To understand how the strata are connected to each other in the rank stratification of a fiber, it suffices to study small moves with displacements from subspaces in ${\mathrm{\Theta }}_{\mathrm{O}}^{\mathrm{fiber}}\cap {\mathrm{\Theta }}_{\mathrm{O}}^{\mathrm{barc}}$. Given a subspace ${\varphi }_{lkjih}\in {\mathrm{\Theta }}_{\mathrm{O}}^{\mathrm{fiber}}\cap {\mathrm{\Theta }}_{\mathrm{O}}^{\mathrm{barc}}$, let $\theta +{\varphi }_{lkjih}$ denote the affine subspace produced by translating ${\varphi }_{lkjih}$ to pass through $\theta$. By Lemma 3, $\theta +{\varphi }_{lkjih}\subseteq {\mu }^{-1}(W)$, but by Lemma 5, no point in $\theta +{\varphi }_{lkjih}$ except $\theta$ lies on the stratum $S$ that contains $\theta$. Whereas given a subspace ${\varphi }_{lkjih}\in {\mathrm{\Theta }}_{\mathrm{O}}^{\mathrm{fiber}}\setminus {\mathrm{\Theta }}_{\mathrm{O}}^{\mathrm{barc}}$, $\theta +{\varphi }_{lkjih}\subseteq \overline{S}$. These facts give us some hints about the connections among the strata and the shape of the stratification (albeit without addressing its curvature).

Interestingly, although a small, basic move may change the ranks of many subsequence matrices, at most four interval counts change. Recall the identity (1): ${\omega }_{ts}=\mathrm{rk}{W}_{t◀s}-\mathrm{rk}{W}_{t◀s-1}-\mathrm{rk}{W}_{t+1◀s}+\mathrm{rk}{W}_{t+1◀s-1}$. If all four ranks increase by $\mathrm{rk}\mathrm{\Delta }{W}_j$, or exactly two ranks with opposite signs do, then ${\omega }_{ts}$ does not change.

For a small displacement $\mathrm{\Delta }\theta \in {\varphi }_{lkjih}\in {\mathrm{\Theta }}_{\mathrm{O}}^{\mathrm{barc}}$, it is straightforward to check that ${\omega }_{kh}$ and ${\omega }_{li}$ decrease by $\mathrm{rk}\mathrm{\Delta }{W}_j$, ${\omega }_{lh}$ and ${\omega }_{ki}$ increase by $\mathrm{rk}\mathrm{\Delta }{W}_j$, and no other interval count changes. The barcode encodes the changes made by small, basic, discrete moves more elegantly than the rank list does. (The rank list is a summed-area table [6] of the interval counts.)

A barcode move is a small, basic, discrete move. There are two types of barcode moves: connecting moves and swapping moves. Every subspace ${\varphi }_{lkjih}\in {\mathrm{\Theta }}_{\mathrm{O}}$ has indices satisfying $k+1\ge j\ge i$. A connecting move is a small move with a nonzero displacement $\mathrm{\Delta }\theta \in {\varphi }_{lkjih}\in {\mathrm{\Theta }}_{\mathrm{O}}^{\mathrm{barc}}$ in the case where $k+1=j=i$. In a connecting move, ${\omega }_{ki}$ does not exist (as ) and only three interval counts change. Figure 7 illustrates two examples of connecting moves and offers an interpretation in terms of a changing barcode: a connecting move deletes $\mathrm{rk}\mathrm{\Delta }{W}_j$ copies of the interval $[h,k]$ and $\mathrm{rk}\mathrm{\Delta }{W}_j$ copies of the interval $[i,l]$, and replaces them with $\mathrm{rk}\mathrm{\Delta }{W}_j$ copies of the interval $[h,l]$. We think of this as connecting the intervals $[h,k]$ and $[i,l]$ together with an added link $[j-1,j]=[k,i]$ to create an interval $[h,l]$; hence the name “connecting move.” (There is much intuition that can be gleaned from a careful study of the figure that is hard to explain in words.) The rank of a connecting move is $\mathrm{rk}\mathrm{\Delta }{W}_j$.

A swapping move is a small move with a nonzero displacement $\mathrm{\Delta }\theta \in {\varphi }_{lkjih}\in {\mathrm{\Theta }}_{\mathrm{O}}^{\mathrm{barc}}$ in the case where $k\ge i$. A swapping move changes four interval counts. Figure 8 illustrates two examples. A swapping move splices $\mathrm{rk}\mathrm{\Delta }{W}_j$ copies of the interval $[h,k]$ with $\mathrm{rk}\mathrm{\Delta }{W}_j$ copies of the interval $[i,l]$, replacing them with $\mathrm{rk}\mathrm{\Delta }{W}_j$ copies of the interval $[h,l]$ (which is longer than both of the replaced intervals) and $\mathrm{rk}\mathrm{\Delta }{W}_j$ copies of the interval $[i,k]$ (which is shorter than both). In effect, the interval endpoints are swapped. (Again, careful study of the figure is rewarding.) The rank of a swapping move is $\mathrm{rk}\mathrm{\Delta }{W}_j$.

Each barcode move has an effect on the rank list (and the barcode) that depends solely on the indices $h$, $i$, $k$, and $l$ and the rank of $\mathrm{\Delta }{W}_j$. This motivates the idea of an abstract move that maps one rank list to another rank list, and one barcode to another barcode, divorced entirely from any geometry. A rank-$c$ abstract barcode move takes a valid rank list $\underset{¯}{r}$ and an index tuple $(l,k,i,h)$ satisfying $L\ge l\ge k+1\ge i>h\ge 0$, and yields the modified rank list $\underset{¯}{z}$ produced by setting $z_{t◀s}=r_{t◀s}+c$ for $t\in [k+1,l],s\in [h,i-1]$; for the other ranks, $z_{t◀s}=r_{t◀s}$. Equivalently, it takes the barcode for $\underset{¯}{r}$, decreases ${\omega }_{li}$ and ${\omega }_{kh}$ by $c$, and increases ${\omega }_{lh}$ and ${\omega }_{ki}$ by $c$ – except that if $k+1=i$, then ${\omega }_{ki}$ does not exist and only three interval counts change (an abstract connecting move). An abstract barcode move produces a valid rank list if and only if ${\omega }_{li}\ge c$ and ${\omega }_{kh}\ge c$ prior to the move.

We think the most interesting aspect of this paper is that the hierarchy of strata is captured by these simple discrete operations on barcodes – barcodes that indicate the flow of information through the neural network. Barcode moves create farther-reaching flows and may offer network training algorithms more opportunities to succeed.

We return to the hard part of Theorem 1, the claim that statement C implies statement D: if $\underset{¯}{r}\le \underset{¯}{z}$, there exists a sequence of rank-one abstract barcode moves that takes us from $\underset{¯}{r}$ to $\underset{¯}{z}$. This claim is a bridge to showing that $S_{\underset{¯}{r}}\subseteq {\overline{S}}_{\underset{¯}{z}}$ if and only if $\underset{¯}{r}\le \underset{¯}{z}$.

Given rank lists $\underset{¯}{r}$ and $\underset{¯}{z}$ with , finding a sequence of abstract moves that takes us from $\underset{¯}{r}$ to $\underset{¯}{z}$ is a puzzle that took us three months to solve. The full proof does not fit here, but we include the constructive part of the proof: the algorithm FindLastMove in Figure 9 finds a rank list $\underset{¯}{u}$ such that and a single rank-one abstract barcode move takes us from $\underset{¯}{u}$ to $\underset{¯}{z}$. Building on this step, a simple recursive algorithm, FindDAGPath in Figure 9, finds a sequence of abstract barcode moves that take us from $\underset{¯}{r}$ to $\underset{¯}{z}$ (computing the sequence in reverse order, from $\underset{¯}{z}$ to $\underset{¯}{r}$). The proof of correctness of FindDAGPath, and thus the proof that C implies D, follows by induction.

FindLastMove and our proofs use differences between the rank lists $\underset{¯}{r}$ and $\underset{¯}{z}$. Let the interval counts associated with $\underset{¯}{r}$ be ${\omega }_{ts}^r$ and the interval counts associated with $\underset{¯}{z}$ be ${\omega }_{ts}^z$. Let

As we assume that $\underset{¯}{r}\le \underset{¯}{z}$, no $\mathrm{\Delta }{r}_{t◀s}$ is negative. (No such constraint applies to $\mathrm{\Delta }{\omega }_{ts}$.)

Figure 10 depicts examples of reverse moves found by FindLastMove, and thereby sheds light on Lines 7–13, the core of the algorithm. In each example, a red rectangle shows which reverse move the algorithm finds – specifically, the index tuple $(l,k,i,h)$ of the move. Line 7 selects $l$ and $h$ so that the bottom corner of the red rectangle, $\mathrm{\Delta }{\omega }_{lh}$, is a bottommost positive $\mathrm{\Delta }\omega$. (Equivalently, the bottommost rank inside the rectangle, $\mathrm{\Delta }{r}_{l◀h}$, is a bottommost positive $\mathrm{\Delta }r$.) Lines 8–13 search for values of $k$ and $i$ such that every $\mathrm{\Delta }r$ inside the rectangle is positive and the rectangle’s top corner is either at a positive $\mathrm{\Delta }{\omega }_{ki}$ or between two $\mathrm{\Delta }d$’s ($k=i-1$) – these constraints guarantee that a reverse move yields a valid rank list. The hard part of our proof is showing that there always exists a rectangle satisfying these constraints.

Lines 8–9 check whether such a rectangle exists with $k=l-1$. If so, Line 10 sets $i$ to indicate the smallest such rectangle; see Figures 10(a) and (b) for examples. If not, the obstacle is some $\mathrm{\Delta }{r}_{l◀i^{\prime }}$ equal to zero. In that case, Lines 12–13 find values of $k$ and $i$ that satisfy the constraints; see Figures 10(c) and (d) for examples. Showing that Lines 12–13 always succeed is the part of the proof we must omit here. (It takes about two pages.)

We conclude with the hard part of Theorem 1.

Small moves are our tool for understanding stratum connections. But we speculate that longer moves on the fiber might be useful in practice to replace a neural network with an equivalent network more amenable to training by gradient descent algorithms, because barcode moves create farther-reaching flows, and longer moves make those flows stronger. A related idea is to modify gradient descent so it tends to move away from “bad” strata.

Given a smooth function $\mathrm{\ell }(W)$, Trager, Kohn, and Bruna [23] call $\theta$ a spurious critical point if $\theta$ is a critical point of $\mathrm{\ell }(\mu (\theta ))$ but $\mu (\theta )$ is not a critical point of $\mathrm{\ell }$ (where the domain of $\mathrm{\ell }$ is restricted to matrices of rank ${\min }_{j=0}^L{d}_j$ or less). They show that there is no spurious critical point on ${\mu }^{-1}(W)$ if $\mathrm{rk}W={\min }_{j=0}^L{d}_j$; also that there is no spurious critical point on any stratum $S_{\underset{¯}{r}}$ that satisfies, for some $j\in [1,L]$, both $r_{L◀j}=d_L$ and $r_{j-1◀0}=d_0$.

We anticipate that geometric interpretations of cost functions in neural networks have the potential to become a thriving area, especially if we can incorporate ReLU activations.