# Local and global topological complexity measures of ReLU neural network
functions

J. Elisenda Grigsby  Boston College; Department of Mathematics; 522 Maloney
Hall; Chestnut Hill, MA 02467<EMAIL_ADDRESS>,  Kathryn Lindsey  Boston
College; Department of Mathematics; 567 Maloney Hall; Chestnut Hill, MA 02467
<EMAIL_ADDRESS>and  Marissa Masden  University of Oregon; Department of
Mathematics, Fenton Hall; Eugene, OR 97403-1222 USA<EMAIL_ADDRESS>
###### Abstract.

We apply a generalized piecewise-linear (PL) version of Morse theory due to
Grunert-Kühnel-Rote to define and study new local and global notions of
topological complexity for fully-connected feedforward ReLU neural network
functions $F:\mathbb{R}^{n}\rightarrow\mathbb{R}$. Along the way, we show how
to construct, for each such $F$, a canonical polytopal complex
$\mathcal{K}(F)$ and a deformation retract
$\mathbb{R}^{n}\rightarrow\mathcal{K}(F)$, yielding a convenient compact model
for performing calculations. We also give a combinatorial description of local
complexity for depth $2$ networks, and a construction showing that local
complexity can be arbitrarily high.

JEG was partially supported by Simons Collaboration grant 635578 and NSF grant
DMS - 2133822.

KL was partially supported by NSF grants DMS - 1901247 and DMS - 2133822.

##  1\. Introduction

It is well-known (e.g. [1]) that the class of functions
$F:\mathbb{R}^{n}\rightarrow\mathbb{R}$ realizable by feedforward ReLU neural
networks is precisely the class of finite piecewise linear (PL) functions
(Definition 3.3). Less well-understood is how architecture impacts function
complexity and how complexity evolves during training. That is, for a fixed
architecture of fully-connected, feedforward ReLU neural network, how does the
set of finite PL functions realizable by that architecture sit inside the set
of all finite PL functions? Do the dynamics of stochastic gradient descent
preference certain classes of finite PL functions over others? In order to
tackle these questions in a systematic way, we need a good framework for
characterizing the complexity of finite PL functions. In the present work, we
draw on algebraic topology and a PL version of Morse theory to develop a new
notion of complexity.

The idea of using Betti numbers of sublevel sets as a measure of complexity
for neural network functions was initiated in [3]. Recall that the Betti
numbers of a topological space are the ranks of its homology groups (see e.g.
[10]), and they are invariants of the space up to homeomorphism (in fact, up
to the weaker notion of homotopy equivalence, see Definition 4.2). In [3] and,
later, [8], the homological or topological complexity of a continuous function
$F:\mathbb{R}^{n}\rightarrow\mathbb{R}$ was defined as the collection of Betti
numbers of the (single) sublevel set $F_{\leq 0}:=F^{-1}(-\infty,0].$ In [3],
the authors explore how homological complexity grows with respect to depth and
width for neural networks with polynomial and $\arctan$ activation functions,
and in [8], the authors use persistent homology, introduced by Zomorodian-
Carlsson in [15], to perform an empirical study of the homological complexity
of ReLU neural networks of varying architectures. We note that modern
practitioners favor the ReLU activation function for supervised learning
problems involving regression.

Our study begins with the observation that another natural and complementary
notion of complexity of a continuous function

$F:\mathbb{R}^{n}\rightarrow\mathbb{R}$

is the number of homeomorphism classes of its sublevel sets,

$F_{\leq a}:=F^{-1}(-\infty,a],\mbox{ for }a\in\mathbb{R}.$

For a _smooth_ function $F$, Morse theory provides a toolkit for not only
computing algebro-topological invariants of the sublevel sets (e.g., their
Betti numbers) but also understanding how they change as the threshold $t=a$
varies. Put simply, for a smooth function
$F:\mathbb{R}^{n}\rightarrow\mathbb{R}$, the homeomorphism class of a sublevel
(or superlevel) set can only change across a critical point, where the
gradient of $F$ vanishes. Moreover, generic smooth functions are Morse, which
means that the critical points are isolated and admit a standard quadratic
local model. These conditions yield a straightforward description of how the
topology of the sublevel set changes as the threshold crosses the critical
value; the change is local, controlled, and relatively easy to describe.

Figure 1. Algebro-topological invariants of the sublevel sets $F_{\leq t}$ of
a function $F:\mathbb{R}^{n}\rightarrow\mathbb{R}$ for varying
$t\in\mathbb{R}$ give strong information about the complexity of the function.

For PL functions $\mathbb{R}^{n}\rightarrow\mathbb{R}$, it is still natural to
define a notion of complexity based on algebro-topological descriptions of
homeomorphism classes of sublevel (or superlevel) sets. However, in contrast
to the smooth setting, a generic finite PL function is not necessarily PL
Morse (see Section 3); consequently, describing how the homological complexity
of a sublevel set $F_{\leq a}$ varies with $a\in\mathbb{R}$ requires a more
delicate analysis.

Following ideas dating back to Banchoff [2], we focus our attention on the
flat cells of a ReLU neural network map
$F:\mathbb{R}^{n}\rightarrow\mathbb{R}$. The _canonical polyhedral complex_
$\mathcal{C}(F)$ associated to a feedforward ReLU neural network map
$F:\mathbb{R}^{n}\to\mathbb{R}$ was introduced in [4]; informally, it is a
decomposition of $\mathbb{R}^{n}$ into convex polyhedra (cells) of varying
dimension such that $F$ is affine-linear on each cell.

The flat cells of $F$ are, by definition, the cells of $\mathcal{C}(F)$ on
which $F$ is constant. Flat cells in the PL category should be viewed as the
appropriate analogues of critical points in the smooth category, with the
caveat that not every flat cell is critical. Explicitly, we prove:

######  Theorem 1.

Let $F:\mathbb{R}^{n}\rightarrow\mathbb{R}$ be a finite PL function, and let
$a\leq b\in\mathbb{R}$ be thresholds. If the polyhedral complex
$\mathcal{C}(F)_{F_{\in[a,b]}}$ contains no flat cells, then the sublevel sets
$F_{\leq a}$ and $F_{\leq b}$ are homotopy equivalent, as are the superlevel
sets $F_{\geq a}$ and $F_{\geq b}$.

Here, $\mathcal{C}(F)_{F_{\in[a,b]}}$ is a level set complex (see §2 for the
precise definition); it is, roughly speaking, the restriction of the complex
$\mathcal{C}(F)$ to the set $F^{-1}([a,b])$. Homotopy equivalence is an
equivalence relation on topological spaces that is weaker than homeomorphism
but strong enough to imply the equality of all standard invariants coming from
algebraic topology (cf. Section 4 and [10]). Moreover, since a finite PL map
has finitely many flat cells, an immediate consequence of Theorem 1 is that
there are finitely many homotopy equivalence classes of sublevel sets – i.e.
for a feedforward ReLU neural network function $F$, we need only consider
finitely many sublevel sets $F_{\leq a}$, $a\in\mathbb{R}$, to capture all of
the topological complexity information associated to $F$.

To this end, we may first consider the sublevel sets $F_{\leq a}$ (resp.
superlevel sets $F_{\geq a}$) for very negative (resp. very positive) values
of $a\in\mathbb{R}$. Indeed, if the images of all flat cells are contained in
the compact interval $[-M,M]$, then the homology of $F_{\leq a}$ and $F_{\leq
b}$ agree for all $a,b<-M$ and the homology of $F_{\geq a}$ and $F_{\geq b}$
agree for all $a,b>M$. Consequently, a first (coarse) description of the
topological topological complexity of $F$ is given by:

  * •

the collection of Betti numbers of the set $F_{\leq a}$ for any $a<-M$, which
we call the stable sublevel homological complexity of $F$, or stable sublevel
$H$–complexity for short, and

  * •

the collection of Betti numbers of $F_{\geq a}$ for any $a>M$, which we call
the stable superlevel $H$–complexity of $F$.

Next, we may investigate how the sublevel sets $F_{\leq t}$ (and superlevel
sets $F_{\geq t}$) change as we vary $t\in[-M,M]$. In analogy to the smooth
setting, our preference would be to apply PL Morse theory (as developed in
[6]) to the class of finite PL maps realized by ReLU neural network functions,
but we quickly see that ReLU neural network functions have a nonzero
probability of being non PL Morse (Definition 3.5):

######  Theorem 2.

Let $F:\mathbb{R}^{n}\rightarrow\mathbb{R}$ be a ReLU neural network map with
hidden layers of dimensions $(n_{1},\ldots,n_{\ell})$. The probability that
$F$ is PL Morse is

(1) $\left\\{\begin{array}[]{cl}=\frac{\sum_{k=n+1}^{n_{1}}{n_{1}\choose
k}}{2^{n_{1}}}&\mbox{if $\ell=1$}\\\
\leq\frac{\sum_{k=n+1}^{n_{1}}{n_{1}\choose k}}{2^{n_{1}}}&\mbox{if
$\ell>1.$}\end{array}\right.$

We remark that the expression (1) above for the probability is

$\left\\{\begin{array}[]{cl}0&\mbox{if $n_{1}\leq n$}\\\
\leq\frac{1}{2}&\mbox{if $n_{1}\leq 2n+1$}.\end{array}\right.$

Additionally, note that for architectures whose hidden layers all have the
same dimension (a common choice), the upper bound given by Theorem 2 is
significantly lower for deep networks than for shallow networks of the same
total dimension. For ReLU neural networks with $>1$ hidden layer, we expect
the true probability that $F$ is PL Morse to be much lower than the given
upper bound.

Thus, in order to measure how the sublevel sets $F_{\leq t}$ change as we vary
the threshold $t$, we need to do more work. Following [7], we associate to
each (connected component of)111Flat cells of PL maps need not be isolated.
flat cell(s) $K$ at level $t$ its local homological complexity (or local
$H$–complexity for short), which we define to be the rank of the relative
homology of the pair $(F_{\leq t},F_{\leq t}\setminus K)$. (Readers unfamiliar
with relative homology may informally view the local $H$–complexity of $K$ as
the (total rank of the) homology of the quotient space obtained by collapsing
everything in $F_{\leq t}$ outside of a neighborhood of $K$ to a point; for
more detail see [10].) We may then define the total $H$–complexity of a finite
PL map to be the sum of all the local $H$–complexities. It is noted in [7]
that PL Morse regular points have local $H$–complexity $0$ and PL Morse
nondegenerate-critical points have local $H$–complexity $1$.

To prove Theorem 1 we draw heavily upon Grunert’s work in [6], where he proves
an analogous result for _bounded_ polyhedral complexes, aka polytopal
complexes.

We apply results in convex geometry and combinatorics (cf. [12]) to construct,
for every ReLU neural network map $F:\mathbb{R}^{n}\rightarrow\mathbb{R}$ with
canonical polyhedral complex $\mathcal{C}(F)$, a _canonical polytopal complex_
, $\mathcal{K}(F)$, and a homotopy equivalence
$|\mathcal{C}(F)|\sim|\mathcal{K}(F)|$ (we use $|\cdot|$ to denote the
underlying set of a polyhedral complex) that respects the finite PL map $F$:

######  Theorem 3.

Let $\mathcal{C}$ be a polyhedral complex in $\mathbb{R}^{n}$, let
$F:|\mathcal{C}|\to\mathbb{R}$ be linear on cells of $\mathcal{C}$, and assume
$|\mathcal{C}_{F\in[a,b]}|\subseteq|\mathcal{C}|$ contains no flat cells. Then
there exists a polytopal complex $\mathcal{D}$ with
$|\mathcal{D}|\subset|\mathcal{C}|$ and a strong deformation retraction
$\Phi:|\mathcal{C}|\to|\mathcal{D}|$ (which induces a cellular map
$\mathcal{C}\to\mathcal{D}$) such that $\Phi$ is $F$-level preserving on
$|\mathcal{C}_{F\in[a,b]}|$ and for every $c\in[a,b]$,

(2) $\Phi(|\mathcal{C}_{F\leq c}|)=|\mathcal{D}_{F\leq
c}|,\quad\Phi(|\mathcal{C}_{F\geq c}|)=|\mathcal{D}_{F\geq c}|.$

Furthermore, there is an $F$-level preserving PL isotopy

$\phi:|\mathcal{D}|_{F=c}\times[a,b]\to|\mathcal{D}_{F\in[a,b]}|.$

Combined with results of Grunert ([6]) for polytopal complexes, this
immediately implies:

######  Theorem 4.

Let $\mathcal{C}$ be a polyhedral complex in $\mathbb{R}^{n}$, let
$F:|\mathcal{C}|\to\mathbb{R}$ be linear on cells of $\mathcal{C}$, and assume
$|\mathcal{C}_{F\in[a,b]}|\subseteq|\mathcal{C}|$ contain no flat cells. Then
for any threshold $c\in[a,b]$, $|\mathcal{C}_{F\leq c}|$ is homotopy
equivalent to $|\mathcal{C}_{F\leq a}|$; also $|\mathcal{C}_{F\geq c}|$ is
homotopy equivalent to $|\mathcal{C}_{F\geq b}|$.

Because polytopal complexes admit finite simplicial subdivisions and there
exist finite time algorithms for computing homology for finite simplicial
complexes, Theorems 3 and 4 together have the following important practical
consequence, which we state informally:

For every flavor of $H$–complexity described in this paper and every finite PL
map $F:\mathbb{R}^{n}\rightarrow\mathbb{R}$, there exists a finite time
algorithm for computing the $H$–complexity of $F$.

After establishing these foundational preliminaries, we turn our attention to
bounds, computations, and examples. In Section 6 we provide a useful
combinatorial characterization of the local complexity of flat cells in
shallow (i.e., depth $2$) ReLU neural networks in terms of the $\nabla F$
orientation on the $1$–complex of $\mathcal{C}(F)$. In Section 7, we introduce
the stable sublevel and superlevel $H$–complexities as well as the coarse
bounded sublevel and superlevel $H$–complexities of a finite PL function
$F:\mathbb{R}^{n}\rightarrow\mathbb{R}$. These are significantly less
computationally expensive than total $H$–complexity but provide a reasonable
measure of topological complexity in their own right. We also establish the
following weak but computationally inexpensive lower bounds for coarse
$H$–complexity:

######  Theorem 5.

Let $F:\mathbb{R}^{n}\rightarrow\mathbb{R}$ be a finite PL function for which
the images of the flat cells are contained in the interval $[-M,M]$. Let
$n_{\pm}$ denote the number of connected components of $F_{\leq\pm M}$ and let
$n^{\pm}$ denote the number of connected components of $F_{\geq\pm M}$. We
have the following lower bounds:

  1. (i)

$|n_{-}-n_{+}|$ is a lower bound for the coarse bounded sublevel
$H$–complexity

  2. (ii)

$|n^{+}-n^{-}|$ is a lower bound for the coarse bounded superlevel
$H$–complexity

We close, in Section 8, by presenting a construction proving that local
$H$–complexity of a ReLU neural network function can be arbitrarily large.

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries
    1. 2.1 Polyhedral complexes
    2. 2.2 Feedforward ReLU neural networks: genericity, transversality and canonical polyhedral complex
  3. 3 PL Morse theory and flat versus critical cells
    1. 3.1 PL $n$–manifolds and PL Morse functions
    2. 3.2 Flat cells, nontransversal thresholds, and general maps
    3. 3.3 Flat cells for ReLU layer maps and proof of Theorem 2
  4. 4 Global and Local H-complexity
  5. 5 Sublevel sets of finite PL maps are homotopy equivalent within transversal intervals
    1. 5.1 The canonical polytopal complex of a pointed polyhedral complex
    2. 5.2 Deformation retraction of a pointed polyhedral complex of $\mathbb{R}^{n}$ to its canonical polytopal complex
      1. 5.2.1 The base map
    3. 5.3 The canonical polytopal complex of unpointed polyhedral complexes
      1. 5.3.1 Unpointed polyhedral complexes and their essentializations
    4. 5.4 Homotopy equivalence of sublevel sets
      1. 5.4.1 The pointed case
      2. 5.4.2 The unpointed case
  6. 6 Morse classification of points for shallow neural network functions
  7. 7 Stable H-complexity, coarse H-complexity, and bounds
    1. 7.1 Stable and coarse H-complexity
    2. 7.2 Upper bounds on global H-complexity
  8. 8 Local $H$–complexity can be arbitrarily large

### Acknowledgments

The authors would like to thank B. Hanin, M. Telgarsky, and D. Rolnick for
interesting conversations.

##  2\. Preliminaries

We briefly recall some definitions and constructions in convex geometry, along
with how they appear in the geometry of ReLU neural networks. We refer the
reader to [5, 6, 4] for more details.

###  2.1. Polyhedral complexes

An (affine) hyperplane $H\subseteq\mathbb{R}^{n}$ is any subset of the form
$H=\\{\vec{x}\in\mathbb{R}^{n}\,\,|\,\,\vec{w}\cdot\vec{x}+b=0\\}$ for some
$b\in\mathbb{R}$ and nonzero $\vec{w}\in\mathbb{R}^{n}$. If $H$ has been
specified as above by a pair $(\vec{w},b)$, then it is equipped with a co-
orientation in the direction of $\vec{w}$, dividing $\mathbb{R}^{n}$ into two
closed half-spaces:

$\displaystyle H^{+}$ $\displaystyle:=$
$\displaystyle\\{\vec{x}\in\mathbb{R}^{n}\,\,|\,\,\vec{w}\cdot\vec{x}+b\geq
0\\}$ $\displaystyle H^{-}$ $\displaystyle:=$
$\displaystyle\\{\vec{x}\in\mathbb{R}^{n}\,\,|\,\,\vec{w}\cdot\vec{x}+b\leq
0\\},$

A polyhedral set $\mathcal{P}$ in $\mathbb{R}^{n}$ is an intersection of
finitely many closed half-spaces in $\mathbb{R}^{n}.$ That is, a polyhedral
set is any subset of $\mathbb{R}^{n}$ that can be written as
$H_{1}^{+}\cap\ldots\cap H_{k}^{+}$ for some co-oriented hyperplanes
$H_{1},\ldots,H_{k}$. A polytope in $\mathbb{R}^{n}$ is a bounded polyhedral
set.

Given a polyhedral set $\mathcal{P}$ and hyperplane $H$ in $\mathbb{R}^{n}$,
$H$ is called a cutting hyperplane of and is said to _cut_ $P$ if $H$ has
nonempty intersection with the interior of $P$, and $H$ is called a supporting
hyperplane of $P$ and is said to support $P$ if $H$ does not cut $P$ and
$H\cap P\neq\emptyset$. The _dimension_ of a polyhedral set $P$ is the
dimension of its _affine hull_ $\textrm{aff}(P)$, which is the the
intersection of all affine-linear subspaces of $\mathbb{R}^{n}$ that contain
$P$. A subset $F$ of a polyhedral set $P$ is said to be a face of $P$ if
either $F=\emptyset$, $F=P$, or $F=H\cap P$ for some supporting hyperplane of
$\mathcal{P}$.

A polyhedral complex $\mathcal{C}$ of dimension $d$ is a finite set of
polyhedral sets of dimension $k$, for $0\leq k\leq d$, called the _cells_ of
$\mathcal{C}$, such that i) If $P\in\mathcal{C}$, then every face of $P$ is in
$\mathcal{C}$, and ii) if $P,Q\in\mathcal{C}$, then $P\cap Q$ is a single
mutual face of $P$ and $Q$. A _polytopal complex_ is a polyhedral complex in
which all the polyhedral cells are polytopes (i.e. bounded). A _simplicial
complex_ is a polytopal complex in which all polytopes are simplices. Any
polytopal complex admits a finite simplicial subdivision, which can, if
desired, be constructed without introducing new vertices, cf. [6, Fact 1.25].
It is immediate that a map that is affine-linear on cells of a simplicial
complex is uniquely determined by the images of the vertices ($0$–cells). The
_domain_ or _underlying set_ $|\mathcal{C}|$ of a polyhedral complex
$\mathcal{C}$ is the union of its cells. If $\mathcal{C}$ is a polyhedral
complex embedded in $\mathbb{R}^{n}$ and $|\mathcal{C}|=\mathbb{R}^{n}$, we
call $\mathcal{C}$ a polyhedral decomposition of $\mathbb{R}^{n}$.

