Rank-sensitive layer recursion for ReLU regions

An empty current cell has no descendants. Otherwise let $E$ be the affine hull of the current cell's image, with $\dim E=s\le r$, and write the restricted preactivations as $a_1,\dots ,a_{n_{\mathrm{\ell }}}$. There are finitely many realized active subsets $A$; choose one image point $y_A$ for each. Choose $\delta >0$ smaller than every positive number among the $a_i(y_A)$, taking any positive $\delta$ if there are none. At each witness, $a_i(y_A)-\delta$ is strictly positive exactly for $i\in A$ and strictly negative otherwise. Thus every original pattern, including a boundary-only pattern, occurs in a distinct full-dimensional chamber of the shifted affine functions on $E$. Constant restrictions have fixed strict signs and add no hyperplanes. By [F1], there are at most $S={\sum }_{j=0}^{\min (r,n_{\mathrm{\ell }})}\left(\genfrac{}{}{0px}{}{n_{\mathrm{\ell }}}{j}\right)$ such patterns; for $s=0$ there is at most one. For a fixed $A$, the original pattern constraints are affine strict or weak half-spaces on the current cell, so they define at most one convex subcell. By [F2], the layer output there keeps the coordinates in $A$ and sets the others to zero, so its affine image dimension is at most $\min (r,\mathrm{\mid }A\mathrm{\mid })$.

Backward induction in the displayed recurrence shows that $R_{\mathrm{\ell }+1}(s)$ is nondecreasing in $s$: increasing $s$ adds nonnegative terms and does not decrease any argument. Therefore, among at most $S$ distinct active subsets its sum is maximized by choosing the $S$ subsets of largest cardinality. Those can be taken to have sizes $n_{\mathrm{\ell }}-j$ with multiplicities $\left(\genfrac{}{}{0px}{}{n_{\mathrm{\ell }}}{j}\right)$ for $0\le j\le \min (r,n_{\mathrm{\ell }})$; their total number is exactly $S$. The associated next dimensions are at most $\min (r,n_{\mathrm{\ell }}-j)$, giving the displayed recurrence. Induction backward from $R_{L+1}=1$ proves the claim.