The _intersection complex_ (c.f. [6] Definition 1.16)
$\mathcal{K}\cap\mathcal{L}$ of two polyhedral complexes $\mathcal{K}$ and
$\mathcal{L}$ in $\mathbb{R}^{n}$ is the complex consisting of all pairwise
intersections $S\cap T$ of cells $S\in\mathcal{K}$ and $T\in\mathcal{L}$, i.e.

$\mathcal{K}\cap\mathcal{L}\coloneqq\\{S\cap T\mid
S\in\mathcal{K},T\in\mathcal{L}\\}.$

By construction,
$|\mathcal{K}\cap\mathcal{L}|=|\mathcal{K}|\cap|\mathcal{L}|$. Now allowing
$\mathcal{K}$ and $\mathcal{L}$ to be embedded in different Euclidean spaces,
given a function $f:|\mathcal{K}|\to|\mathcal{L}|$ that is affine-linear on
cells of $\mathcal{K}$, the _level set complex_ (c.f. [6] Definition 2.6) of
$\mathcal{K}$ with range $\mathcal{L}$ is the polyhedral complex

$\mathcal{K}_{f\in\mathcal{L}}\coloneqq\\{K\cap f^{-1}(L)\mid
K\in\mathcal{K},L\in\mathcal{L}\\}.$

When the map $f$ is clear from context, we will suppress the $f$ and write
$\mathcal{K}_{\in\mathcal{L}}$. By construction,
$|\mathcal{K}_{\in\mathcal{L}}|=|\mathcal{K}|\cap f^{-1}(|\mathcal{L}|)$. In
particular, when $\mathcal{L}$ is a interval complex in $\mathbb{R}$ of the
form $\\{t\\},[t_{1},t_{2}],(-\infty,t]$ or $[t,\infty)$ (together with their
faces), we denote the associated level set complexes $\mathcal{K}_{=t}$,
$\mathcal{K}_{[t_{1},t_{2}]}$, $\mathcal{K}_{\leq t}$ and $\mathcal{K}_{\geq
t}$, respectively. We call $\mathcal{K}_{\leq t}$ (resp. $\mathcal{K}_{\geq
t}$) a _sublevel_ (resp. _superlevel_) _set complex_.

###  2.2. Feedforward ReLU neural networks: genericity, transversality and
canonical polyhedral complex

The ReLU activation function, $\textrm{ReLU}:\mathbb{R}\to\mathbb{R}$, is
defined by $\textrm{ReLU}(x)=\max\\{0,x\\}$; for any $n\in\mathbb{N}$, denote
by $\sigma$ the function $\mathbb{R}^{n}\to\mathbb{R}^{n}$ that applies ReLU
in each coordinate. A fully connected, feedforward ReLU neural network defined
on $\mathbb{R}^{n_{0}}$, $n_{0}\in\mathbb{N}$, with one-dimensional output is
a finite sequence of natural numbers $n_{0},n_{1},\dots,n_{m}$ together with
affine-linear maps $A_{i}:\mathbb{R}^{n_{i}}\to\mathbb{R}^{n_{i+1}}$ for
$i=0,\dots,m$. This determines a function

$F:\mathbb{R}^{n_{0}}\xrightarrow{F_{1}=\sigma\circ
A_{1}}\mathbb{R}^{n_{1}}\xrightarrow{F_{2}=\sigma\circ
A_{2}}\ldots\xrightarrow{F_{m}=\sigma\circ
A_{m}}\mathbb{R}^{n_{m}}\xrightarrow{G=A_{m+1}}\mathbb{R}^{1}.$

Such a neural network is said to be of _architecture_ $(n_{0},\dots,n_{m};1)$,
_depth_ $m+1$, and _width_ $\max\\{n_{1},\ldots,n_{m},1\\}$. The
$k^{\textrm{th}}$ _layer map_ of such a neural network is the composition
$\sigma\circ A_{k}$ for $k=1,\dots,m$ and is the map $G=A_{k}$ for $k=m+1$.
For each $i\in\\{1,\ldots,m\\}$ and $j\in\\{1,\ldots,n_{i}\\}$, the node map,
$F_{i,j}$, is the map

$\pi_{j}\circ A_{i}\circ F_{i-1}\circ\ldots\circ
F_{1}:\mathbb{R}^{n_{0}}\rightarrow\mathbb{R},$

where $\pi_{j}$ denotes projection onto the $j$th coordinate.

The standard polyhedral decomposition
$\mathcal{C}^{\textrm{std}}(\mathbb{R}^{n})$ of $\mathbb{R}^{n}$ is the
polyhedral decomposition induced by the standard coordinate hyperplane
arrangement $\mathcal{A}^{\textrm{std}}$ in $\mathbb{R}^{n}$ (consisting of
the $n$ hyperplanes defined by setting one coordinate to be $0$). Let

$F:\mathbb{R}^{n_{0}}\xrightarrow{F_{1}}\mathbb{R}^{n_{1}}\xrightarrow{F_{2}}\ldots\xrightarrow{F_{m}}\mathbb{R}^{n_{m}}\xrightarrow{A_{m+1}}\mathbb{R}^{1}$

be a feedforward ReLU neural network (all layer maps except the last map
$A_{m+1}$ have a ReLU factor). The reader can easily verify that the
_canonical polyhedral complex_ $\mathcal{C}(F)$ defined in [4] has the
following description as an intersection complex:

$\mathcal{C}(F)\coloneqq\mathcal{I}_{F_{1}\in\mathcal{C}^{std}(\mathbb{R}^{n_{1}})}\cap\mathcal{I}_{F_{2}\circ
F_{1}\in\mathcal{C}^{std}(\mathbb{R}^{n_{2}})}\cap\ldots\cap\mathcal{I}_{F_{m}\circ\ldots\circ
F_{1}\in\mathcal{C}^{std}(\mathbb{R}^{n_{m}})}$

where $\mathcal{I}$ is the polyhedral decomposition of $\mathbb{R}^{n_{0}}$
consisting of a single $n_{0}$-cell. By construction, $F$ is affine-linear on
cells of $\mathcal{C}(F)$.

The _affine solution set arrangement_ associated to a layer map $\sigma\circ
A_{i+1}:\mathbb{R}^{n_{i}}\to\mathbb{R}^{n_{i+1}}$ is the the collection $S$
of sets
$S_{j}\coloneqq\\{\vec{x}\in\mathbb{R}^{n_{i}}:\pi_{j}(A(\vec{x}))=0\\}$, for
$1\leq j\leq n_{i+1}$, where $\pi_{j}$ denotes projection onto the $j$th
coordinate. We call such an affine solution set _generic_ if for all subsets
$\\{S_{i_{1}},\ldots,S_{i_{p}}\\}\subseteq S$, it is the case that
$S_{i_{1}}\cap\ldots\cap S_{i_{p}}$ is an affine linear subspace of
$\mathbb{R}^{i}$ of dimension $i-p$, where a negative-dimensional intersection
is understood to be empty. In particular, each element of a generic affine
solution set arrangement is a hyperplane. We call the neural network map $F$
_generic_ if each of its layer maps has a generic affine solution set
arrangement ([4]).

The $1$-skeleton, $\mathcal{C}(F)_{1}$, of the canonical polyhedral complex is
an embedded linear graph in $\mathbb{R}^{n_{0}}$. This graph has a natural
partial orientation (see [4]), which we call the $\nabla F$–orientation: If
$F$ is nonconstant on $C$, orient $C$ in the direction in which $F$ increases.
If $F$ is constant on $C$, we leave it unlabeled and refer to $C$ as a flat
edge.

We say that a cell $C$ in the canonical polyhedral complex $\mathcal{C}(F)$ is
_flat_ if $F$ is constant on that cell. Note that $C\in\mathcal{C}(F)$ is flat
if and only if all $1$–dimensional faces of $C$ are unoriented with respect to
the $\nabla F$–orientation. The following lemma is immediate from the
definition of a transversal threshold in [4]; readers unfamiliar with [4] may
take this lemma as the definition of a nontransversal threshold.

######  Lemma 2.1.

For a neural network function $F:\mathbb{R}^{n}\rightarrow\mathbb{R}$, a
threshold $t\in\mathbb{R}$ is _nontransversal_ if and only if it is the image
of a flat cell $C$ in the canonical polyhedral complex $\mathcal{C}(F)$.

A neural network map

$F:\mathbb{R}^{n_{0}}\xrightarrow{F_{1}=\sigma\circ
A_{1}}\mathbb{R}^{n_{1}}\xrightarrow{F_{2}=\sigma\circ
A_{2}}\ldots\xrightarrow{F_{m}=\sigma\circ
A_{m}}\mathbb{R}^{n_{m}}\xrightarrow{G=A_{m+1}}\mathbb{R}^{1}.$

is called _transversal_ ([4]) if, for each $i\in\\{1,\ldots,m\\}$ and each
$j\in\\{1,\ldots,n_{i}\\}$, $t=0$ is a transversal threshold for the node map
$F_{i,j}:\mathbb{R}^{n_{0}}\to\mathbb{R}$.

The following lemma was essentially proved in [4]:

######  Lemma 2.2.

Let $F:\mathbb{R}^{n}\rightarrow\mathbb{R}$ be a ReLU neural network function
and $a\in\mathbb{R}$ a threshold. Then the level set $F_{=a}$, the sublevel
set $F_{\leq a}$, and the superlevel set $F_{\geq a}$ are domains of imbedded
polyhedral complexes in $\mathbb{R}^{n}$. Moreover, if $F$ is generic and
transversal and $a\in\mathbb{R}$ is a transversal threshold, then $F_{=a}$ has
dimension $n-1$.

###### Proof.

$F$ is linear on cells of the canonical polyhedral complex $\mathcal{C}(F)$,
so [6, Lem. 2.5] tells us that $F_{=a}$ (resp., $F_{\leq a}$ and $F_{\geq a}$)
is the domain of the polyhedral subcomplex $\mathcal{C}(F)_{\in\\{a\\}}$
(resp., $\mathcal{C}(F)_{\in\\{(-\infty,a]\\}}$ and
$\mathcal{C}(F)_{\in\\{[a,\infty)\\}}$ in the level set complex associated to
the polyhedral decomposition

$\\{(-\infty,a],\\{a\\},[a,\infty)\\}$

of the codomain, $\mathbb{R}$. If $F$ is generic and transversal and $a$ is a
transversal threshold, [4, Lem. 5.6] tells us $\mathcal{C}(F)_{\in\\{a\\}}$
has dimension $n-1$, as desired. ∎

##  3\. PL Morse theory and flat versus critical cells

As indicated in the introduction, studying the topology of sublevel sets of
finite PL functions is quite a bit more involved than it is in the smooth
case. The purpose of this section is to introduce the notion of a PL Morse
function (using the definition from [7], see also [6]) and prove that for each
architecture of depth $\geq 2$, a positive measure subset of ReLU neural
network functions fail to be PL Morse (Definition 3.5).

Precisely, we have:

######  Theorem 2.

Let $F:\mathbb{R}^{n}\rightarrow\mathbb{R}$ be a ReLU neural network map with
hidden layers of dimensions $(n_{1},\ldots,n_{\ell})$. The probability that
$F$ is PL Morse is

$\left\\{\begin{array}[]{cl}=\frac{\sum_{k=n+1}^{n_{1}}{n_{1}\choose
k}}{2^{n_{1}}}&\mbox{if $\ell=1$}\\\
\leq\frac{\sum_{k=n+1}^{n_{1}}{n_{1}\choose k}}{2^{n_{1}}}&\mbox{if
$\ell>1$}\end{array}\right.$

Indeed, we believe that the probability that a given ReLU neural network
function is non PL Morse grows with depth. Thus, studying the topology of the
sublevel sets of ReLU neural network functions requires establishing more
flexible results governing how the sublevel set varies with the threshold. We
will introduce suitable notions for our purposes in Section 4.

Unsurprisingly, the key to understanding how the topology of sublevel sets
changes as one varies the threshold are the PL analogues of points where the
gradient of the function vanishes, cf. Theorem 1. These are the so-called flat
or constant cells (Definition 3.7), which map to nontransversal thresholds
(cf. Lemma 2.1). Indeed, one should view the analogues of critical cells (both
Morse and non-Morse) in the PL category as an appropriate subset of the flat
cells. For experts familiar with the ways ReLU neural network functions can
degenerate, Lemma 3.12 should provide a clear explanation for why most ReLU
neural network functions are not PL Morse.

###  3.1. PL $n$–manifolds and PL Morse functions

We begin with the following preliminaries about PL $n$–manifolds and finite PL
maps.

######  Definition 3.1.

Let $U\subseteq\mathbb{R}^{n},V\subseteq\mathbb{R}^{m}$ be open sets. A
function $f:U\rightarrow V$ is said to be piecewise affine-linear (PL) if it
is continuous and there is a locally-finite decomposition $U=\bigcup_{i\in
I}K_{i}$ into connected, closed subsets $K_{i}\subseteq U$ with respect to
which $f|_{K_{i}}$ is affine-linear.

Recall that a decomposition $U=\bigcup_{i\in I}K_{i}$ is locally finite if
every point $x\in U$ has a neighborhood meeting finitely many $K_{i}$. A PL
homeomorphism is a bijective PL function whose inverse is PL.

######  Definition 3.2.

A topological $n$–manifold $M$ is a PL $n$–manifold if it is equipped with an
open covering $M=\bigcup_{i\in I}M_{i}$ and coordinate charts
$\psi_{i}:M_{i}\rightarrow(U_{i}\subseteq\mathbb{R}^{n})$ to open subsets of
$\mathbb{R}^{n}$ for which all transition maps

$\psi_{i}\circ\psi_{j}^{-1}:\psi_{j}(U_{i}\cap
U_{j})\rightarrow\psi_{i}(U_{i}\cap U_{j})$

are PL homeomorphisms.

######  Definition 3.3.

Let $M$ be a PL $n$–manifold. A continuous map $F:M\rightarrow\mathbb{R}^{m}$
is said to be finite PL if $M$ admits a finite polyhedral decomposition with
respect to which $F$ is affine-linear on cells with respect to the standard PL
structure on the codomain, $\mathbb{R}^{m}$. That is, there is an imbedded
finite polyhedral complex $\mathcal{C}\subseteq M$ and a compatible finite
atlas $\\{(M_{i},\psi_{i})\\}_{i\in I}$ for $M$ for which

  * •

$|\mathcal{C}|=M$, and

  * •

for every $n$–cell $C$ of $\mathcal{C}$ there exists some $M_{i}$ such that
$C\subset M_{i}$ and the map $(F\circ\psi_{i}^{-1})|_{\psi_{i}(C)}$ is affine-
linear.

######  Remark 3.4.

ReLU neural network functions $F:\mathbb{R}^{n}\rightarrow\mathbb{R}$ are
finite PL with respect to the standard PL structures on $\mathbb{R}^{n}$ and
$\mathbb{R}$.

We are now ready for the following definition, which is adapted from [7, Defn.
4.1].

######  Definition 3.5.

Let $M$ be a PL $n$–manifold and $F:M\rightarrow\mathbb{R}$ a finite PL map.

  * •

A point $p\in M$ is called PL regular for $F$ if there is a chart around $p$
such that the function $F$ can be used as one of the coordinates on the chart,
i.e., if in those coordinates $F$ takes the form

$F_{\tiny reg}(x_{1},\ldots,x_{n}):=F(p)+x_{n}.$

  * •

A point $p\in M$ is called PL nondegenerate-critical for $F$ if there is a PL
chart around $p$ such that in those coordinates the function $F$ can be
expressed as

$F_{\tiny
crit,k}(x_{1},\ldots,x_{n}):=F(p)-|x_{1}|-\ldots-|x_{k}|+|x_{k-1}|+\ldots+|x_{n}|.$

The number $k$ is then uniquely determined and is called the index of $p$.

  * •

If $p\in M$ is neither PL regular nor PL nondegenerate-critical, it is said to
be _PL degenerate-critical_.

  * •

The function $F$ is called a PL Morse function if all points are either PL
regular or PL nondegenerate-critical.

######  Remark 3.6.

If a point $p\in M$ is PL regular (resp., PL nondegenerate-critical of index
$k$) for $F$, then the function $F$ is locally-equivalent at $p$ to $F_{\tiny
reg}$ (resp., to $F_{\tiny crit,k}$) in the language of [6, Defn. 3.1]. The
interested reader may also wish to consult [6, Sec. 3.2.5], which reviews the
relationship with previous notions due to Brehm-Kühnel, Eells-Kuiper, and
Kosinski.

###  3.2. Flat cells, nontransversal thresholds, and general maps

Recall the following terminology from [4], which can be traced back to
Banchoff [2]:

######  Definition 3.7.

Let $F:|M|\rightarrow\mathbb{R}$ be linear on the cells of a polyhedral
complex, $M$. A cell $C\in M$ satisfying $F(C)=\\{t\\}$ for some
$t\in\mathbb{R}$ will be called a flat cell or a constant cell for $F$.

######  Remark 3.8.

Note that all $0$–cells of $M$ are flat.

It is immediate that any face of a flat cell will also be flat, so the set of
flat cells relative to a map $F:|M|\rightarrow\mathbb{R}$ forms a subcomplex
of $M$, which we will denote $M_{\tiny\mbox{flat}}(F)$.

The following related definition, which appears frequently in the literature,
is also due to Banchoff [2]:

######  Definition 3.9.

A map $F:|M|\rightarrow\mathbb{R}$ that is linear on cells of a polyhedral
complex $M$ is said to be general if

  1. (i)

$F(v)\neq F(w)$ for $0$–cells $v\neq w$ and

  2. (ii)

all flat cells are $0$–dimensional.

######  Remark 3.10.

In [2], Banchoff restricts his attention to polytopal complexes and defines a
map that is linear on cells of such a complex to be general if it satisfies
condition (i) above, which implies condition (ii) in the bounded case. Since
the complexes we consider will have unbounded cells, we add condition (ii).
Note that we could equivalently have replaced condition (ii) with the
condition that every unbounded cell has unbounded image.

######  Remark 3.11.

Note that while all flat cells of a general PL map are $0$-dimensional, not
every PL map whose flat cells all have dimension $0$ is general. Note also
that a general PL map need not be PL Morse. See, e.g., the example in [2, Sec.
2].

######  Lemma 3.12.

Let $M$ be a PL $n$–manifold, and let $F:M\rightarrow\mathbb{R}$ be a finite
PL map. If $F$ has a flat cell $C$ of dimension $n$, then every point in $C$
is PL degenerate-critical, and hence $F$ is not PL Morse.

###### Proof.

By definition, if $p\in M$ is either PL regular or PL non-degenerate critical
for $F$, and $F(p)=a$, then $p$ has a neighborhood $N_{p}$ that is PL
homeomorphic to a neighborhood of the origin in $\mathbb{R}^{n}$, and the
level sets of the induced map are PL homeomorphic. By examining $F_{=0}$ in
each of the two local models, one concludes that the intersection of $F_{=a}$
with $N_{p}$ is therefore locally PL homeomorphic to an imbedded polyhedral
complex of $N_{p}$ of dimension $n-1$.

But if $p$ is contained in a flat cell of dimension $n$, then the intersection
of $F_{=a}$ with every neighborhood of $p$ contains an $n$–dimensional ball, a
contradiction. ∎

Figure 2. Left: A PL non-degenerate critical point of index 1 of a function
$\mathbb{R}^{2}\to\mathbb{R}$. Right: A PL strongly regular point.

###  3.3. Flat cells for ReLU layer maps and proof of Theorem 2

To prove Theorem 2, we briefly investigate how flat cells arise in ReLU neural
network functions.

It will be convenient to note that if $F$ is a ReLU neural network function of
architecture $(n_{0},\ldots,n_{m};1)$,

then every cell $C$ of $\mathcal{C}(F)$ admits a labeling by a sequence of
ternary tuples

$\theta_{C}:=\left(\theta^{(1)},\ldots,\theta^{(m)}\right)\in\\{-1,0,1\\}^{n_{1}+\ldots+n_{m}}$

indicating the sign of the pre-activation output of each neuron.

Explicitly, if $x=x^{(0)}\in\mathbb{R}^{n_{0}}$ is an input vector, and we
denote by

$z^{(\ell)}:=(A^{(\ell)}\circ F^{(\ell-1)}\circ\ldots\circ
F^{(1)})(x)\in\mathbb{R}^{n_{\ell}}$

the pre-activation output of the first $\ell$ layer maps, then the components
of
$\theta^{(\ell)}_{C}=\left(\theta^{(\ell)}_{1},\,\,\ldots\,\,,\theta^{(\ell)}_{n_{\ell}}\right)$
are defined by $\theta^{(\ell)}_{i}=\mbox{sgn}(z_{i}^{(\ell)})$. For generic,
transversal ReLU networks, this assignment agrees with the activation patterns
defined in [9].

It is immediate that if $C$ is a cell for which the components of
$\theta^{(\ell)}_{C}$ are all non-positive for some $\ell$, then $C$ is flat.
The following lemma tells us that the converse holds for cells of generic,
transversal neural networks with a single ReLU layer.

######  Lemma 3.13.

Let $F:\mathbb{R}^{d}\to\mathbb{R}^{n}$ be a generic ReLU neural network layer
map with associated (generic) co-oriented hyperplane arrangement
$\mathcal{A}:=\\{H_{1},...,H_{n}\\}$. Denote by $\mathcal{C}(\mathcal{A})$ the
associated polyhedral decomposition of $\mathbb{R}^{d}$ and let
$C\in\mathcal{C}(\mathcal{A})$ be a $k$-cell, for any $1\leq k\leq d$. If any
coordinate of $F$ is constant on $C$ (i.e. $\pi_{j}\circ F(C)$ is a point),
then $F(C)=\vec{0}$. Furthermore, $C$ is a face of a $d$–cell with ternary
labeling $(-1,\ldots,-1)\in\\{-1,0,1\\}^{n}$.

###### Proof.

First consider the case $1\leq k<d$. By the genericity of $\mathcal{A}$, the
affine hull of $C$ is uniquely determined by some intersection of hyperplanes
from $\mathcal{A}$, that is, $C\subset H_{i_{1}}\cap H_{i_{2}}...\cap
H_{i_{d-k}}$. Suppose, by way of contradiction, that $C$ is sent to a nonzero
constant in some coordinate corresponding to a hyperplane $H$ in
$\mathcal{A}$. This precisely means that $C\in H^{+}$ and, additionally, for
each $x\in C$, the distance $d(x,H)$ is constant and nonzero. Thus the affine
hull of $C$ is contained in the hyperplane parallel to $H$ at a fixed
distance. This implies that $H\cap(H_{i_{1}}...\cap H_{i_{d-k}})=\emptyset$.
However, this is an intersection of $d-k+1\leq d$ hyperplanes in
$\mathcal{A}$, and by genericity cannot be empty. This is a contradiction, and
therefore if $C$ is sent to a constant, it must be sent to $0$ in all
coordinates. Thus $C$ is in the intersection of the closed half spaces
$H_{i}^{-}$ for all hyperplanes $H_{i}$ forming the arrangement $\mathcal{A}$,
and must be a face of the cell with the ternary labeling $(-1,\ldots,-1)$.

Now consider the case $k=d$, and again suppose that $C$ is sent to a nonzero
constant in some coordinate corresponding to a hyperplane $H$ in
$\mathcal{A}$. Since $\mathcal{A}$ is nonempty, $C$ is not all of
$\mathbb{R}^{d}$. Hence $C$ contains a lower dimensional facet, $C^{\prime}$.
Then $F$ sends $C^{\prime}$ to the same nonzero constant in the coordinate
corresponding to $H$. But by the result of the previous case,
$F(C^{\prime})=\vec{0}$. Lastly, if $C$ were contained in $H_{i}^{+}$ for some
$i$, then $F(C)$ would be nonzero in some coordinate, which is a
contradiction. Thus $C$ has the ternary labeling $(-1,\ldots,-1)$.

∎

######  Remark 3.14.

The assumption in Lemma 3.13 that the hyperplane arrangement is generic is
necessary. Here is an example of how the conclusion can fail without this
assumption. Consider the nongeneric layer map
$F:\mathbb{R}^{2}\to\mathbb{R}^{2}$ given by

$(x,y)\mapsto(\textrm{Relu}(x+1),\textrm{Relu}(x)).$

Then $\\{(x,y):x=0\\}$ is a flat $1$-cell in $\mathcal{C}(F)$ whose image
under $F$ is the point $(1,0)$, not $(0,0)$.

######  Remark 3.15.

The conclusion of Lemma 3.13 does not always hold when $F$ is a composition of
multiple generic, transversal layer maps.

For example, define a neural network map $F$ (omitting the final affine-linear
layer) by

$F:\mathbb{R}^{2}\xrightarrow{F_{1}=\sigma\circ
A_{1}}\mathbb{R}^{2}\xrightarrow{F_{2}=\sigma\circ A_{2}}\mathbb{R}^{1}$

where the affine-linear maps $A_{i}$ are defined by $A_{1}(x,y)=(x,y)$ and
$A_{2}(u,v)=u+1$. Then $\mathcal{C}(F)=\mathcal{C}^{std}(\mathbb{R}^{2})$. Let
$C$ be the $1$-cell $\\{(0,y)\in\mathbb{R}^{2}\mid y\geq 0\\}$ in
$\mathcal{C}(F)$. Then $C$ is flat since $F(C)=\\{1\\}$, but $C$ is not a face
of a cell whose ternary labeling is $(-1,\ldots,-1)$ for either layer. (Note
that $\theta^{(2)}=1$ for all points in the domain.)

Examples like this can arise when there exists some $i$ such that the image of
a positive-dimensional cell, $C$, of $\mathcal{C}(F)$ under the first $i-1$
layer maps, $F^{(i-1)}\circ\ldots\circ F^{(1)}$,

  1. (i)

is in the orthogonal complement of the span of the weight vectors of
$F^{(i)}$, and

  2. (ii)

at least one neuron of $F^{(i)}$ is switched on in the interior of $C$.

The following was essentially proved in [6]:

######  Lemma 3.16.

Let $F:\mathbb{R}^{n}\rightarrow\mathbb{R}$ be a ReLU neural network function
and $\mathcal{C}(F)$ its canonical polyhedral complex. Any point $p$ in the
interior of a non-flat cell $C$ of dimension $k\geq 1$ is PL regular.

###### Proof.

Recall that $F$ is affine-linear on the cells of $\mathcal{C}(F)$ by
construction. Let $p$ be a point in the interior of a cell $C$ of dimension
$k\geq 1$. Any finite simplicial subdivision of the intersection complex,
$\mathcal{C}_{p}$, of a star neighborhood of $p$ with $\mathcal{C}(F)$ will be
a combinatorial $n$–manifold with boundary, since it is imbedded in
$\mathbb{R}^{n}$ (cf. the discussion following [6, Defn. 1.33]). If $C$ is
non-flat, it then follows from [6, Lem. 3.22] that $p$ is PL regular. ∎

We are now ready to prove Theorem 2.

###### Proof of Theorem 2.

Let $F:\mathbb{R}^{n}\rightarrow\mathbb{R}$ be a ReLU neural network map with
hidden layers of dimensions $(n_{1},\ldots,n_{\ell})$.

We focus first on proving that when $\ell=1$ the probability that $F$ is PL
Morse is

$\frac{\sum_{k=n+1}^{n_{1}}{n_{1}\choose k}}{2^{n_{1}}}.$

Note that since the output layer map
$G:\mathbb{R}^{n_{1}}\rightarrow\mathbb{R}$ is affine-linear, in the $\ell=1$
case we have $\mathcal{C}(F)=\mathcal{C}(F^{(1)})$ where
$F^{(1)}:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n_{1}}$ is the first layer map.
In other words, $\mathcal{C}(F)=\mathcal{C}(\mathcal{A})$, where $\mathcal{A}$
is the hyperplane arrangement associated to $F^{(1)}$.

We now claim that the probability that $F$ is PL Morse when $\ell=1$ is
precisely the probability that no $n$–cell of $\mathcal{C}(F)$ has ternary
labeling $(-1,\ldots,-1)$.

To prove this claim, we first note that since there are finitely many cells of
$\mathcal{C}(F)$, and the final layer map $G$ is affine-linear, the
probability that $\mathcal{C}(F)$ has a flat cell of positive dimension is
precisely the probability that $\mathcal{C}(F^{(1)})$ does. Moreover, Lemma
3.13 tells us that $\mathcal{C}(F^{(1)})$ has a flat cell of positive
dimension if and only if it has a flat cell of dimension $n$ with ternary
labeling $(-1,\ldots,-1)$.

If there is an $n$–cell of $\mathcal{C}(F)$ with ternary labeling
$(-1,\ldots,-1)$, Lemma 3.12 tells us that $F$ is not PL Morse. If there is no
$n$–cell with ternary labeling $(-1,\ldots,-1)$, then the only flat cells of
$F$ are $0$–cells. Lemma 3.16 above tells us that any point in the interior of
a non-flat cell is PL regular, and Proposition 6.6 tells us that every
$0$–cell of $\mathcal{C}(F)$ is PL regular or PL nondegenerate-critical, since
there are no flat cells of positive dimension. It follows that $F$ is PL
Morse, completing the proof of the claim.

To compute the probability that an $n$–cell of
$\mathcal{C}(F)=\mathcal{C}(\mathcal{A})$ has ternary labeling
$(-1,\ldots,-1)$, recall that Zaslavsky’s theorem (cf. [13, Prop. 2.4]) tells
us that the total number of $n$–cells of $\mathcal{C}(\mathcal{A})$ when
$\mathcal{A}$ is a generic arrangement of $n_{1}$ hyperplanes in
$\mathbb{R}^{n}$ is $r(\mathcal{A})=\sum_{k=0}^{n}{n_{1}\choose k}$.
Associated to each region is precisely one co-orientation of the hyperplane
arrangement causing the region to be labeled with $\vec{0}$. So, of the
$2^{n_{1}}$ possible co-orientations on each generic arrangement, precisely
$r(\mathcal{A})=\sum_{k=0}^{n}{n_{1}\choose k}$ yield an $n$–cell with ternary
labeling $(-1,\ldots,-1)$. But $\mathcal{A}$ is generic for all but a measure
$0$ set of parameters. It follows that the probability that $F$ is PL Morse is

$1-\frac{\sum_{k=0}^{n}{n_{1}\choose
k}}{2^{n_{1}}}=\frac{\sum_{k=n+1}^{n_{1}}{n_{1}\choose k}}{2^{n_{1}}},$

as desired.

We will now prove that the above expression gives an upper bound on the
probability that $F:\mathbb{R}^{n}\rightarrow\mathbb{R}$ is PL Morse in the
case $\ell>1$. By the discussion above and before the statement of Lemma 3.13,
the probability that $F$ has a flat $n$–cell is bounded below by the
probability that $\mathcal{C}(F^{(1)})$ has a region with ternary label
$(-1,\ldots,-1)$. The latter probability is $\frac{\sum_{k=0}^{n}{n_{1}\choose
k}}{2^{n_{1}}}$, as above, so

$\frac{\sum_{k=n+1}^{n_{1}}{n_{1}\choose k}}{2^{n_{1}}}$

is an upper bound on the probability that $F$ is PL Morse. ∎

######  Corollary 3.17.

Let $F:\mathbb{R}^{n}\rightarrow\mathbb{R}$ be a ReLU neural network function
with hidden layers of dimensions $(n_{1},\ldots,n_{\ell})$.

  1. (i)

If $n_{1}\leq n$, the probability that $F$ is PL Morse is $0$.

  2. (ii)

If $\ell=1$ and $n_{1}\geq 2n+1$, the probability that $F$ is PL Morse exceeds
$\frac{1}{2}$.

  3. (iii)

If $\ell=1$, the probability that $F$ is PL Morse approaches $1$ as
$n_{1}\rightarrow\infty$.

###### Proof.

Item (i) is immediate. To see (ii), recall that
$\sum_{k=0}^{n_{1}}{n_{1}\choose k}=2^{n_{1}}$ and ${n_{1}\choose
k}={n_{1}\choose n_{1}-k}$. To see (iii), note that for fixed $n$,
$\sum_{k=0}^{n}{n_{1}\choose k}$ is a degree $n$ polynomial in $n_{1}$, while
$2^{n_{1}}$ is exponential in $n_{1}$, so

$\lim_{n_{1}\rightarrow\infty}\frac{\sum_{k=0}^{n}{n_{1}\choose
k}}{2^{n_{1}}}\rightarrow 0.$

∎

######  Definition 3.18.

Let $F:\mathbb{R}^{n}\rightarrow\mathbb{R}$ be linear on cells of a polyhedral
decomposition $\mathcal{C}$ of $\mathbb{R}^{n}$. We say that $F$ is almost PL
Morse if there exists some cell $C\in\mathcal{C}$ such that if $x$ is neither
PL regular nor PL nondegenerate critical, then $x\in|C|$.

The following is immediate from the proof of Theorem 2.

######  Corollary 3.19.

Let $F:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n_{1}}\rightarrow\mathbb{R}$ be a
depth $2$ ReLU neural network function. $F$ is almost PL Morse with
probability $1$.

We close the section with a first estimate of the prevalence of flat cells, in
the form of a lower bound.

######  Lemma 3.20.

Fix $x$ in $\mathbb{R}^{n_{0}}$, and a neural network architecture
$(n_{0},n_{1},...n_{m})$. Select a network $F$ with this architecture randomly
such that its parameters are i.i.d. following a distribution which is
symmetric about the origin. Letting $C$ be the minimal-dimensional cell in
$\mathcal{C}(F)$ containing $x$, then the probability that $C$ is a flat cell
for $F$ is at least $2^{-n_{m}}$.

###### Proof.

We may assume that $C$ is an $n_{0}$-cell, as the probability that $x$ is in
the $(n_{0}-1)$-skeleton of $\mathcal{C}(F)$ is zero. We also assume that the
network is transversal so that the bent hyperplane arrangement forms the
$(n_{0}-1)$ skeleton of $\mathcal{C}(F)$.

Recall $\mathcal{A}_{m}$, the hyperplane arrangement associated with
$\mathbb{F}_{m}$, and its associated co-oriented hyperplane arrangement. Now,
$C$ is given by the intersection of two cells in $\mathbb{R}^{n_{0}}$: A
unique cell $R^{\prime}=(F_{m}^{-1}\circ...\circ F_{1})^{-1}(R)$, with $R$ a
top-dimensional region of the polyhedral decomposition of
$\mathbb{R}^{n_{m-1}}$ given by $\mathcal{A}_{m}$, together with a unique cell
of $\mathcal{C}(F_{m-1}\circ...\circ F_{1})$.

Because the parameters for $F$ are selected i.i.d. from a distribution which
is symmetric about the origin, the following construction of the network
$F^{\prime}$ has the same distribution as $F$: Selecting a network from the
same distribution as $F$, then randomly and independently multiplying each row
of $A_{m}$ by -1 or 1 with equal probability, effectively selecting $F$ and
then uniformly selecting a co-orientation of the hyperplane arrangement
$\mathcal{A}_{m}$ to produce $F^{\prime}$. We note that the polyhedral complex
$\mathcal{C}(F)$ is equivariant under changing co-orientations of
$\mathcal{A}_{m}$: all such co-orientations lead to the same final polyhedral
complex $\mathcal{C}(F)$ and the presence of the same cell $C$. Recall that
there is a unique co-orientation of $\mathcal{A}_{m}^{\prime}$ making $F_{m}$
constant on $R$. There are $2^{n_{m}}$ such co-orientations, so the
probability that $F_{m}^{\prime}$ is constant on $R$, given initial network
$F$, is $2^{-n_{m}}$. If $F_{m}^{\prime}$ is constant on $R$, then
$F^{\prime}$ is constant on $C$, so the probability $F^{\prime}$ is constant
on $C$ given $F$ is at least $2^{-n_{m}}$. Since this is true for almost all
$F$, the probability any $F^{\prime}$ selected in this way is constant on the
cell containing $x$ is at least $2^{-n_{m}}$. As $F^{\prime}$ follows the same
distribution as $F$, this is true for any network $F$ as well. ∎

##  4\. Global and Local H-complexity

The purpose of this section is to define and study algebro-topological
invariants of the level sets and sublevel sets of ReLU neural network
functions. We extract local and global notions of topological complexity of
ReLU neural network functions by studying how the homology of its level sets
and sublevel sets change as we vary the final layer threshold.

We recall the following definitions from algebraic topology (cf. [10]) and
piecewise linear (PL) topology (cf. [11]):

######  Definition 4.1.

Let $X,Y$ be topological spaces, and let $I:=[0,1]$ denote the closed unit
interval endowed with the standard topology. A homotopy between continuous
maps $f,g:X\rightarrow Y$ is a continuous map $H:X\times[0,1]\rightarrow Y$
satisfying $H|_{X\times\\{0\\}}=f$ and $H|_{X\times\\{1\\}}=g$.

If there exists a homotopy between $f,g:X\to Y$ we say that $f$ and $g$ are
homotopic and write $f\simeq g$.

######  Definition 4.2.

Let $X,Y$ be topological spaces. $X$ and $Y$ are said to be homotopy
equivalent if there exist continuous maps $f:X\rightarrow Y$ and
$g:Y\rightarrow X$ such that $f\circ g\simeq\mbox{Id}$ and $g\circ
f\simeq\mbox{Id}$. In this case, $f$ (resp., $g$) induces a homotopy
equivalence between $X$ and $Y$.

_Strong deformation retraction_ is a special case of homotopy equivalence that
will be particularly important in the present work. A strong deformation
retraction of a space $X$ onto a subspace $A\subset X$ is a continuous map
$F:X\times[0,1]\to X$ such that $F(x,0)=x$, $F(x,1)\in A$ and $F(a,t)=a$ for
all $x\in X,a\in A,t\in[0,1]$.

Homotopy equivalence is an equivalence relation on topological spaces that is
weaker than homeomorphism. Many algebro-topological invariants (in particular,
the ones studied here) are homotopy equivalence class invariants.

Since we will also define invariants of pairs $(X,A)$ of topological spaces
where $A\subseteq X$ is a subspace (i.e., the inclusion map is continuous), we
will need a few more definitions.

######  Definition 4.3.

Let $(X,A)$ and $(Y,B)$ be pairs of topological spaces. A map on pairs
$f:(X,A)\rightarrow(Y,B)$ is a continuous map $X\rightarrow Y$ whose
restriction to $A$ is a continuous map $A\rightarrow B$.

######  Definition 4.4.

Let $f,g:(X,A)\rightarrow(Y,B)$ be maps of pairs. $f$ and $g$ are said to be
homotopic through maps of pairs $(X,A)\rightarrow(Y,B)$ if there exists a
homotopy $H:X\times I\rightarrow Y$ for which $H_{t}:X\times\\{t\\}\rightarrow
Y$ is a map on pairs $(X,A)\rightarrow(Y,B)$ for all $t\in[0,1]$.

Recall that if $(X,A)$ is a pair of topological spaces, then $H_{n}(X,A)$
refers to the degree $n$ relative singular homology of the pair $(X,A)$ with
$\mathbb{Z}$ coefficients, cf. [10, Chp. 2]. If $X$ is a simplicial complex
and $A$ is a subcomplex, then the relative singular homology agrees with the
relative simplicial homology of the pair $(X,A)$, cf. [10, Thm. 2.27].

Note that if $f:(X,A)\rightarrow(Y,B)$ is a map of pairs then $f$ induces a
homomorphism $f_{*}:H_{n}(X,A)\rightarrow H_{n}(Y,B)$ for all $n$. We will
make use of the following standard results, cf. [10, Prop. 2.19, Ex. 2.27].

######  Lemma 4.5.

If two maps $f,g$ are homotopic through maps of pairs $(X,A)\rightarrow(Y,B)$,
then $f_{*}=g_{*}:H_{n}(X,A)\rightarrow H_{n}(Y,B)$ for all $n$.

######  Lemma 4.6.

If $f:(X,A)\rightarrow(Y,B)$ is a map on pairs for which $f:X\rightarrow Y$
and its restriction $f|_{A}:A\rightarrow B$ induce homotopy equivalences, then
$f_{*}:H_{n}(X,A)\rightarrow H_{n}(Y,B)$ is an isomorphism for all $n$.

The following definition is adapted from [7].

######  Definition 4.7.

Let $F:|M|\rightarrow\mathbb{R}$ be a map that is linear on cells of a finite
polyhedral complex $M$, let $a\in\mathbb{R}$ be a nontransversal threshold,
and $K$ a connected component of the intersection of its corresponding level
set, $F_{=a}$, with the subcomplex, $M_{\tiny\mbox{flat}}(F)$, of flat cells.
$K$ is said to be homologically critical (or H-critical for short) if
$H_{*}(F_{\leq a}\,\,,F_{\leq a}\setminus K)\neq 0$. $K$ is said to be
homologically regular (resp., H-regular) otherwise.

######  Remark 4.8.

In [7], the authors define the notion of H-criticality and H-regularity only
for flat $0$–cells and not for (connected unions of) flat higher-dimensional
cells. Since the functions of interest to us have a non-zero probability of
having higher-dimensional flat cells, we extend the definition.

######  Definition 4.9.

Let $F:|M|\rightarrow\mathbb{R}$ be a map that is linear on cells of a finite
polyhedral complex $M$, let $a\in\mathbb{R}$ be a nontransversal threshold,
and let $K$ be a connected component of $F_{=a}\cap M_{\tiny\mbox{flat}}(F)$
as in Definition 4.7 above.

  1. (i)

The $i$th local $H$–complexity of $K$ is defined to be the rank of

$H_{i}(F_{\leq a}\,\,,F_{\leq a}\setminus K).$

  2. (ii)

The total local $H$–complexity of $K$ is defined to be the sum of the $i$th
local $H$–complexities of $K$ over all $i$.

  3. (iii)

The global $H$–complexity of $F$ is the sum, over all nontransversal
thresholds $a\in\mathbb{R}$ and all connected components $K$, of

$F_{=a}\cap M_{\tiny\mbox{flat}}(F),$

of the total local $H$–complexity of $K$.

######  Remark 4.10.

Note that the universal coefficient theorem tells us that if the total local
$H$–complexity $H_{*}(F_{\leq a}\,\,,F_{\leq a}\setminus K)=0$ then
$H_{*}(F_{\leq a}\,\,,F_{\leq a}\setminus K;\mathbb{F})=0$ for any field
$\mathbb{F}$, but this statement may not hold for the $i$th local
$H$–complexity for fixed $i$.

######  Proposition 4.11.

Let $M$ be a PL $n$–manifold and $F:M\rightarrow\mathbb{R}$ be a finite PL
map. If $v$ is either a PL regular or PL nondegenerate-critical $0$–cell, then
$v$ is a connected component of $F_{=a}\cap M_{\tiny\mbox{flat}}(F)$.
Moreover:

  1. (i)

If $v$ is PL regular, then the $i$th local $H$–complexity of $v$ is $0$ for
all $i$.

  2. (ii)

If $v$ is PL nondegenerate-critical of index $k$ with $F(v)=a$, then the
$i$–th local H-complexity of $v$ is $\left\\{\begin{array}[]{cl}1&\mbox{ if
$i=k$ and}\\\ 0&\mbox{ otherwise.}\end{array}\right.$

###### Proof.

It follows immediately from the definitions of regular and non-degenerate
critical point that $v$ is isolated, so $v$ is a connected component of
$F_{=a}\cap M_{\tiny\mbox{flat}}(F)$. Consider the intersection complex of $M$
with any closed star neighborhood of $v$ containing no other flat cells. In
[6, Thm. 5.2], Grunert proves that if

  * •

$M$ is a polytopal complex with $F:M\rightarrow\mathbb{R}$ linear on cells,

  * •

$v$ is a non-degenerate critical point of index $k$ with $F(v)=a$, and

  * •

$v$ is the only $0$–cell in $F^{-1}[a-\epsilon,a+\epsilon]$ for some
$\epsilon>0$,

then $F_{a+\epsilon}$ is homotopy-equivalent to $F_{a-\epsilon}$ with a
$k$–handle attached. By applying the above result to the restriction of $F$ to
the star complex of $v$ in the intersection complex constructed above, it
follows by excision (cf. the discussion following [7, Defn. 3.3]) that

$H_{i}(F_{\leq a}\,\,,F_{\leq
a}\setminus\\{v\\})=\left\\{\begin{array}[]{cl}\mathbb{Z}&\mbox{ if $i=k$}\\\
0&\mbox{ otherwise. }\end{array}\right.$

∎

##  5\. Sublevel sets of finite PL maps are homotopy equivalent within
transversal intervals

The goal of this section is to develop the necessary technical machinery to
prove the following two keystone results of this paper:

######  Theorem 3.

Let $\mathcal{C}$ be a polyhedral complex in $\mathbb{R}^{n}$, let
$F:|\mathcal{C}|\to\mathbb{R}$ be linear on cells of $\mathcal{C}$, and let
$[a,b]$ be an interval of transversal thresholds for $F$ on $\mathcal{C}$.
Then there exists a polytopal complex $\mathcal{D}$ with
$|\mathcal{D}|\subset|\mathcal{C}|$ and a strong deformation retraction
$\Phi:|\mathcal{C}|\to|\mathcal{D}|$ (which induces a cellular map
$\mathcal{C}\to\mathcal{D}$) such that $\Phi$ is $F$-level preserving on
$|\mathcal{C}_{F\in[a,b]}|$ and for every $c\in[a,b]$,

(3) $\Phi(|\mathcal{C}_{F\leq c}|)=|\mathcal{D}_{F\leq
c}|,\quad\Phi(|\mathcal{C}_{F\geq c}|)=|\mathcal{D}_{F\geq c}|.$

Furthermore, there is an $F$-level preserving PL isotopy

$\phi:|\mathcal{D}|_{F=c}\times[a,b]\to|\mathcal{D}_{F\in[a,b]}|.$

######  Theorem 4.

Let $\mathcal{C}$ be a polyhedral complex in $\mathbb{R}^{n}$, let
$F:|\mathcal{C}|\to\mathbb{R}$ be linear on cells of $\mathcal{C}$, and let
$[a,b]$ be an interval of transversal thresholds for $F$ on $\mathcal{C}$.
Then for any threshold $c\in[a,b]$, $|\mathcal{C}_{F\leq c}|$ is homotopy
equivalent to $|\mathcal{C}_{F\leq a}|$; also $|\mathcal{C}_{F\geq c}|$ is
homotopy equivalent to $|\mathcal{C}_{F\geq b}|$.

While we believe the above results are useful more generally, our main
motivation for proving them here is to extend existing results in the
literature adapting Morse-theoretic ideas to the PL setting so that they apply
to some noncompact settings. Indeed, Theorem 3 allows us to extend [6, Lem.
4.13], which applies only to polytopal complexes, to all polyhedral complexes
imbedded in $\mathbb{R}^{n}$ equipped with the standard PL structure.

Note also that Theorem 4 is sufficient to guarantee that for a map that is
affine-linear on cells of a finite polyhedral complex in $\mathbb{R}^{n}$, we
need only perform computations at finitely many thresholds $a\in\mathbb{R}$ in
order to compute the full set of algebro-topological invariants described in
Sections 4 and 7. In addition, we note that having compact models for the
spaces of interest guarantees the existence of finite time algorithms to
compute the algebro-topologial invariants we study, since polytopal complexes
admit finite simplicial subdivisions, and simplicial homology can be computed
algorithmically.

This section is organized as follows. In Subsection 5.1, we establish
terminology and notation. In particular, we recall the classical decomposition
of polyhedral sets as a Minkowski sum (Theorem 6). In Subsection 5.2 we use
this decomposition in the pointed case (see Definition 5.1) to construct a
deformation retraction to a canonical polytopal complex. In Subsection 5.3 we
prove that for connected polyhedral complexes imbedded in $\mathbb{R}^{n}$,
all cells are pointed or all cells are unpointed. This allows us to extend the
deformation retraction to the unpointed setting. In Subsection 5.4, we then
show that, with respect to any map that is affine-linear on cells, these
deformation retractions are well-behaved enough to guarantee that sublevel
sets are homotopy equivalent within transversal intervals.

###  5.1. The canonical polytopal complex of a pointed polyhedral complex

We begin by recalling some definitions from [12] pertaining to the structure
of polyhedral sets:

######  Definition 5.1 ([12]).

  1. (i)

A _cone_ in $\mathbb{R}^{n}$ is a set $C$ such that if $x,y\in C$ and
$\lambda,\mu\geq 0$, then $\lambda x+\mu y\in C$.

  2. (ii)

Let $P$ and $Q$ be polyhedral sets embedded in $\mathbb{R}^{n}$. The
_Minkowski sum_ of $P$ and $Q$ is

$P+Q:=\\{p+q\mid p\in P,q\in P\\}.$

Let $P\subset\mathbb{R}^{n}$ be a polyhedral set.

  1. (iii)

The _characteristic cone_ (or _recession cone_) of $P$ is the set

$\textrm{char.cone}(P):=\\{y\mid x+y\in P\textrm{ for all }x\in P\\}$

  2. (iv)

The _lineality space_ of $P$ is the set

$\textrm{lin.space}(P):=\textrm{char.cone}(P)\cap-\textrm{char.cone}(P).$

  3. (v)

$P$ is said to be _pointed_ if $\textrm{lin.space}(P)=\\{0\\}$.

  4. (vi)

A _minimal face_ of $P$ is a face not containing any other face.

  5. (vii)

A _minimal proper_ face of a cone $C$ is a face of dimension

$\textrm{dim}(\textrm{lin.space}(C))+1.$

Recall also that the _convex hull_ (resp. _linear hull_ and _affine hull_) of
a set $S\subset\mathbb{R}^{n}$ is the intersection of all convex subsets
(resp. linear and affine-linear subspaces) of $\mathbb{R}^{n}$ that contain
$S$.

The following well-known characterization of pointed cells is immediate:

######  Lemma 5.2 ([12]).

Let $P\subset\mathbb{R}^{n}$ be a polyhedral set. $P$ is pointed if and only
if it has a face of dimension $0$.

It will be important to us that a pointed polyhedral set has a canonical
representation as the Minkowski sum of its compact part and its characteristic
cone:

######  Theorem 6.

[12, Theorem 8.5] Let $P\subset\mathbb{R}^{n}$ be a polyhedral set. For each
minimal face $F$ of $P$, fix a point $x_{F}\in F$. For each minimal proper
face $F$ of $\textrm{char.cone}(P)$, fix a point $y_{F}\in
F\setminus\textrm{lin.space}(P)$. Fix a set $\\{z_{1},\ldots,z_{k}\\}$ that
generates the linear space $\textrm{lin.space}(P)$. Then

$P=\textrm{conv.hull}(\\{x_{F}\mid F\textrm{ a minimal face of }P\\})+\\\
\textrm{cone}(\\{y_{F}\mid F\textrm{ a minimal proper face of
}\textrm{char.cone}(P)\\})+\\\ \textrm{lin.hull}(\\{z_{1},\ldots,z_{k}\\})$

Equipped with the definition of a pointed polyhedral set, we can now define
and establish notation for its compact part:

######  Definition 5.3 (Compact part of a pointed polyhedral set).

For any polyhedral set $C$ embedded in $\mathbb{R}^{n}$, we denote by $K_{C}$
the convex hull of the set of $0$-cells of $C$, and denote by
$\widetilde{K}_{C}$ the polytopal complex consisting of all the faces of
$K_{C}$ (including the set $K_{C}$ itself).

######  Definition 5.4 (Compact part of pointed complexes in
$\mathbb{R}^{n}$).

Let $\mathcal{C}$ be a polyhedral complex embedded in $\mathbb{R}^{n}$ in
which all cells are pointed. Define the _canonical polytopal complex
associated to_ $\mathcal{C}$ to be the following family of sets:

(4)
$\textrm{com.part}(\mathcal{C}):=\bigcup_{C\in\mathcal{C}}\widetilde{K}_{C}.$

######  Remark 5.5.

We interpret the union in (4) as not allowing redundancy, i.e. each set occurs
only once in $\textrm{com.part}(\mathcal{C})$, even if it is represented in
the union more than once.

For a polyhedral complex $\mathcal{C}$ whose cells are all pointed, we will
also refer to $\textrm{com.part}(\mathcal{C})$ as the canonical polytopal
complex associated to $\mathcal{C}$ (c.f. Definition 5.36). Calling
$\textrm{com.part}(\mathcal{C})$ a “polytopal complex” is justified by the
following result:

######  Lemma 5.6.

Let $\mathcal{C}$ be a polyhedral complex embedded in $\mathbb{R}^{n}$ in
which all cells are pointed. Then the compact part of $\mathcal{C}$,
$\textrm{com.part}(\mathcal{C})$, is a polytypal complex.

###### Proof.

A polyhedral complex, by definition, has only finitely many $0$-cells, so for
each cell $C\in\mathcal{C}$, $K_{C}$ is a polytope. Furthermore, a face of a
polytope is a polytope. Hence, $\textrm{com.part}(\mathcal{C})$ is a finite
collection of polytopes. We must verify that

  1. (i)

every face of each polytope in $\textrm{com.part}(\mathcal{C})$ is in
$\textrm{com.part}(\mathcal{C})$, and

  2. (ii)

the intersection of any two polytopes in $\textrm{com.part}(\mathcal{C})$ is a
face of both.

Property (i) holds because $\textrm{com.part}(\mathcal{C})$ consists of a
union of polytopal complexes, and each such complex must satisfy (i).

To see property (ii), suppose that $A$ and $B$ are any two polytopes in
$\textrm{com.part}(\mathcal{C})$. We wish to show that $A\cap B$ is
additionally a member of $\textrm{com.part}(\mathcal{C})$, and is a face of
both $A$ and $B$. Let $C_{1}$ and $C_{2}$ be minimal cells in $\mathcal{C}$
such that $A\in\widetilde{K}_{C_{1}}$ and $B\in\widetilde{K}_{C_{2}}$. We
claim that $A\cap B$ is a face of $K_{C_{1}\cap C_{2}}$, and therefore a
member of $\textrm{com.part}(\mathcal{C})$. Furthermore, $A\cap B$ is a face
of both $A$ and $B$.

First, we may assume $A\cap B$ is nonempty, since otherwise (ii) holds
vacuously. Then, since any two cells of $\mathcal{C}$ are either disjoint or
intersect in a common face, we know $C_{1}\cap C_{2}$ is a polyhedral set in
$\mathcal{C}$, and a face of both $C_{1}$ and of $C_{2}$. As a result, the
$0$-cells of $C_{1}\cap C_{2}$ are precisely those $0$–cells contained in both
$C_{1}$ and $C_{2}$. Two compact polytopes are equal as sets if and only if
they have the same vertices, as taking convex hulls preserves subsets. This
implies $K_{C_{1}\cap C_{2}}=K_{C_{1}}\cap K_{C_{2}}$.

Furthermore, $K_{C_{1}\cap C_{2}}$ is a face of $K_{C_{1}}$. We see this as
follows. Since $C_{1}\cap C_{2}$ is a face of $C_{1}$, there is a supporting
hyperplane $H$ of $C_{1}$ such that $C_{1}\cap C_{2}=C_{1}\cap H$. Consider
$K_{C_{1}}\cap H$. First, $H$ is a supporting hyperplane of $K_{C_{1}}$ since
$H$ does not cut $C_{1}$, so it cannot cut $K_{C_{1}}\subset C_{1}$. Since
$K_{C_{1}\cap C_{2}}\subset(C_{1}\cap H)$ is nonempty, $K_{C_{1}}\cap H$ is
nonempty, and must be a face of $K_{C_{1}}$. We claim $K_{C_{1}}\cap
H=K_{C_{1}\cap C_{2}}$. Now, since $K_{C_{1}}\cap H$ is a face of $K_{C_{1}}$,
the vertices of $K_{C_{1}}\cap H$ are precisely the vertices of $K_{C_{1}}$
contained in $H$, which are precisely the vertices of $C_{1}$ contained in
$H$. But the vertices of $C_{1}$ contained in $H$ are the vertices of
$C_{1}\cap H$, since $C_{1}\cap H$ is a face of $C_{1}$. Since $C_{1}\cap
H=C_{1}\cap C_{2}$, the vertex set of of $C_{1}\cap H$ is precisely the same
as the vertex set of $C_{1}\cap C_{2}$, which is the vertex set of
$K_{C_{1}\cap C_{2}}$. Thus $K_{C_{1}}\cap H=K_{C_{1}\cap C_{2}}$ since their
vertex sets are equal, and $K_{C_{1}\cap C_{2}}$ is a face of $K_{C_{1}}$. By
symmetry, $K_{C_{1}\cap C_{2}}$ is also a face of $K_{C_{2}}$.

Now, to see that $A\cap B$ is a face of $K_{C_{1}\cap C_{2}}$, we note that
$A\cap K_{C_{1}\cap C_{2}}$ must be a face of $K_{C_{1}\cap C_{2}}$ since both
$A$ and $K_{C_{1}\cap C_{2}}$ are faces of $K_{C_{1}}$. Likewise $B\cap
K_{C_{1}\cap C_{2}}$ must be a face of $K_{C_{1}\cap C_{2}}$. Since
$\tilde{K}_{C_{1}\cap C_{2}}$ is a polytopal complex, their intersection,
$A\cap B\cap K_{C_{1}\cap C_{2}}$ must be a face of $K_{C_{1}\cap C_{2}}$ as
well. But $A\cap B\subset K_{C_{1}}\cap K_{C_{2}}$, so $A\cap B\cap
K_{C_{1}\cap C_{2}}=A\cap B$, and $A\cap B$ must be a face of $K_{C_{1}\cap
C_{2}}.$

This establishes that $A\cap B$ is a member of
$\textrm{com.part}(\mathcal{C})$.

Lastly, we show that $A\cap B$ is a face of $A$. However this is immediate. We
note that $A$ is a face of $K_{C_{1}}$, $K_{C_{1}\cap C_{2}}$ is a face of
$K_{C_{1}}$, and $A\cap B$ is a face of $K_{C_{1}\cap C_{2}}$, and thus a face
of $K_{C_{1}}$. Since $\tilde{K}_{C_{1}}$ is a polytopal complex, two faces of
$K_{C_{1}}$ intersect in a common face if the intersection is nonempty,
telling us that $A\cap(A\cap B)$ is a face of $A$. By symmetry, $B\cap(A\cap
B)$ is a face of $B$. ∎

######  Remark 5.7.

We must extend the argument to faces of $K_{C}$ because if a cell $C$ is
unbounded,$\tilde{K}_{C}$ may have a face which cannot be expressed as
$K_{C^{\prime}}$ for any cell $C^{\prime}$ in $\mathcal{C}$.

###  5.2. Deformation retraction of a pointed polyhedral complex of
$\mathbb{R}^{n}$ to its canonical polytopal complex

The purpose of this subsection is to prove:

######  Proposition 5.8.

Let $\mathcal{C}$ be a polyhedral complex in $\mathbb{R}^{n}$ in which all
cells are pointed. Then there is a strong deformation retraction from
$|\mathcal{C}|$ to $|\textrm{com.part}|(\mathcal{C})|$ that induces a
surjective cellular map from $\mathcal{C}$ to $\textrm{com.part}(\mathcal{C})$
respecting the face poset partial order.

Figure 3. An unbounded, pointed polyhedral set expressed as the Minkowski sum
of its characteristic cone and the convex hull of its vertices.

####  5.2.1. The base map

For a pointed polyhedral set $P$, we first define a function $\delta_{P}$
which measures the distance _along directions in $\textrm{char.cone}(P)$_
between a point in $P$ and $K_{P}$.

######  Lemma 5.9.

Let $P\subset\mathbb{R}^{n}$ be a pointed polyhedral set. Define the function
$\delta_{P}:P\to\mathbb{R}^{\geq 0}$ by

$\delta_{P}(p):=\inf\left\\{t\in\mathbb{R}^{\geq 0}\mid p=x+ty,x\in
K_{P},y\in\textrm{char.cone}(P),|y|=1\right\\}.$

Then for each point $p\in P$, the infimum in the definition of $\delta_{P}(p)$
is attained by a unique point in $K$ (i.e. there exists a unique choice of
$x\in K$ such that $p=x+\delta_{P}(p)y$ for some $y\in\textrm{char.cone}(P)$
with $|y|=1$).

###### Proof.

We first show that the infimum is attained for every $p\in P$. By Theorem 6,
the set of points $x\in K_{P}$ such that $p=x+ty$ for some $t\geq 0$ and
$y\in\textrm{char.cone}(P)$ is nonempty. Hence there exist sequences
$\\{x_{n}\\}_{n\in\mathbb{N}}\subset K_{P}$,
$\\{y_{n}\\}_{n\in\mathbb{N}}\subset\textrm{char.cone}(P)$ with $|y_{n}|=1$
for all $n$, and $\\{t_{n}\\}_{n\in\mathbb{N}}\subset\mathbb{R}^{\geq 0}$ with
$\lim_{n\to\infty}t_{n}=\delta_{P}(p)$ such that $p=x_{n}+t_{n}y_{n}.$

Since $K_{P}$ is compact, we may assume without loss of generality that the
sequence $x_{n}$ converges to a point $x_{\infty}\in K_{P}$. It follows that
the sequence of vectors $t_{n}y_{n}=p-x_{n}$ also converges. Since $|y_{n}|=1$
for all $n$, both the sequences $\\{t_{n}\\}$ and $\\{y_{n}\\}$ must converge;
denote their limits by $t_{\infty}$ and $y_{\infty}$. Notice $|y_{\infty}|=1$
and $t_{\infty}=\delta_{P}(p)$. Since $y_{n}\in\textrm{char.cone}(P)$ for all
$n$ and $\textrm{char.cone}(P)$ is closed (for any polyhedral set $P$,
$\textrm{char.cone}(P)$ is the intersection of finitely many closed half
spaces), $y_{\infty}$ is also in $\textrm{char.cone}(P)$. Thus
$p=x_{\infty}+t_{\infty}y_{\infty}$, as desired.

Now, to show uniqueness, suppose there are two distinct points $x_{1}$ and
$x_{2}$ in $K_{P}$ with corresponding unit-length vectors $y_{1}$ and $y_{2}$
in $\textrm{char.cone}(P)$ such that

$p=x_{1}+\delta_{P}(p)y_{1}=x_{2}+\delta_{P}(p)y_{2}.$

Since $K_{P}$ is convex, the point

$\alpha\coloneqq\frac{x_{1}+x_{2}}{2}$

is in $K$. But then the line segment connecting $p$ and $\alpha$ is the median
of the isosceles triangle with vertices $p$, $x_{1}$ and $x_{2}$, and hence

$|p-\alpha|<\delta_{P}(p).$

Furthermore,

$\alpha+\frac{\delta_{P}(p)y_{1}+\delta_{P}(p)y_{2}}{2}=p$

and

$\frac{\delta_{P}(p)y_{1}+\delta_{P}(p)y_{2}}{2}\in\textrm{char.cone}(P)$

since the characteristic cone is closed under taking nonnegative linear
combinations. This contradicts the definition of $\delta_{P}(p)$ as the
shortest distance from a point in $K_{P}$ to $p$ along a vector in
$\textrm{char.cone}(P)$. ∎

Figure 4. The $\textrm{base}_{P}$ map, visualized as sending each point in $P$
to the closest point in $K_{P}$ intersected with the negative characteristic
cone of $P$ based at $x$.

The uniqueness guaranteed by Lemma 5.9 enables us to define the _base map_ for
a single pointed polyhedral set:

######  Definition 5.10.

Let $P\subset\mathbb{R}^{n}$ be a pointed polyhedral set. The _base map_ for
$P$ is the map

$\textrm{base}_{P}:|P|\to|K_{P}|$

defined by setting, for each $p\in|P|$, $\textrm{base}_{P}(p)$ to be the
unique point $x\in|K_{P}|$ such that

$p=x+\delta_{P}(p)y$

for some $y\in\textrm{char.cone}(P)$ with $|y|=1$.

The following technical lemma will be needed to prove that $\textrm{base}_{P}$
is a continuous map (Proposition 5.12).

Figure 5. An illustration of the setup for the proof of Lemma 5.11.

######  Lemma 5.11.

Let $P\subset\mathbb{R}^{n}$ be a pointed polyhedral set. Let $x\in P$. Then
for any $\epsilon>0$, there exists $\eta>0$ such that for every $x^{\prime}\in
P$, if $|x-x^{\prime}|<\eta$ then
$\delta_{P}(x^{\prime})\leq\delta_{P}(x)+\epsilon$.

###### Proof.

Fix any point $p\in P$. Denote by $v_{p}$ the unique element of
$-\textrm{char.cone}(P)$ such that

$p+v_{p}\delta_{P}(p)=\textrm{base}_{P}(p).$

Let $H_{1},\ldots,H_{n}$ be an irredundant collection of hyperplanes that
bound $P$. Then there exists $r=r(p)>0$ such that for each $i=1,\ldots,n$,
either $p\in H_{i}$ or $\overline{B_{r}(p)}\cap H_{i}=\emptyset$. (Here,
$\overline{B_{r}(p)}$ denotes the closed ball of radius $r$ centered at $x$.)
Define

$\displaystyle D_{r}(p):=$ $\displaystyle\\{q\in\mathbb{R}^{n}\mid|q-p|\leq
r\\}\cap P,$ $\displaystyle S_{r}(p):=$
$\displaystyle\\{q\in\mathbb{R}^{n}\mid|q-p|=r\\}\cap P,$ $\displaystyle
M_{p}:=$ $\displaystyle\sup\\{|q-k|\mid q\in D_{r}(x),k\in K_{P}\\}<\infty.$

For each point $q\in S_{r}(p)$, define $v_{q}$ to be the unique element of
$-\textrm{char.cone}(P)$ such that

$q+v_{q}\delta_{P}(q)=\textrm{base}_{P}(q).$

Also for each $q\in S_{r}(p)$, define the path $s_{q}:[0,1]\to P$ by

$s_{q}(\alpha)\coloneqq(1-\alpha)p+\alpha q.$

Note $s_{q}$ is the straight-line path from $p$ to $q$. By construction, for
any $0<r^{\prime}\leq r$,

(5) $\overline{B(p,r^{\prime})}\cap P=\bigcup_{q\in
S_{r}(q),\alpha\in[0,r^{\prime}/r]}s_{q}(\alpha)$

Define, for each $q\in S_{r}(p)$, the path $z_{q}:[0,1]\to\mathbb{R}^{n}$ by

$z_{q}(\alpha)\coloneqq
s(\alpha)+(1-\alpha)\delta_{P}(p)v_{p}+\alpha\delta_{P}(q)v_{q}.$

Note that

$z_{q}(\alpha)=(1-\alpha)(p+\delta_{P}(p)v_{p})+\alpha(q+\delta_{P}(q)v_{q})=(1-\alpha)\textrm{base}_{P}(p)+\alpha\textrm{base}_{P}(q).$

Thus $z_{q}$ is a straight-line path from $\textrm{base}_{P}(p)$ to
$\textrm{base}_{P}(q)$. Therefore, since $\textrm{base}_{P}(p)$ and
$\textrm{base}_{P}(q)$ are in $K_{P}$ and $K_{P}$ is convex, $z_{q}(\alpha)\in
K_{P}$ for all $\alpha$.

Note that

$(1-\alpha)\delta_{P}(p)v_{p}+\alpha\delta_{P}(q)v_{q}\in-\textrm{char.cone}(P)$

since characteristic cones are, by definition, closed under taking nonnegative
linear combinations. Thus, for any $q\in S_{r}(p)$ and any $\alpha\in[0,1]$,

(6)
$\delta_{P}(s_{q}(\alpha))\leq|s_{q}(\alpha)-z_{q}(\alpha)|=|(1-\alpha)\delta_{P}(p)v_{p}+\alpha\delta_{P}(q)v_{q}|\\\
\leq|\delta_{P}(p)v_{p}|+|\alpha\delta_{P}(p)v_{p}|+|\alpha\delta_{P}(q)v_{q}|\leq\delta_{P}(p)+\alpha
2M.$

Set

$\eta\coloneqq\min\left\\{\frac{\epsilon r}{2M},r\right\\}.$

Consider any point $p^{\prime}\in P$ such that

$|p^{\prime}-p|<\eta=\min\left\\{\frac{\epsilon r}{2M},r\right\\}$

By (5), there exists a point $q_{0}\in S_{r}(p)$ and a real number
$\alpha_{0}\in[0,\frac{\epsilon}{2M}]$ such that
$p^{\prime}=s_{q_{0}}(\alpha_{0})$. Hence, by (6), we have

$\delta_{P}(p^{\prime})=\delta_{P}(s_{q_{0}}(\alpha_{0}))\leq\delta_{P}(p)+\alpha_{0}2M\leq\delta_{P}(p)+\epsilon.$

∎

######  Proposition 5.12.

Let $P\subset\mathbb{R}^{n}$ be a pointed polyhedral set of dimension $n$.
Then the function $\textrm{base}_{P}:|P|\to|K_{P}|$ is continuous.

###### Proof.

Suppose $\textrm{base}_{P}$ is not continuous at $p\in P$. This means there
exists $\epsilon>0$ and a sequence of points $\\{p_{n}\\}_{n\in\mathbb{N}}$ in
$P$ such that $\lim_{n\to\infty}p_{n}=p$ but

$|\textrm{base}_{P}(p_{n})-\textrm{base}_{P}(p)|\geq\epsilon$

for all $n\in\mathbb{N}$. Since $K_{P}$ is compact, we may, by passing to a
subsequence if necessary, assume without loss of generality that the sequence
$\\{\textrm{base}_{P}(p_{n})\\}_{n\in\mathbb{N}}$ converges to a point
$x^{\prime}\in K_{P}$. Notice $\textrm{base}_{P}(p)\neq x^{\prime}$, since
$|\textrm{base}_{P}(p)-x^{\prime}|\geq\epsilon$.

The vectors $p_{n}-\textrm{base}_{P}(p_{n})$ are all in
$\textrm{char.cone}(P)$ by definition. Since

(7)
$p-x^{\prime}=\left(\lim_{n\to\infty}p_{n}\right)-\left(\lim_{n\to\infty}\textrm{base}_{P}(p_{n})\right)=\lim_{n\to\infty}(p_{n}-\textrm{base}_{P}(p_{n})),$

and $\textrm{char.cone}(P)$ is closed, (7) implies

(8) $p-x^{\prime}\in\textrm{char.cone}(P).$

Now fix any $\epsilon>0$. Pick $N_{1}\in\mathbb{N}$ such that
$|p-p_{n}|<\epsilon/2$ for all $n\geq N_{1}$. By Lemma 5.11, we may pick
$N_{2}\in\mathbb{N}$ such that

$\delta_{P}(p_{n})=|p_{n}-\textrm{base}_{P}(p_{n})|\leq|p-\textrm{base}_{P}(p)|+\epsilon/2$

for all $n\geq N_{2}$. Hence, for $n\geq\textrm{max}\\{N_{1},N_{2}\\}$, we
have

(9)
$|p-\textrm{base}_{P}(p_{n})|\leq|p-p_{n}|+|p_{n}-\textrm{base}_{P}(p_{n})|\\\
\leq\epsilon/2+|p-\textrm{base}_{P}(p)|+\epsilon/2=\delta_{P}(p)+\epsilon.$

Since $\epsilon$ was arbitrary, (9) implies

(10)
$|p-x^{\prime}|=|p-\lim_{n\to\infty}\textrm{base}_{P}(p_{n})|\leq|p-\textrm{base}_{P}(p)|.$

Thus

$p=x^{\prime}+|p-x^{\prime}|\frac{p-x^{\prime}}{|p-x^{\prime}|},$

where $x^{\prime}$ is a point in $K_{P}$ distinct from $\textrm{base}_{P}(p)$,
$\frac{p-x^{\prime}}{|p-x^{\prime}|}\in\textrm{char.cone}(P)$ by (8) and has
unit length, and $|p-x^{\prime}|\leq\delta_{P}(p)$ by (10). This contradicts
the fact that $x=\textrm{base}_{P}(p)$ is the unique (by Lemma 5.9) point in
$K_{P}$ such that $p=x+cv$ for some $x\in K_{P}$, unit vector
$v\in\textrm{char.cone}(P)$ and constant $0\leq c\leq\delta_{P}(p)$.

∎

######  Lemma 5.13.

Let $P\subset\mathbb{R}^{n}$ be a pointed polyhedral set and let $F$ be a face
of $P$. Then $\textrm{base}_{P}(F)\subseteq F$.

###### Proof.

If $F$ is either $P$ itself or a $0$-cell of $P$, the result is immediate. So
assume $F$ is a proper face of $P$ (i.e. $0<\textrm{dim}(F)<\textrm{dim}(P)$)
and fix a point $p\in F$. Suppose, for a contradiction, there exists $x\in
K_{P}\setminus F$ such that $p=x+ty$ for some $y\in\textrm{char.cone}(P)$ with
$|y|=1$ and $t>0$.

Let $H$ be the affine hull of $F$. Since $P$ is convex, $F=P\cap H$. Since
$x\not\in F$, this implies $x\not\in H$. Therefore the vector
$y=\tfrac{p-x}{t}$ is not in the tangent space $T_{p}H$, i.e. the ray
$\\{x+ty\mid t\geq 0\\}$ “crosses” $F$. Since $P$ is convex and $F$ is in the
boundary of $P$, points of the form $x+ty$ are in $P$ whenever $0\leq
t\leq|p-x|$ and are not in $P$ whenever $t>|p-x|$. In particular,

$x+(|p-x|+\epsilon)y=p+\epsilon y\not\in P$

for $\epsilon>0$. This contradicts the assumption that
$y\in\textrm{char.cone}(P)$. ∎

######  Lemma 5.14.

Let $P$ be an $n$-dimensional polyhedral set in $\mathbb{R}^{n}$ and let $F$
be a face of $P$. Then the maps $\textrm{base}_{P}$ and $\textrm{base}_{F}$
agree on $|F|$.

###### Proof.

Since $\textrm{base}_{P}(F)\subset F$ by Lemma 5.13 and $F\subset P$, we must
have $\delta_{P}(p)=\delta_{F}(p)$ for every point $p\in F$. By Lemma 5.9,
there is a unique point in $F$ that that realizes this minimum. ∎

An immediate corollary of Lemma 5.14 is that base maps for different cells of
a polyhedral complex in $\mathbb{R}^{n}$ agree on shared faces:

######  Corollary 5.15.

Let $P_{1}$ and $P_{2}$ be two distinct, pointed, polyhedral sets in a
polyhedral complex embedded in $\mathbb{R}^{n}$ that share a common face $F$.
Then for every point $p\in|F|$,
$\textrm{base}_{P_{1}}(p)=\textrm{base}_{P_{2}}(p)$.

As a consequence of Corollary 5.15, we can formulate the following definition:

######  Definition 5.16.

Let $\mathcal{C}$ be a polyhedral complex embedded in $\mathbb{R}^{n}$ in
which all cells are pointed. Define the function

$\textrm{base}_{\mathcal{C}}:|\mathcal{C}|\to|\textrm{com.part}(\mathcal{C})|$

by whichever of the functions $\textrm{base}_{P}$, for $P\in\mathcal{C}$, is
defined.

######  Proposition 5.17.

For any polyhedral complex $\mathcal{C}$ embedded in $\mathbb{R}^{n}$, the map
$\textrm{base}_{\mathcal{C}}$ is continuous.

###### Proof.

Proposition 5.12 asserts that for each top-dimensional cell $P\in\mathcal{C}$,
the map $\textrm{base}_{P}$ is continuous. Corollary 5.15 asserts that if two
cells share a face, the base maps for those cells agree on the shared face.
Consequently, $\textrm{base}_{\mathcal{C}}$ is continuous. ∎

######  Proposition 5.18.

Let $\mathcal{C}$ be a polyhedral complex embedded in $\mathbb{R}^{n}$ in
which all cells are pointed. Define
$\Phi:|\mathcal{C}|\times[0,1]\to|\mathcal{C}|$ by

$\Phi(p,t)=t\textrm{base}_{\mathcal{C}}(p)+(1-t)p.$

Then $\Phi$ is a strong deformation retraction of $|\mathcal{C}|$ onto
$|\textrm{com.part}(\mathcal{C})|$.

###### Proof.

It suffices to show that $\Phi$ is continuous – but this is an immediate
consequence of the fact that $\textrm{base}_{\mathcal{C}}$ is continuous
(Proposition 5.17). ∎

###### Proof of Proposition 5.8.

The strong deformation retract $\Phi$ of Proposition 5.18 induces the map
$\textrm{base}_{\mathcal{C}}:|\mathcal{C}|\to|\textrm{com.part}(\mathcal{C})|$.
By Lemma 5.13, the map $\textrm{base}_{\mathcal{C}}$ in turn induces a
cellular map

$\underline{\textrm{base}}_{\mathcal{C}}:\mathcal{C}\to\textrm{com.part}(\mathcal{C})$

defined by setting $\underline{\textrm{base}}_{\mathcal{C}}(C)$ to be the
smallest cell in $\textrm{com.part}(\mathcal{C})$ that contains the set
$\textrm{base}_{\mathcal{C}}(C)$. Since $\textrm{base}_{\mathcal{C}}$ is the
identity on $|\textrm{com.part}(\mathcal{C})|$, the cellular map
$\underline{\textrm{base}}_{\mathcal{C}}$ is surjective. ∎

###  5.3. The canonical polytopal complex of unpointed polyhedral complexes

This subsection extends the definitions and results of Subsection 5.2 to
arbitrary polyhedral complexes $\mathcal{C}$ in $\mathbb{R}^{n}$ – dropping
the requirement that all cells of $\mathcal{C}$ be pointed.

To begin, we establish the _Pointedness Dichotomy_ (Corollary 5.29): If
$\mathcal{C}$ is a connected polyhedral complex imbedded in $\mathbb{R}^{n}$,
then either every cell of $\mathcal{C}$ is pointed or every cell of
$\mathcal{C}$ is unpointed. This will allow us to associate to any connected
polyhedral complex $\mathcal{C}$ a homotopy-equivalent pointed connected
polyhedral complex, which we call its _essentialization_. We can then apply
the results of Subsection 5.2 to the essentialization of $\mathcal{C}$ to
obtain a homotopy-equivalent compact model for $\mathcal{C}$.

####  5.3.1. Unpointed polyhedral complexes and their essentializations

For a hyperplane arrangement $\mathcal{A}$ in $\mathbb{R}^{n}$, we will call
the linear space spanned by the normal vectors of $\mathcal{A}$ the _normal
span_ of $\mathcal{A}$ and denote it by $\textrm{n.span}(\mathcal{A})$. The
_rank_ of a hyperplane arrangement is defined as the dimension of
$\textrm{n.span}(\mathcal{A})$.

Every polyhedral set $P\subset\mathbb{R}^{n}$ admits a _irredundant
realization_ as the intersection of finitely many closed half-spaces,
$P=H_{1}^{+}\cap\ldots H_{m}^{+}$, such that $P$ is not equal to the
intersection of any proper subset of $\\{H_{1}^{+},\ldots,H_{m}^{+}\\}$ ([5,
Sec. 26]). If $P$ is $n$-dimensional, this irredundant realization is unique:
the boundaries of these half-spaces are the affine hulls of the
$(n-1)$-dimensional faces of $P$.

######  Definition 5.19.

Let $P\subset\mathbb{R}^{n}$ be a polyhedral set (of arbitrary dimension).

  1. (i)

Define the _normal span_ of $P$, denoted $\textrm{n.span}(P)$, to be the
linear space spanned by the set of all vectors $v$ that are normal to some
hyperplane $H$ such that $H\cap P=\emptyset$.

  2. (ii)

Define the _rank_ of $P$, denoted $\textrm{rank}(P)$, to be the dimension of
$\textrm{n.span}(P)$

The following well-known lemma asserts that any redundant inequality in a
system of linear inequalities with non-empty solution set is a non-negative
linear combination of the other linear inequalities in the system:

######  Lemma 5.20.

(Farkas’ Lemma III, [14, Prop. 1.9]) Let $A\in\mathbb{R}^{m\times d}$,
$z\in\mathbb{R}^{m}$, $a_{0}\in\mathbb{R}^{d}$, $z_{0}\in\mathbb{R}$. Then
$a_{0}^{T}x\leq z_{0}$ is valid for all $x\in\mathbb{R}^{d}$ with $Ax\leq z$
if and only if at least one of the following hold:

  1. (i)

there exists a row vector $c\geq\vec{0}$ such that $cA=a_{0}^{T}$ and $cz\leq
z_{0}$

  2. (ii)

there exists a row vector $c\geq\vec{0}$ such that $cA=\vec{0}$ and $cz<0$

######  Remark 5.21.

All inequalities in Farkas’ Lemma III should be interpreted coordinate-wise.
Condition (i) is the statement that the inequality $a_{0}^{T}x\leq z_{0}$ is
redundant and can be expressed as a positive linear combination of the other
inequalities in the system $Ax\leq z$; condition (ii) implies that the
polyhedral set determined by $Ax\leq z$ is empty.

######  Corollary 5.22.

Let $P$ be a polyhedral set of dimension $n$ in $\mathbb{R}^{n}$. Then
$\textrm{n.span}(P)=\textrm{n.span}(\mathcal{A})$ where $\mathcal{A}$ is the
hyperplane arrangement

$\mathcal{A}\coloneqq\\{\textrm{aff}(F)\mid F\textrm{ is an
}(n-1)\textrm{-cell of }P\\}.$

###### Proof.

If $F$ is an $(n-1)$-face of $P$, then parallel translating $\textrm{aff}(F)$
along the normal vector to the hyperplane $\textrm{aff}(F)$ in the direction
“away” from $P$ yields a hyperplane disjoint from $P$. Hence
$\textrm{n.span}(\mathcal{A})\subset\textrm{n.span}(P)$. Farkas’ Lemma III
gives the reverse containment,
$\textrm{n.span}(\mathcal{A})\supset\textrm{n.span}(P)$. ∎

######  Lemma 5.23.

Let $P$ be a polyhedral set, and let $F$ be a proper face of $P$. Then
$\textrm{n.span}(P)=\textrm{n.span}(F)$.

###### Proof.

Let $P=H_{1}^{+}\cap\ldots\cap H_{k}^{+}$ be a realization of $P$ as an
intersection of half-spaces and, for each $i$, let $\vec{v}_{i}$ be a vector
normal to $H_{i}$. Farkas’ Lemma then tells us that
$\textrm{n.span}(P)=\mbox{span}\\{\vec{v}_{1},\ldots,\vec{v}_{k}\\}$.

Note that is immediate from Definition 5.19 that
$\textrm{n.span}(P)\subseteq\textrm{n.span}(F)$. To see that
$\textrm{n.span}(F)\subseteq\textrm{n.span}(P)$, note that $F=P\cap
H^{\prime}$ for $H^{\prime}$ a supporting hyperplane of $P$ containing
$\textrm{aff}(F)$, and therefore

$F=(H_{1}^{+}\cap\ldots\cap
H_{k}^{+})\cap(H^{\prime})^{+}\cap(H^{\prime})^{-}$

is a realization of $F$ as an intersection of half-spaces.

Let $\pm\vec{v}$ be a nonzero vector normal to $H^{\prime}$ in the direction
of $(H^{\prime})^{\pm}$. Since $H^{\prime}$ is a supporting hyperplane of $P$,
at least one of $H^{\prime}\pm\vec{v}$ is disjoint from $P$, so
$v\in\textrm{n.span}(P)$. We then conclude that

$\textrm{n.span}(F)=\mbox{span}\\{v,v_{1},\ldots,v_{k}\\}=\mbox{span}\\{v_{1},\ldots,v_{k}\\}=\textrm{n.span}(P),$

as desired. ∎

######  Lemma 5.24.

Let $\mathcal{C}$ be a polyhedral complex in $\mathbb{R}^{n}$, and let
$P_{1},P_{2}$ be cells of $\mathcal{C}$. If $P_{1}$ and $P_{2}$ share a common
face $F$, then $\textrm{n.span}(P_{1})=\textrm{n.span}(P_{2})$.

###### Proof.

By Lemma 5.23, $n.span(P_{1})=n.span(F)=n.span(P_{2})$. ∎

The following is now immediate:

######  Lemma 5.25.

Let $\mathcal{C}$ be a connected polyhedral complex in $\mathbb{R}^{n}$. Then
$\textrm{n.span}(C)$ is independent of $C\in\mathcal{C}$.

In view of Lemma 5.25, we can formulate the following definition:

######  Definition 5.26.

For $\mathcal{C}$ a connected polyhedral complex in $\mathbb{R}^{n}$, define

$\displaystyle\textrm{n.span}(\mathcal{C})$
$\displaystyle\coloneqq\textrm{n.span}(C)$
$\displaystyle\textrm{rank}(\mathcal{C})$
$\displaystyle\coloneqq\textrm{rank}(C)$

for any cell $C\in\mathcal{C}$.

######  Remark 5.27.

The conclusion of Lemma 5.25 may not hold if $\mathcal{C}$ is not connected.
For example, consider the polyhedral complex in $\mathbb{R}^{2}$ consisting of
the infinite strip $C_{1}\coloneqq[0,1]\times\mathbb{R}$ and the square
$C_{2}\coloneqq[2,3]\times[2,3]$, along with all the faces of $C_{1}$ and
$C_{2}$. Then $\textrm{n.span}(C_{1})=\mathbb{R}\times 0$ and
$\textrm{n.span}(C_{2})=\mathbb{R}^{2}$.

######  Lemma 5.28.

Let $P\subset\mathbb{R}^{n}$ be a polyhedral set of dimension $n$. Then $P$ is
pointed if and only if $\textrm{rank}(P)=n$.

###### Proof.

Without loss of generality, we may assume $P$ contains the origin. Denote the
polar dual of $P$ by $P^{*}$:

$P^{*}\coloneqq\\{z\in\mathbb{R}^{n}\mid z^{T}x\leq 1\textrm{ for all }x\in
P\\}.$

We have

$n=\textrm{rank}(P)=\textrm{dim}(\textrm{n.span}(P))=\textrm{dim}(P^{*}).$

By Theorem 9.1 of [12], $P^{*}$ is a polyhedron and $P^{**}=P$. By Corollary
9.1a of [12], $P^{**}$ is pointed. ∎

Lemma 5.28 has the following immediate corollary:

######  Corollary 5.29 (Pointedness Dichotomy).

Let $\mathcal{C}$ be a connected polyhedral complex in $\mathbb{R}^{n}$. If
$\textrm{rank}(\mathcal{C})=n$ then every cell of $\mathcal{C}$ is pointed;
otherwise every cell of $\mathcal{C}$ is unpointed.

######  Lemma 5.30.

Let $\mathcal{C}$ be a $n$-dimensional, connected polyhedral complex in
$\mathbb{R}^{n}$. Let $\mathcal{A}$ be the hyperplane arrangement

$\mathcal{A}\coloneqq\\{\textrm{aff}(F)\mid F\textrm{ is an
}(n-1)\textrm{-cell of }\mathcal{C}\\}.$

Then

$\textrm{n.span}(\mathcal{A})=\textrm{n.span}(\mathcal{C}).$

###### Proof.

For any $(n-1)$-cell $F\in\mathcal{C}$, normal vectors to $\textrm{aff}(F)$
are contained in $\textrm{n.span}(F)$. By Lemma 5.25,
$\textrm{n.span}(F)=\textrm{n.span}(\mathcal{C})$. Hence
$\textrm{n.span}(\mathcal{A})\subset\textrm{n.span}(\mathcal{C})$.

For the converse, fix any $n$-cell $C\in\mathcal{C}$. Then Lemma 5.22 implies

$\textrm{n.span}(\mathcal{C})=\textrm{n.span}(C)=\textrm{rank}(\mathcal{H}),$

where $\mathcal{H}$ is the hyperplane arrangement

$\mathcal{H}\coloneqq\\{\textrm{aff}(D)\mid D\textrm{ is an
}(n-1)\textrm{-face of }C\\}.$

Since $\mathcal{H}\subset\mathcal{A}$, this yields
$\textrm{n.span}(\mathcal{C})\subset\textrm{n.span}(\mathcal{A})$. ∎

######  Remark 5.31.

A decomposition like the one shown in Figure 6 is not a counterexample to
Corollary 5.29, because it is _not_ a polyhedral decomposition of
$\mathbb{R}^{2}$ (c.f. Section 2). Specifically, $C_{2}\cap C_{3}$ is not a
face of $C_{2}$, as it cannot be written as $C_{2}\cap H$ for a supporting
hyperplane $H$ of $C_{2}$. Similarly, $C_{2}\cap C_{4}$ is not a face of
$C_{2}$.

$C_{1}$$C_{2}$$C_{3}$$C_{4}$ Figure 6. The “nonexample” of polyhedral
decomposition of $\mathbb{R}^{2}$ of Remark 5.31.

Recall that the _essentialization_ (see e.g. [13]) of a hyperplane arrangement
$\mathcal{A}$ in $\mathbb{R}^{n}$ is the hyperplane arrangement

$\textrm{ess}(\mathcal{A})\coloneqq\\{H\cap\textrm{n.span}(\mathcal{A})\mid
H\textrm{ is a hyperplane in }\mathcal{A}\\}$

in the linear space $\textrm{n.span}(\mathcal{A})\subset\mathbb{R}^{n}$.
Denoting by $\text{n.span}(\mathcal{A})^{\perp}$ the orthogonal complement of
$\textrm{n.span}(\mathcal{A})$ in $\mathbb{R}^{n}$, it follows immediately
from the definition that $H^{\prime}\in\textrm{ess}(\mathcal{A})$ if and only
if $H^{\prime}\oplus\text{n.span}(\mathcal{A})^{\perp}\in\mathcal{A}$ ([13]).

We define the essentialization of an unpointed polyhedral decomposition of
$\mathbb{R}^{n}$:

######  Definition 5.32.

Let $\mathcal{C}$ be a connected polyhedral complex in $\mathbb{R}^{n}$.
Define the _essentialization of $\mathcal{C}$_ to be the family of sets

$\textrm{ess}(\mathcal{C})\coloneqq\\{C\cap\textrm{n.span}(\mathcal{C})\mid
C\in\mathcal{C}\\}$

######  Remark 5.33.

An immediate consequence of Corollary 5.29 is that every cell of
$\textrm{ess}(\mathcal{C})$ is pointed. Furthermore, Corollary 5.29 implies
that if all cells of $\mathcal{C}$ are pointed, then
$\textrm{ess}(\mathcal{C})=\mathcal{C}$.

The reader may verify the following result:

######  Lemma 5.34.

For any connected polyhedral complex $\mathcal{C}$ in $\mathbb{R}^{n}$, the
essentialization of $\mathcal{C}$, $\textrm{ess}(\mathcal{C})$, is a
polyhedral complex and
$|\textrm{ess}(\mathcal{C})|=\textrm{n.span}(\mathcal{C})\cap|\mathcal{C}|$.

######  Lemma 5.35.

Let $\mathcal{C}$ be a connected polyhedral complex in $\mathbb{R}^{n}$. Then
there is a strong deformation retraction
$r:|\mathcal{C}|\times[0,1]\to|\textrm{ess}(\mathcal{C})|$ such that

  1. (i)

If $C$ is a $k$-cell of $\mathcal{C}$, $r(C)$ is a
$(k-n+\textrm{rank}(\mathcal{C}))$-cell of $\textrm{ess}(\mathcal{C})$.

  2. (ii)

The cellular map $\mathcal{C}\to\textrm{ess}(\mathcal{C})$ given by $C\mapsto
r(C)$ is a poset-preserving bijection.

  3. (iii)

$r(C)\subset C$ for all $C\in\mathcal{C}$.

###### Proof sketch.

Let $\pi:\mathbb{R}^{n}\to\textrm{n.span}(\mathcal{C})$ denote orthogonal
projection onto $\textrm{n.span}(\mathcal{A})$. Then the linear contraction
$r(x,t)\coloneqq xt+\pi(x)(1-t)$ has the desired properties. ∎

We are now ready to define the canonical polytopal complex associated to a
polyhedral complex imbedded in $\mathbb{R}^{n}$.

######  Definition 5.36.

Let $\mathcal{C}$ be a connected polyhedral complex in $\mathbb{R}^{n}$. The
_canonical polytopal complex_ $\mathcal{K}(\mathcal{C})$ associated to
$\mathcal{C}$ is the polytopal complex

$\mathcal{K}(\mathcal{C})\coloneqq\textrm{com.part}(\textrm{ess}(\mathcal{C})).$

######  Remark 5.37.

If every cell in $\mathcal{C}$ is pointed,
$\textrm{ess}(\mathcal{C})=\mathcal{C}$, so the canonical polytopal complex
$\mathcal{K}(\mathcal{C})$ is just $\textrm{com.part}(\mathcal{C})$ from
Definition 5.4.

######  Theorem 7.

Let $\mathcal{C}$ be a connected polyhedral complex in $\mathbb{R}^{n}$. Then
there is a strong deformation retraction
$H:|\mathcal{C}|\to|\mathcal{K}(\mathcal{C})|$ that induces a surjective
cellular map from $\mathcal{C}$ to the canonical polytopal complex
$\mathcal{K}(\mathcal{C})$ that preserves the face poset relation.

###### Proof.

Lemma 5.35 gives a strong deformation retraction from the arbitrary polyhedral
complex $\mathcal{C}$ in $\mathbb{R}^{n}$ to the pointed polyhedral complex
$\textrm{ess}(\mathcal{C})$ that induces a surjective cellular map that
preserves the face poset relation. Proposition 5.8 then applies to the strong
deformation retraction of $\textrm{ess}(\mathcal{C})$ onto its compact part. ∎

###  5.4. Homotopy equivalence of sublevel sets

####  5.4.1. The pointed case

Recall that the _product complex_ $\mathcal{K}\times\mathcal{L}$ of two
polyhedral complexes $\mathcal{K}$ and $\mathcal{L}$ is the polyhedral complex
consisting of all pairwise products of cells:

$\mathcal{K}\times\mathcal{L}\coloneqq\\{K\times L\mid
K\in\mathcal{K},L\in\mathcal{L}\\}.$

Definition 5.38 and Lemma 5.40 involve a product complex in which one factor
is the complex denoted $[a,b]$, which consists of the real interval $[a,b]$
together with its faces.

######  Definition 5.38.

[6, Defn. 4.4] Let $M$ be a polyhedral complex and $f:|M|\to\mathbb{R}$ linear
on cells. An _$f$ -level-preserving PL isotopy of level sets_ between $M_{=a}$
and $M_{=b}$ is a PL homeomorphism

$\phi:|M|_{=h}\times[a,b]\to|M|_{\in[a,b]}$

for $h\in[a,b]$ such that for every $t\in[a,b]$, the restriction of $\phi$ to
$|M|_{=h}\times\\{t\\}$ is a PL homeomorphism between $|M|_{=h}\times\\{t\\}$
and $|M|_{=t}$.

######  Definition 5.39.

Two polyhedral complexes $K$ and $L$ are said to be _combinatorially
equivalent_ if there is a bijection $\phi:K\to L$ of cells that preserves both
dimension and the poset structure given by the face relation. That is:

  1. (i)

For all $S,T\in K$, $S$ is a face of $T$ in $K$ if and only if $\phi(S)$ is a
face of $\phi(T)$ in $L$ and

  2. (ii)

For all $S\in K$, $\textrm{dim}(S)=\textrm{dim}(\phi(S))$.

An upshot of Theorem 7 is that it enables us to leverage the following result
of Grunert, which only applies to polytopal complexes, into a result for
polyhedral complexes.

######  Lemma 5.40.

[6, Lem. 4.13] Let $M$ be a polytopal complex with a map $f:|M|\to\mathbb{R}$
linear on cells. Suppose no vertex of $M$ has a value $f(v)\in[a,b]$ under
$f$. Then for any $t\in[a,b]$, the complexes $M_{=t}\times[a,b]$ and
$M_{\in[a,b]}$ are combinatorially equivalent (via the combinatorial
equivalence $C_{=t}\times[a,b]\mapsto C_{\in[a,b]}$) and there is an
$f$-level-preserving PL isotopy $\phi:|M|_{=t}\times[a,b]\to|M|_{\in[a,b]}$.

We will use the following well-known result:

######  Lemma 5.41 ([4]).

Let $F:\mathbb{R}^{n_{0}}\to\mathbb{R}$ be a neural network, and
$\mathcal{C}(F)$ be its canonical polyhedral complex. If $\mathcal{P}$ is a
cell of $\mathcal{C}(F)$ with at least one vertex as a face, and $F$ achieves
a maximum (resp., minimum) on $\mathcal{P}$, then $F$ achieves a maximum
(resp., minimum) at a vertex of $\mathcal{P}$.

######  Lemma 5.42.

Let $\mathcal{C}$ be a polyhedral complex in $\mathbb{R}^{n}$ of which every
cell is pointed. Let $F:|\mathcal{C}|\to\mathbb{R}$ be linear on cells of
$\mathcal{C}$. Let $[a,b]$ be an interval of transversal thresholds for $F$ on
$\mathcal{C}$. Then there exists $\epsilon>0$ such that for every cell
$C\in\mathcal{C}$ for which $F(C)\cap[a,b]$ is nonempty, we have

$F(C)\supseteq[a-\epsilon,b+\epsilon].$

###### Proof.

Since $\mathcal{C}$ has only finitely many cells and $F$, it suffices to show
the result for each cell. So fix any cell $C\in\mathcal{C}$ such that
$F(C)\cap[a,b]\neq\emptyset$. By continuity of $F$, it suffices to show there
exist points $w,v\in C$ such that $F(w)<a$ and $F(v)>b$.

If $F$ is unbounded above, such a point $v$ clearly exists. So suppose $F$ is
bounded above (on $C$). Since $F$ is linear on $C$, $F$ achieves its maximum,
which we denote $m$. By assumption, $F$ attains a value $\geq a$ somewhere on
$C$, so $m\geq a$. By Lemma 5.41, $F$ attains $m$ on a $0$-cell of $C$. Hence
$m$ is not a transversal threshold. Thus $m>b$.

A similar argument shows the existence of $w\in C$ such that $F(w)<a$. ∎

Recall that for a real-valued function $F$, a map $b$ is said to be _$F$
-level preserving_ if $F(x)=F(b(x))$ for all $x$.

######  Lemma 5.43.

Let $\mathcal{C}$ be a polyhedral complex in $\mathbb{R}^{n}$ in which all
cells are pointed. Let $F:|\mathcal{C}|\to\mathbb{R}$ be linear on cells. Let
$[a,b]$ be an interval of transversal thresholds for $F$ on $\mathcal{C}$. Fix
$\epsilon>0$ as in Lemma 5.42. Let $I_{a-\epsilon,b+\epsilon}$ be the
polyhedral decomposition of $\mathbb{R}$ whose $1$-cells are
$(-\infty,a-\epsilon],[a-\epsilon,b+\epsilon]$ and $[b+\epsilon,\infty)$. Let
$\mathcal{C}^{\prime}$ be the refinement of $\mathcal{C}$ obtained as the
following level set complex:

$\mathcal{C}^{\prime}=\mathcal{C}_{F\in I_{a-\epsilon,b+\epsilon}}.$

Then the following hold:

  1. (i)

The surjective map
$\textrm{base}_{\mathcal{C}^{\prime}}:|\mathcal{C}^{\prime}|\to|\textrm{com.part}(\mathcal{C}^{\prime})|$
is induced by a strong deformation retraction.

  2. (ii)

The restriction of $\textrm{base}_{\mathcal{C}^{\prime}}$ to the set

$F_{[a,b]}\coloneqq\\{x\in|\mathcal{C}|:a\leq F(x)\leq b\\}$

is $F$-level preserving. Equivalently, for any $a\leq c\leq b$,

$\textrm{base}_{\mathcal{C}^{\prime}}(F_{=c})=|\textrm{com.part}(\mathcal{C}^{\prime})_{F=c}|.$

  3. (iii)

$\displaystyle\textrm{base}_{\mathcal{C}^{\prime}}(F_{\leq a-\epsilon})$
$\displaystyle=|\textrm{com.part}(\mathcal{C}^{\prime})_{F\leq a-\epsilon}|,$
$\displaystyle\textrm{base}_{\mathcal{C}^{\prime}}(F_{\geqq b+\epsilon})$
$\displaystyle=|\textrm{com.part}(\mathcal{C}^{\prime})_{F\geq b+\epsilon}|,$
$\displaystyle\textrm{base}_{\mathcal{C}^{\prime}}(F_{[a-\epsilon,a)})$
$\displaystyle\subseteq|\textrm{com.part}(\mathcal{C}^{\prime})_{F\in[a-\epsilon,a)}|,$
$\displaystyle\textrm{base}_{\mathcal{C}^{\prime}}(F_{(b,b+\epsilon]})$
$\displaystyle\subseteq|\textrm{com.part}(\mathcal{C}^{\prime})_{F\in(b,b+\epsilon]}|,$
$\displaystyle\textrm{base}_{\mathcal{C}^{\prime}}(F_{\leq a})$
$\displaystyle=|\textrm{com.part}(\mathcal{C}^{\prime})_{F\leq a}|,$
$\displaystyle\textrm{base}_{\mathcal{C}^{\prime}}(F_{\geq b})$
$\displaystyle=|\textrm{com.part}(\mathcal{C}^{\prime})_{F\geq b}|.$

  4. (iv)

For any $a\leq c\leq b$,

$\displaystyle\textrm{base}_{\mathcal{C}^{\prime}}(F_{=c})$
$\displaystyle=|\textrm{com.part}(\mathcal{C}^{\prime})_{F=c}|,$
$\displaystyle\textrm{base}_{\mathcal{C}^{\prime}}(F_{\leq c})$
$\displaystyle=|\textrm{com.part}(\mathcal{C}^{\prime})_{F\leq c}|,$
$\displaystyle\textrm{base}_{\mathcal{C}^{\prime}}(F_{\geq c})$
$\displaystyle=|\textrm{com.part}(\mathcal{C}^{\prime})_{F\geq c}|.$

###### Proof.

Note that (i) holds by Proposition 5.8.

Consider any cell $C^{\prime}\in\mathcal{C}^{\prime}$ that has nonempty
intersection with $F_{[a,b]}$. By our choice of $\epsilon$, we must have
$F(C^{\prime})=[a-\epsilon,b+\epsilon]$. By construction, there exists a cell
$C\in\mathcal{C}$ such that

$C^{\prime}=C\cap F_{[a-\epsilon,b+\epsilon]}.$

So $F(C)\supseteq[a-\epsilon,b+\epsilon]$. Thus, the level sets
$F_{=a-\epsilon}$ and $F_{=b-\epsilon}$ both have nonempty intersection with
$C$. Furthermore, the sets $F_{=a-\epsilon}\cap C$ and $F_{=b-\epsilon}\cap C$
are faces of $C^{\prime}$.

We claim that $\textrm{char.cone}(C^{\prime})$ consists of directions along
with $F$ is constant. Indeed, consider any point $p\in C^{\prime}$ and any
vector $v\in\textrm{char.cone}(C^{\prime})$. Then the point $p+tv\in
C^{\prime}$ for all $t\geq 0$. By affine-linearity of $F$,
$F(p+tv)=F(p)+t\frac{dF}{dv}$. Thus, if the derivative $\frac{dF}{dv}<0$,
$C^{\prime}$ must contain a point where $F$ attains a value less than
$a-\epsilon/2$, which is impossible. Similarly, if $\frac{dF}{dv}>0$,
$C^{\prime}$ must contain a point where $F$ attains a value greater than
$a-\tfrac{\epsilon}{2}$, which is also impossible. Hence $\frac{dF}{dv}=0$,
and the claim follows.

The map $\textrm{base}_{C^{\prime}}$ acts on $C^{\prime}$ by collapsing rays
in $\textrm{char.cone}(C^{\prime})$. Since $F$ is constant along each ray in
$\textrm{char.cone}(C^{\prime})$, it follows that $\textrm{base}_{C^{\prime}}$
is $F$-level preserving. Since $\textrm{base}_{\mathcal{C}^{\prime}}$ is
defined cell-by-cell and agrees on shared faces, this implies that
$\textrm{base}_{\mathcal{C}^{\prime}}$ is $F$-level preserving on $F_{[a,b]}$,
establishing (ii).

Next, note that by construction of $\mathcal{C}^{\prime}$, each cell
$D\in\mathcal{C}^{\prime}$ satisfies at least one of the following:

  1. (i)

$F(D)\subseteq(-\infty,a-\epsilon]$,

  2. (ii)

$F(D)\subseteq[a-\epsilon,a)$

  3. (iii)

$F(D)\subseteq[b+\epsilon,\infty)$.

  4. (iv)

$F(D)\subseteq(b,b+\epsilon]$,

  5. (v)

$F(D)=[a-\epsilon,b+\epsilon]$.

The argument above shows that $\textrm{base}_{\mathcal{C}^{\prime}}$ is
$F$-level preserving on cells $D$ of type (v). The map
$\textrm{base}_{\mathcal{C}^{\prime}}$ is not necessarily $F$-level preserving
on cells of the other types, but we do have the containment
$\textrm{base}_{\mathcal{C}^{\prime}}(D)\subseteq D$ for every cell $D$.
Hence:

$\displaystyle\textrm{base}_{\mathcal{C}^{\prime}}(F_{\leq a-\epsilon})$
$\displaystyle=|\textrm{com.part}(\mathcal{C}^{\prime})_{F\leq a-\epsilon}|,$
$\displaystyle\textrm{base}_{\mathcal{C}^{\prime}}(F_{\geqq b+\epsilon})$
$\displaystyle=|\textrm{com.part}(\mathcal{C}^{\prime})_{F\geq b+\epsilon}|,$
$\displaystyle\textrm{base}_{\mathcal{C}^{\prime}}(F_{[a-\epsilon,a)})$
$\displaystyle\subseteq|\textrm{com.part}(\mathcal{C}^{\prime})_{F\in[a-\epsilon,a)}|,$
$\displaystyle\textrm{base}_{\mathcal{C}^{\prime}}(F_{(b,b+\epsilon]})$
$\displaystyle\subseteq|\textrm{com.part}(\mathcal{C}^{\prime})_{F\in(b,b+\epsilon]}|.$

Consequently, for any point $p$ in the closed set
$|\textrm{com.part}(\mathcal{C}^{\prime})_{F\in[a-\epsilon,a]}|$, if
$x\in|\mathcal{C}^{\prime}|$ satisfies $\textrm{base}_{\mathcal{C}}(x)=p$,
then at least one of the following holds: $x$ belongs to a cell of type (ii);
$x$ belongs to a cell of type (v) and $F(x)=F(p)$. Since
$\textrm{base}_{\mathcal{C}^{\prime}}:|\mathcal{C}^{\prime}|\to|\textrm{com.part}(\mathcal{C}^{\prime})|$
is surjective, it follows that

$\textrm{base}_{\mathcal{C}^{\prime}}(F_{\leq
a})=|\textrm{com.part}(\mathcal{C}^{\prime})_{F\leq a}|.$

An analogous argument yields

$\textrm{base}_{\mathcal{C}^{\prime}}(F_{\geq
b})=|\textrm{com.part}(\mathcal{C}^{\prime})_{F\geq b}|,$

establishing (iii).

Conclusion (iv) follows immediately from (ii) and (iii) together.

∎

######  Lemma 5.44.

Let $\mathcal{C},F,a,b,\epsilon,\mathcal{C}^{\prime}$ be as in Lemma 5.43.
Then $[a,b]$ is an interval of transversal thresholds for $F$ with respect to
the complex $\textrm{com.part}(\mathcal{C}^{\prime})$.

###### Proof.

First, note that $[a,b]$ is an interval of transversal thresholds for $F$ with
respect to the complex $\mathcal{C}^{\prime}$. This is because the complexes
$\mathcal{C}$ and $\mathcal{C}^{\prime}$ only differ away from points of
$F_{[a,b]}$. Thus, $\mathcal{C}^{\prime}$ has no flat cells where $F$ takes
values in $[a,b]$. Since $\mathcal{C}^{\prime}$ and
$\textrm{com.part}(\mathcal{C}^{\prime})$ have the same set of $0$-cells, $F$
does not take a value in $[a,b]$ on any $0$-cell of
$\textrm{com.part}(\mathcal{C}^{\prime})$. Because
$\textrm{com.part}(\mathcal{C}^{\prime})$ is a polytopal complex and any
nontransversal threshold for a polytopal complex is attained on a $0$-cell of
that polytopal complex, it follows that all thresholds in $[a,b]$ are
transversal for $F$ with respect to $\textrm{com.part}(\mathcal{C}^{\prime})$.
∎

######  Proposition 5.45.

Let $\mathcal{C}$ be a polyhedral complex in $\mathbb{R}^{n}$ in which all
cells are pointed. Let $F:|\mathcal{C}|\to\mathbb{R}$ be linear on cells of
$\mathcal{C}$. Let $[a,b]$ be an interval of transversal thresholds for $F$ on
$\mathcal{C}$.

Then there exists a polytopal complex $\mathcal{D}$ with
$|\mathcal{D}|\subset|\mathcal{C}|$ and a strong deformation retraction
$\Phi:|\mathcal{C}|\to|\mathcal{D}|$ (that induces a cellular map from
$\mathcal{C}$ to $\mathcal{D}$) such that $\Phi$ is $F$-level preserving on
$|\mathcal{C}_{F\in[a,b]}|$ and for every $c\in[a,b]$,

(11) $\Phi(|\mathcal{C}_{F\leq c}|)=|\mathcal{D}_{F\leq
c}|,\quad\Phi(|\mathcal{C}_{F\geq c}|)=|\mathcal{D}_{F\geq c}|.$

Furthermore, there is an $F$-level preserving PL isotopy

$\phi:|\mathcal{D}|_{F=c}\times[a,b]\to|\mathcal{D}_{F\in[a,b]}|.$

###### Proof.

Let $\mathcal{C}^{\prime}$ be the refinement of $\mathcal{C}$ constructed in
Lemma 5.43; set $\mathcal{D}=\textrm{com.part}(\mathcal{C}^{\prime})$ and
$\Phi=\textrm{base}_{\mathcal{C}^{\prime}}$. Lemma 5.43 implies $\Phi$ has the
stated properties. By Lemma 5.44, $[a,b]$ is an interval of transversal
thresholds for $F$ with respect to the polytopal complex $\mathcal{D}$.
Grunert’s result (Lemma 5.40) then gives, for any $c\in[a,b]$, the $F$-level
preserving PL isotopy $\phi$. ∎

####  5.4.2. The unpointed case

######  Lemma 5.46.

Let $\mathcal{C}$ be a connected polyhedral complex in $\mathbb{R}^{n}$ in
which all cells are unpointed, let $F:|\mathcal{C}|\to\mathbb{R}$ be linear on
the cells of $\mathcal{C}$, and let $[a,b]$ be a closed interval of
transversal thresholds for $F$ on $\mathcal{C}$. Then there exists a
refinement $\mathcal{C}^{\prime}$ of $\mathcal{C}$ such that

  1. (i)

the projection map
$\textrm{proj}:\mathcal{C}^{\prime}\rightarrow\textrm{ess}(\mathcal{C}^{\prime})$
is $F$–level preserving and hence induces a canonical map
$F_{\tiny\textrm{ess}}:\textrm{ess}(\mathcal{C}^{\prime})\rightarrow\mathbb{R}$
which is linear on cells,

  2. (ii)

$[a,b]$ is an interval of transversal thresholds for $F_{\tiny\textrm{ess}}$
with respect to $\textrm{ess}(\mathcal{C}^{\prime})$

We will find the following notation convenient. Let
$c_{1},\ldots,c_{k}\in\mathbb{R}$ be a set of finitely many distinct real
numbers, and let $\mathbb{R}_{c_{1},\ldots,c_{k}}$ be the unique induced
polyhedral decomposition of $\mathbb{R}$ whose $0$–cells are
$c_{1},\ldots,c_{k}$ and whose $1$–cells are the $k+1$ closed intervals in
$\mathbb{R}$ satisfying the condition that they contain at least one $c_{i}$
in their boundary and no $c_{i}$ in their interior. Then for a polyhedral
complex $\mathcal{C}$ in $\mathbb{R}^{n}$ and a map
$F:\mathcal{C}\rightarrow\mathbb{R}$ that is linear on cells, we will denote
by $\mathcal{C}_{c_{1},\ldots,c_{k}}$ the level set complex associated to $F$
and $\mathbb{R}_{c_{1},\ldots,c_{k}}$.

###### Proof.

The Pointedness Dichotomy (Corollary 5.29) tells us that since all cells of
$\mathcal{C}$ are unpointed, $\mbox{rank}(\mathcal{C})<n$.

We begin by noting that since $[a,b]$ is a closed interval of transversal
thresholds, and the set of transversal thresholds is open in $\mathbb{R}$,
there exists some $\epsilon>0$ such that $(a-\epsilon,b+\epsilon)$ is an open
interval of transversal thresholds. Moreover,
$\mbox{rank}(\mathcal{C}_{c})=\mbox{rank}(\mathcal{C}_{c^{\prime}})$ for all
$c,c^{\prime}\in(a-\epsilon,b+\epsilon)$.

The complex $\mathcal{C}^{\prime}$ can now be constructed from $\mathcal{C}$
by taking finitely many refinements as follows. If there exists
$c_{1}\in\mathbb{R}$ for which
$\mbox{rank}(\mathcal{C}_{c_{1}})>\mbox{rank}(\mathcal{C})$, then there exists
a threshold $c_{1}^{\prime}\in(\mathbb{R}\setminus[a,b])$ for which

$\mbox{rank}(\mathcal{C}_{c_{1}^{\prime}})=\mbox{rank}(\mathcal{C}_{c_{1}})>\mbox{rank}(\mathcal{C}).$

If $\mbox{rank}(\mathcal{C}_{c_{1}^{\prime}})=n,$ then the Pointedness
Dichotomy tells us that
$\mathcal{C}_{c_{1}^{\prime}}=\textrm{ess}(\mathcal{C}^{\prime})$, and hence
the induced map on
$\mathcal{C}^{\prime}:=\mathcal{C}_{c_{1}^{\prime}}=\textrm{ess}(\mathcal{C}^{\prime})$
is trivially $F$–level preserving. Since, by construction, we have introduced
no new cells mapping into the interval $[a,b]$, it remains an interval of
transversal thresholds.

If $\mbox{rank}(\mathcal{C}_{c_{1}^{\prime}})<n$, repeat the process in the
paragraph above until we have found
$c_{1}^{\prime},\ldots,c_{k}^{\prime}\in(\mathbb{R}\setminus[a,b])$ for which
$\mathcal{C}_{c_{1}^{\prime},\ldots,c_{k}^{\prime}}$ has rank $m\leq n$ and
there exists no $d\in\mathbb{R}$ for which
$\mbox{rank}(\mathcal{C}_{c_{1}^{\prime},\ldots,c_{k}^{\prime},d})>m$. Note
that since each step in the process increases rank, we know that
$k\leq(n-\mbox{rank}(\mathcal{C}))$ is finite.

We now claim that the finite refinement
$\mathcal{C}^{\prime}:=\mathcal{C}_{c_{1}^{\prime},\ldots,c_{k}^{\prime}}$
satisfies the required conditions. If $m=n$, the argument is as above. If
$m<n$, then
$\mbox{rank}(\mathcal{C}^{\prime}_{d})=\mbox{rank}(\mathcal{C}^{\prime})$ for
every $d\in\mathbb{R}$. But this implies that every level set of $F$ is
invariant under translation by vectors in
$\mbox{lin.space}(\mathcal{C}^{\prime})$, and hence the projection map
$proj:\mathcal{C}^{\prime}\rightarrow\textrm{ess}(\mathcal{C}^{\prime})$ is
$F$–level preserving. Since  $proj$ is bijective and $F$–level preserving on
cells, the interval $[a,b]$ remains an interval of transversal thresholds for
$F_{\textrm{ess}}:\textrm{ess}(\mathcal{C}^{\prime})\rightarrow\mathbb{R}$. ∎

We are now ready to prove Theorems 3 and 4, which we restate below for
convenience.

######  Theorem 3.

Let $\mathcal{C}$ be a polyhedral complex in $\mathbb{R}^{n}$, let
$F:|\mathcal{C}|\to\mathbb{R}$ be linear on cells of $\mathcal{C}$, and let
$[a,b]$ be an interval of transversal thresholds for $F$ on $\mathcal{C}$.
Then there exists a polytopal complex $\mathcal{D}$ with
$|\mathcal{D}|\subset|\mathcal{C}|$ and a strong deformation retraction
$\Phi:|\mathcal{C}|\to|\mathcal{D}|$ (which induces a cellular map
$\mathcal{C}\to\mathcal{D}$) such that $\Phi$ is $F$-level preserving on
$|\mathcal{C}_{F\in[a,b]}|$ and for every $c\in[a,b]$,

(12) $\Phi(|\mathcal{C}_{F\leq c}|)=|\mathcal{D}_{F\leq
c}|,\quad\Phi(|\mathcal{C}_{F\geq c}|)=|\mathcal{D}_{F\geq c}|.$

Furthermore, there is an $F$-level preserving PL isotopy

$\phi:|\mathcal{D}|_{F=c}\times[a,b]\to|\mathcal{D}_{F\in[a,b]}|.$

###### Proof.

It suffices to prove the result for each connected component of $\mathcal{C}$.
Thus, without loss of generality, assume $\mathcal{C}$ is connected. If
$\mathcal{C}$ is pointed, the result is Proposition 5.45. If $\mathcal{C}$ is
unpointed, Lemma 5.46 yields that the projection map proj is a strong
deformation retraction that is $F$-level preserving from $\mathcal{C}$ to the
pointed polyhedral complex
$\mathcal{D}\coloneqq\textrm{ess}(\mathcal{C}^{\prime})$; it furthermore
guarantees that $[a,b]$ is an interval of transversal thresholds for $F$ with
respect to $\mathcal{D}=\textrm{ess}(\mathcal{C}^{\prime})$. We may therefore
apply Proposition 5.45 to the action of $F$ on
$\textrm{ess}(\mathcal{C}^{\prime})$; let $\Phi$ be the composition of proj
and the strong deformation retraction guaranteed by Proposition 5.45. ∎

######  Theorem 4.

Let $\mathcal{C}$ be a polyhedral complex in $\mathbb{R}^{n}$, let
$F:|\mathcal{C}|\to\mathbb{R}$ be linear on cells of $\mathcal{C}$, and let
$[a,b]$ be an interval of transversal thresholds for $F$ on $\mathcal{C}$.
Then for any threshold $c\in[a,b]$, $|\mathcal{C}_{F\leq c}|$ is homotopy
equivalent to $|\mathcal{C}_{F\leq a}|$; also $|\mathcal{C}_{F\geq c}|$ is
homotopy equivalent to $|\mathcal{C}_{F\geq b}|$.

###### Proof.

By Theorem 3, $|\mathcal{C}_{F\leq c}|$ is homotopy equivalent to
$|\mathcal{D}_{F\leq c}|$ and $|\mathcal{C}_{F\leq a}|$ is homotopy equivalent
to $|\mathcal{C}_{F\leq a}|$, where $\mathcal{D}$ is as constructed in that
theorem. It furthermore gives that $|\mathcal{D}_{F\leq c}|$ is homotopy
equivalent to $|\mathcal{D}_{F\leq a}|$. Since homotopy equivalence is a
transitive relation, this implies $|\mathcal{C}_{F\leq c}|$ is homotopy
equivalent to $|\mathcal{C}_{F\leq a}|$. The proof for the superlevel sets is
the same.

∎

##  6\. Morse classification of points for shallow neural network functions

The purpose of this section is to give a purely combinatorial characterization
of regular and critical points of depth $2$ generic, transversal neural
network functions. We begin by establishing some terminology and notation.

Recall (cf. [11, Sec. 1]) that if $A,B\subseteq\mathbb{R}^{n}$ are subsets,
their join $AB$ in $\mathbb{R}^{n}$ is the set of points of the form
$\\{\lambda a+\mu b\,\,|\,\,a\in A,b\in B,\lambda,\mu\geq 0,\lambda+\mu=1\\}$.
If $A=\\{a\\}$ is a single point, then the join of $a$ with a subset $B$ is
said to be a cone $aB$ with vertex $a$ and base $B$ if every point in the join
has a unique expression as $\lambda a+\mu b$. A star of a point, $p$, in
$\mathbb{R}^{n}$ (equipped with the standard PL structure) is a closed cone
neighborhood of $p$ with compact non-empty base, $B$. If $pB$ is a star of
$p$, then $B$ is said to be a link of $p$.

It is well-known (cf. [11, Lem. 2.1]) that all stars (resp., all links) of a
fixed point $p$ in $\mathbb{R}^{n}$ (equipped with the standard PL structure)
are PL homeomorphic. A standard choice for a star neighborhood of a point $p$
is the unit ball centered at $p$ with respect to the $L^{1}$ norm:

$N^{\tiny std}(p):=\left\\{{\bf
x}\in\mathbb{R}^{n}\,\,:\,\,\sum_{i=1}^{n}|x_{i}-p_{i}|=1\right\\}.$

The star (resp., link) of a point $p$ in a PL manifold is a closed
neighborhood of $p$ whose image under a compatible coordinate chart is a star
(resp. link) in $\mathbb{R}^{n}$.

Let ${\bf e}_{i}$ be the $i$th standard unit coordinate vector in
$\mathbb{R}^{n}$, and let $H_{i}^{\tiny std}$ be its associated normal
coordinate hyperplane in $\mathbb{R}^{n}$, defined by

$H_{i}^{\tiny std}:=\\{{\bf x}\in\mathbb{R}^{n}\,\,|\,\,{\bf e}_{i}\cdot{\bf
x}=0\\}.$

Let $\mathcal{C}^{\tiny std}$ denote the polyhedral complex associated to the
hyperplane arrangement $\mathcal{A}^{\tiny std}=\left\\{H_{i}^{\tiny
std}\right\\}_{i=1}^{n}.$ The $k$–cells of $\mathcal{C}^{\tiny std}$ have the
following convenient description:

######  Lemma 6.1.

There is a one-to-one correspondence between $k$–cells of $\mathcal{C}^{\tiny
std}$ and pairs $(S,\eta)$, where $S$ is a $k$–element subset of
$[n]:=\\{1,\ldots,n\\}$ and $\eta\in\\{+,-\\}^{n-k}$. Explicitly, the domain
of the unique $k$–cell $C_{S}^{\eta}$ associated to $(S,\eta)$ is:

$\left(\bigcap_{i\not\in S}H_{i}^{\tiny std}\right)\cap\left(\bigcap_{j\in
S}\left(H_{j}^{\tiny std}\right)^{\eta_{j}}\right).$

Moreover, a cell $C_{S}^{\eta}$ is a face of $C_{S^{\prime}}^{\eta^{\prime}}$
in $\mathcal{C}^{std}$ if and only if $S\supseteq S^{\prime}$ and
$\eta^{\prime}_{j}|_{j\in([n]\setminus S)}=\eta_{j}$.

###### Proof.

Immediate from the definitions. ∎

A star complex (resp., link complex) is a polytopal complex whose domain is
the star (resp., link) of some point. Let

$\mbox{St}^{\tiny std}({\bf 0}):=\mathcal{C}^{\tiny std}\cap N^{\tiny
std}({\bf 0})$

denote the star complex of ${\bf 0}$ formed as the intersection complex of
$\mathcal{C}^{std}$ with $N^{\tiny std}({\bf 0})$, the unit $L^{1}$ norm ball
centered at ${\bf 0}$.

######  Remark 6.2.

The set of $1$–cells of $\mbox{St}^{std}({\bf 0})$ contains the unit intervals
along the positive and negative coordinate axes. Applying the notation

$\hat{i}:=\\{1,\ldots,n\\}\setminus\\{i\\}$

to the notation developed in Lemma 6.1, we will refer to the the unit interval
along the positive (resp., negative) $i$th coordinate axis using the notation
$C_{\hat{i}}^{+}$ (resp., $C_{\hat{i}}^{-}$).

We will also need the following standard method of sudividing polytopal
complexes.

######  Definition 6.3.

[6, Defn. 1.21] (elementary starring) Let $K$ be a polytopal complex, and let
p be a point in its domain, $|K|$. The elementary starring of $K$ at $p$ is
produced by remove all cells containing $p$ from $K$ and adding, for each cell
$S$ that is a face of a removed cell but not removed itself, the cell $pS$. In
other words, we replace the star of $p$ by the cone on its link with apex $p$.

######  Definition 6.4.

[6, Defn. 1.22] (stellar subdivision) A stellar subdivision of a polytopal
complex $K$ is any subdivision that is obtained by a sequence of elementary
starrings starting from K.

With all of the above understood, let
$F:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}\rightarrow\mathbb{R}$ be a generic,
transversal, depth $2$ ReLU neural network map with $m\geq n$. In this case
the polyhedral complex $\mathcal{C}(F)$ is just $\mathcal{C}(\mathcal{A})$ for
the generic arrangement $\mathcal{A}=\\{H_{1},\ldots,H_{m}\\}$ of $m$
hyperplanes in $\mathbb{R}^{n}$ associated to the first layer map.

The following lemma gives us a standard local model for neighborhoods of
$0$–cells in the canonical polyhedral complex associated to a shallow ReLU
neural network function.

######  Lemma 6.5.

Let $F:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}\rightarrow\mathbb{R}$ be a
depth $2$ generic, transversal ReLU neural network function with $m\geq n$.
For every $0$–cell $p\in\mathcal{C}(F)$ there exists a subdivision
$\mathcal{C}^{\prime}$ of $\mathcal{C}(F)$ with respect to which there is a
combinatorial equivalence $\phi:\mbox{St}^{\tiny std}({\bf
0})\rightarrow\mbox{St}(p)$.

###### Proof.

To construct a subdivision of $\mathcal{C}(F)$ with respect to which
$\mbox{St}(p)$ is combinatorially-equivalent to $\mbox{St}^{\tiny std}({\bf
0})$, we proceed as follows. Since $\mathcal{C}(F)=\mathcal{C}(\mathcal{A})$,
the $0$–cells of $\mathcal{C}(F)$ are precisely the $0$–flats of
$\mathcal{A}$, and since $\mathcal{A}$ is generic the latter are in one-to-one
correspondence with $n$–element subsets of $[m]=\\{1,\ldots,m\\}$. Now suppose
$v=\bigcap_{i\in S}H_{i}$ for an $n$–element subset $S\subset[m]$, and let
$\mathcal{A}_{S}=\\{H_{j}\,\,|\,\,j\in S\\}\subset\mathcal{A}$ be the
associated sub-arrangement of $\mathcal{A}$.

Since $\mathcal{A}_{S}$ is generic, we can find an affine-linear isomorphism
(cf. [4]) $\varphi:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ taking ${\bf 0}$
to $v$ and $\mathcal{A}^{\tiny std}$ to $\mathcal{A}_{S}$, which induces a
combinatorial equivalence $\phi:\mathcal{C}^{\tiny
std}\rightarrow\mathcal{C}(\mathcal{A}_{S})$. By contracting $\varphi$ if
necessary, we additionally ensure that the only $0$–cell of
$\mathcal{C}(\mathcal{A})$ contained in $\varphi(N^{\tiny std}({\bf 0}))$ is
$v$.

It is then straightforward to see that the star of $v$ in the subdivision
$\mathcal{C}^{\prime}$ obtained as the intersection complex
$\mathcal{C}(\mathcal{A})\cap\varphi(N^{\tiny std}({\bf 0}))$ is
combinatorially equivalent to $\mbox{St}^{\tiny std}({\bf 0})$, since
$\mbox{St}(p)$ in $\mathcal{C}(\mathcal{A})\cap\varphi(N^{\tiny std}({\bf
0}))$ is combinatorially equivalent to $\mbox{St}(p)$ in
$\mathcal{C}(\mathcal{A}_{S})\cap\varphi(N^{\tiny std}({\bf 0}))$. The latter
intersection complex is combinatorially equivalent to $\mathcal{C}^{\tiny
std}\cap N^{\tiny std}({\bf 0})$, with the equivalence $\phi$ on cells induced
by the affine-linear isomorphism $\varphi$. ∎

We are now ready to state the following combinatorial characterization of PL
regular, PL nondegenerate-critical and PL degenerate-critical points of $F$
for a generic, transversal depth $2$ ReLU neural network function in terms of
the polyhedral complex $\mathcal{C}(F)$ and the $\nabla F$ partial orientation
on the $1$–skeleton. See Subsection 2.2 for the definition of the $\nabla
F$–orientation.

######  Proposition 6.6.

Let $F:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}\rightarrow\mathbb{R}$ be a
depth $2$ generic, transversal ReLU neural network function ($m\geq n$) with
associated polyhedral complex $\mathcal{C}(F)$. We can classify points in the
domain as PL regular, PL nondegenerate-critical, or PL degenerate-critical as
follows. If $p$ is in the interior of a non-flat (resp., flat) cell of
$\mathcal{C}(F)$ of dimension $\geq 1$, then $p$ is PL regular (resp., PL
degenerate-critical).

Otherwise, $p$ is a $0$–cell of $\mathcal{C}(F)$, and with respect to the
combinatorial equivalence described in Lemma 6.5 we have the following
complete and mutually exclusive list of possibilities:

  * •

$p$ is PL regular if and only if there is at least one pair,
$\phi(C_{\hat{i}}^{\pm})$, of $1$–dimensional cofaces of $p$ for which
$\phi(C_{\hat{i}}^{+})$ is pointing toward and $\phi(C_{\hat{i}}^{-})$ is
pointing away from $p$ (or vice versa).

  * •

$p$ is PL nondegenerate-critical if and only if the $\nabla F$ orientations on
each pair, $\phi(C_{\hat{i}}^{\pm})$, are either both pointing toward or both
pointing away from $p$. Moreover, the index of $p$ is equal to the number of
pairs, $\phi(C_{\hat{i}}^{\pm})$, whose $\nabla F$ orientations point toward
$p$.

  * •

$p$ is PL degenerate-critical if and only if there is at least one flat
$1$–dimensional co-face of $p$

Figure 7. Left: A regular vertex of a depth $2$ neural network function
$\mathbb{R}^{2}\to\mathbb{R}$ has at least one pair of matched $1$–dimensional
cofaces, $\phi(C_{\hat{i}}^{\pm})$, for which the $\nabla F$ orientation
points in the same direction. Right: A nondegenerate critical vertex has the
property that orientations on all pairs of matched $1$–dimensional cofaces,
$\phi(C_{\hat{i}}^{\pm})$, change direction across the vertex. In the above
example, the vertex is nondegenerate critical of index $1$ since one pair of
matched arrows points towards the vertex.

###### Proof.

By the argument given in the proof of Theorem 2 (see also Lemma 3.16), if $p$
is in the interior of a non-flat (resp., flat) cell of dimension $k\geq 1$,
then $p$ is PL regular (resp., PL degenerate-critical).

So we need only justify the claim about the classification of $0$–cells in
terms of the $\nabla F$ orientations of $1$–dimensional co-faces.

To this end, recall that Grunert defines regular and nondegenerate critical
points using the notion of local equivalence ([6, Defn. 3.1]) of triples
$(M,x,f)$, where $M$ is a (finite) polyhedral complex, $x$ is a point in
$|M|$, and $f:|M|\rightarrow\mathbb{R}$ is a map affine-linear on cells. Two
triples $(M,x,f)$ and $(M^{\prime},x^{\prime},f^{\prime})$ are said to be
locally equivalent if there exist neighborhoods $N_{x}$ and $N_{x^{\prime}}$
and a PL homeomorphism $\varphi:N_{x}\rightarrow N_{x^{\prime}}$ mapping $x$
to $x^{\prime}$ and satisfying the property that $(f\circ\varphi)$ and
$f^{\prime}$ differ by a constant. A point $x$ is then said to be regular
(resp., nondegenerate critical of index $k$) for $f$ if $(M,x,f)$ is locally-
equivalent to $\mbox{(}\mathcal{C}^{\tiny std},{\bf 0},g)$, for $g=x_{n}$
(resp., $g=-\sum_{i=1}^{k}|x_{i}|+\sum_{j=k+1}^{n}|x_{j}|$). Grunert’s
definition agrees with the definition in [7] when $|M|$ is a PL manifold.

Grunert goes on to prove, in [6, Thm. 3.11], that the following statements are
equivalent:

  * •

$(M,x,f)$ and $(M^{\prime},x^{\prime},f^{\prime})$ are locally equivalent;

  * •

There are combinatorially-equivalent link complexes for $x$ and $x^{\prime}$
contained in the stars of $x$ and $x^{\prime}$ such that $f-f(x)$ and
$f^{\prime}-f^{\prime}(x^{\prime})$ are linear on cells and have the same
signs at the corresponding vertices;

  * •

Any pair of link complexes for $x$ and $x^{\prime}$ that are contained in the
stars of $x$ and $x^{\prime}$ has combinatorially equivalent subdivisions such
that $f-f(x)$ and $f^{\prime}-f^{\prime}(x^{\prime})$ have the same sign at
corresponding vertices.

With the above understood, we are ready to classify the $0$–cells of
$\mathcal{C}(F)$.

Let $p$ be a $0$–cell. We constructed a combinatorial equivalence in Lemma 6.5
between the star complex $\mbox{St}^{\tiny std}({\bf 0})$ and the star complex
$\mbox{St}(p)$ in the intersection complex
$\mathcal{C}(\mathcal{A})\cap\varphi(N^{\tiny std}({\bf 0}))$. The boundary
link complexes $\mbox{lk}({\bf 0})$ and $\mbox{lk}(p)$ are therefore also
combinatorially equivalent.

If a $1$–dimensional coface of $p$ in $\mbox{St}(p)$ is flat, then just as
above, $p$ is PL degenerate critical.

If no $1$–dimensional coface of $p$ in $\mbox{St}(p)$ is flat, then there are
two cases to consider: either the $\nabla F$ orientation changes direction
through $p$ for all pairs, $\phi(C_{\hat{i}}^{\pm})$, or there exists at least
one pair $\phi(C_{\hat{i}}^{\pm})$ for which the direction of the $\nabla F$
orientation is preserved through $p$.

In the first case, by reindexing the $1$–cells of $\mbox{St}^{\tiny std}({\bf
0})$ if necessary so that the $k$ pairs pointing toward $p$ correspond to
$\phi(C_{\hat{1}}^{\pm}),\ldots,\phi(C_{\hat{k}}^{\pm})$, it is immediate that
the signs of $F-F(p)$ and $F_{\tiny crit,k}-F({\bf 0})$ agree on
$\mbox{lk}(p)$ and $\mbox{lk}({\bf 0})$, so $p$ is a nondegenerate critical
point.

In the second case, reindex the $1$–cells of $\mbox{St}^{\tiny std}({\bf 0})$
so that the direction of the $\nabla F$ orientation is preserved through $p$
on the pair, $\phi(C_{\hat{n}}^{\pm})$, corresponding to the coordinate
$x_{n}$ in $\mathcal{C}^{\tiny std}$, switching the roles of
$C_{\hat{n}}^{\pm}$ if necessary so that the signs of $F-F(p)$ on
$\partial(\phi(C_{\hat{n}}^{\pm}))$ agree with $x_{n}$ instead of $-x_{n}$ on
$\partial(C_{\hat{n}}^{\pm})$.

We now claim that we can construct combinatorially equivalent subdivisions of
$\mbox{lk}(p)$ and $\mbox{lk}({\bf 0})$ so that the signs of $F-F(p)$ and
$x_{n}$ agree on the vertices of the subdivision, which will imply that $p$ is
regular. We proceed as follows. For each $i\in\\{1,\ldots,n-1\\}$ consider the
restriction of $\mbox{lk}({\bf 0})$ to the coordinate plane spanned by ${\bf
e}_{i}$ and ${\bf e}_{n}$. This restriction is the standard simplicial complex
whose domain is homeomorphic to $S^{1}$. It has four $0$–cells, which we’ll
label by $p_{i}^{\pm}$ and $p_{n}^{\pm}$ and four $1$–cells connecting
$p_{i}^{+}$ to $p_{n}^{\pm}$ and $p_{i}^{-}$ to $p_{n}^{\pm}$. Working in
ascending order beginning from $i=1$ and doing $``+"$ before $``-"$, add a new
$0$–cell, $r_{i}^{\pm}$, in the interior of the $1$–cell connecting
$p_{i}^{\pm}$ to $p_{n}^{+}$ (resp., connecting $p_{i}^{\pm}$ to $p_{n}^{-}$)
according to whether the $\nabla F$ orientation on $\phi(C_{\hat{i}}^{\pm})$
is oriented away from $p$ (resp., toward $p$) and then perform an elementary
starring on $\mbox{lk}({\bf 0})$ with respect to the newly-added point.

When performing each of the elementary starrings of $\mbox{lk}({\bf 0})$
described above, perform the following elementary starring on $\mbox{lk}(p)$.
If the $\nabla F$ orientation on $\phi(C_{\hat{i}}^{\pm})$ is oriented away
from $p$ (resp., toward $p$) we know that there exists a point $q_{i}^{\pm}$
on the $1$–cell connecting $\phi(p_{i}^{\pm})$ to $\phi(p_{n}^{-})$ (resp., to
$\phi(p_{n}^{+})$) for which the value of $F$ is equal to the value of $F(p)$.
Perform an elementary starring of $\mbox{lk}(p)$ at $q_{i}^{\pm}$.

It is straightforward to check that after each elementary starring of
$\mbox{lk}({\bf 0})$ and corresponding elementary starring of $\mbox{lk}(p)$