\documentclass[11pt]{amsart}
\usepackage[letterpaper, top=1in, bottom=1in, left=1in, right=1in]{geometry}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{mathtools}
\usepackage{enumitem}
\usepackage{microtype}
\usepackage[hidelinks]{hyperref}

% ---------- theorem environments (shared counter) ----------
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{algorithm}[theorem]{Algorithm}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

% ---------- macros ----------
\newcommand{\R}{\mathbb{R}}
\newcommand{\Lap}{\mathcal{L}}
\newcommand{\Lsym}{\mathcal{L}_{\mathrm{sym}}}
\newcommand{\Lrw}{\mathcal{L}_{\mathrm{rw}}}
\newcommand{\one}{\mathbf{1}}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\col}{\operatorname{col}}
\newcommand{\rank}{\operatorname{rank}}
\newcommand{\diag}{\operatorname{diag}}
\newcommand{\Perp}{P_K^{\perp}}
\DeclarePairedDelimiter{\norm}{\lVert}{\rVert}
\DeclarePairedDelimiter{\abs}{\lvert}{\rvert}

\title[Low-Frequency Spectral Alignment in ReLU Networks]{Propagation and Optimization of Low-Frequency Spectral Alignment\\ in ReLU Networks on a Fixed Sample Graph}
\author{Cameron Ryan}
\date{\today}

\begin{document}
\maketitle

\begin{abstract}
We study how low-frequency structure, measured with respect to the Laplacian of a fixed graph built on the training samples, propagates through a ReLU network to the least-squares readout $g$, and how individual neurons $h=S\Phi\theta$ can be optimized to capture low-frequency eigenvectors.
The readout error splits into a low-frequency part controlled by \emph{coverage} (how well the feature span contains the low eigenvectors) and a high-frequency part controlled by the \emph{smoothness} (Dirichlet energy) of the target.
We prove an error bound that makes this precise, with coverage measured by the coverage gap, the largest principal-angle sine between the low eigenvectors and the feature span, and show that coverage can always be preserved across ReLU layers.
Finally, we define a count $N_K$ of captured low-frequency features, relate it to our error bounds, and prove that error can be reduced to a smoothness component when $N_K$ captures every low frequency feature.
Lastly, we show that a ReLU layer can strictly increase $N_K$ whenever the previous layer keeps the samples distinct and coverage is not yet full, that $2K+2$ neurons suffice to preserve coverage, that greedily chosen neurons drive the coverage gap down at rate $O(1/t)$ governed by a ReLU variation norm of the low eigenvectors, and that $t$ neurons can reduce the coverage gap no further than the $(t+1)$-st principal-angle sine.
\end{abstract}

\section{Setting and notation}
\label{sec:setting}

Let $X\in\R^{d\times n}$ be the sample and $f\in\R^n$ the target values. Let $\mathcal G(X)$ be a weighted undirected graph on the $n$ samples with symmetric nonnegative weights $w_{ij}$, degrees $d_i=\sum_j w_{ij}>0$, $D=\diag(d_1,\dots,d_n)$ and $W=(w_{ij})$. We consider the use of Laplacians such as the combinatorial or symmetric normalized:
\[
L=D-W,\qquad \Lsym=D^{-1/2}LD^{-1/2}
\]
see \cite{chung1997,vonluxburg2007}. Their quadratic forms are
\begin{equation}
x^\top Lx=\sum_{i<j}w_{ij}(x_i-x_j)^2,\qquad
x^\top \Lsym x=\sum_{i<j}w_{ij}\Big(\frac{x_i}{\sqrt{d_i}}-\frac{x_j}{\sqrt{d_j}}\Big)^2.
\label{eq:edge}
\end{equation}
Throughout, $\Lap$ denotes either $L$ or $\Lsym$ unless stated otherwise. Write $\Lap=U\Lambda U^\top$ with $U=[u_1,\dots,u_n]$ orthogonal and $0=\lambda_1\le\lambda_2\le\cdots\le\lambda_n$. Let $U_K=[u_1,\dots,u_K]$, $P_K=U_KU_K^\top$ and $\Perp=I-P_K$.

\begin{definition}[Energy and Rayleigh quotient]
\label{def:energy}
The \emph{Dirichlet energy} of $x\in\R^n$ is $E(x)^2=x^\top\Lap x$, and $E(x)=\sqrt{x^\top\Lap x}=\norm{\Lap^{1/2}x}$ is the \emph{Dirichlet energy seminorm}. For $x\ne0$ the \emph{Rayleigh quotient} is
\[
R(x)=\frac{E(x)^2}{\norm{x}^2}=\frac{x^\top\Lap x}{x^\top x}=\frac{\sum_k\lambda_k\hat x_k^2}{\sum_k\hat x_k^2},\qquad \hat x=U^\top x,
\]
the average eigenvalue weighted by the spectral mass of $x$, so that $\lambda_1\le R(x)\le\lambda_n$, with $R(u_k)=\lambda_k$.
\end{definition}

\noindent\textbf{Network.} Let $\sigma(t)=\max(t,0)$ act entrywise. Set $H_0=X^\top\in\R^{n\times d}$ and, for $\ell=1,\dots,p$,
\[
H_\ell=\sigma\big(H_{\ell-1}W_\ell+\one b_\ell^\top\big),\qquad W_\ell\in\R^{m_{\ell-1}\times m_\ell},\ b_\ell\in\R^{m_\ell},\ m_0=d.
\]
The readout features are $Z=[H_p,\one]$, $\beta=Z^+f$, $g=Z\beta=\Pi_Zf$ where $\Pi_Z$ is the orthogonal projector onto $\col(Z)$, and the residual is $r=g-f$.

\noindent\textbf{Single neuron.} For a neuron in layer $\ell$ let $\Phi=[H_{\ell-1},\one]\in\R^{n\times m}$, $\theta\in\R^m$, $z=\Phi\theta$ the pre-activation and
\begin{equation}
S=S(\theta)=\diag\big(\mathbb 1[(\Phi\theta)_i>0]\big),\qquad h=\sigma(z)=S\Phi\theta .
\label{eq:neuron}
\end{equation}
For vectors and matrices, $\abs{\cdot}$ is the entrywise absolute value and inequalities between vectors are entrywise.

\noindent\textbf{Coverage.} For a matrix $Z$ define the \emph{coverage gap}
\[
s_K(Z)=\norm{(I-\Pi_Z)U_K}_2\in[0,1].
\]
When $\rank Z\ge K$, $s_K(Z)$ is the sine of the largest principal angle between $\mathrm{span}(U_K)$ and its closest $K$-dimensional subspace of $\col(Z)$ \cite{bjorckgolub1973,stewartsun1990,golubvanloan2013}.

\section{Preliminaries}

% \begin{lemma}[Energy is a seminorm]
% \label{lem:seminorm}
% $E$ is a seminorm on $\R^n$ with kernel $\ker\Lap$. In particular $E(a+b)\le E(a)+E(b)$ and $E(ca)=\abs{c}E(a)$. The constant vector has energy
% \[
% c_{\one}:=E(\one)=\begin{cases}0,&\Lap=L,\\[2pt] \Big(\sum_{i<j}w_{ij}\big(d_i^{-1/2}-d_j^{-1/2}\big)^2\Big)^{1/2},&\Lap=\Lsym,\end{cases}
% \]
% which is nonzero for $\Lsym$ whenever some edge joins vertices of different degree.
% \end{lemma}
% \begin{proof}
% Since $\Lap\succeq0$, $E(x)=\norm{\Lap^{1/2}x}$ is the composition of a linear map with a norm, hence a seminorm vanishing exactly on $\ker\Lap^{1/2}=\ker\Lap$. The formula for $c_{\one}$ follows from \eqref{eq:edge} with $x=\one$.
% \end{proof}
% 
% \begin{remark}
% Lemma~\ref{lem:seminorm} shows that with $\Lsym$ the bias column of $Z=[H_p,\one]$ is not energy-free; the kernel of $\Lsym$ is spanned by $D^{1/2}\one$ on each connected component. All bounds below therefore carry a $c_{\one}$ term, which vanishes for $L$ and for $\Lrw$ (Remark~\ref{rem:rw}).
% \end{remark}

\begin{lemma}[High-frequency mass]
\label{lem:highfreq}
If $\lambda_{K+1}>0$ then for every $x\in\R^n$, $\norm{\Perp x}^2\le x^\top\Lap x/\lambda_{K+1}$.
\end{lemma}
\begin{proof}
With $\hat x=U^\top x$, Parseval gives $\norm{\Perp x}^2=\sum_{k>K}\hat x_k^2\le\lambda_{K+1}^{-1}\sum_{k>K}\lambda_k\hat x_k^2\le\lambda_{K+1}^{-1}\sum_k\lambda_k\hat x_k^2=x^\top\Lap x/\lambda_{K+1}$.
\end{proof}

% \begin{lemma}[Laplacian loss bounds]
% \label{lem:loss}
% If $\lambda_{K+1}>0$,
% \[
% \norm{P_Kr}^2\le\norm{g-f}^2\le\norm{P_Kr}^2+\frac{2\big(E(g)^2+E(f)^2\big)}{\lambda_{K+1}}.
% \]
% \end{lemma}
% \begin{proof}
% By Pythagoras $\norm{r}^2=\norm{P_Kr}^2+\norm{\Perp r}^2$, which gives the lower bound. By Lemma~\ref{lem:highfreq}, $\norm{\Perp r}^2\le E(r)^2/\lambda_{K+1}$, and by Lemma~\ref{lem:seminorm}, $E(r)^2\le(E(g)+E(f))^2\le2E(g)^2+2E(f)^2$.
% \end{proof}

% \section{Smoothness propagates through ReLU layers}
% \label{sec:smoothness}
% 
% \begin{lemma}[ReLU does not increase graph energy]
% \label{lem:contraction}
% Let $\varphi:\R\to\R$ be $1$-Lipschitz and $h=\varphi(z)$ entrywise. Then $h^\top Lh\le z^\top Lz$. If in addition $\varphi$ is positively homogeneous, i.e.\ $\varphi(ct)=c\varphi(t)$ for $c>0$, then also $h^\top\Lsym h\le z^\top\Lsym z$. In particular, for a ReLU neuron \eqref{eq:neuron} and $\Lap\in\{L,\Lsym\}$,
% \[
% h^\top\Lap h\;\le\;z^\top\Lap z\;=\;\theta^\top\big(\Phi^\top\Lap\Phi\big)\theta .
% \]
% \end{lemma}
% \begin{proof}
% For $L$, by \eqref{eq:edge} it suffices to compare edge terms: $(h_i-h_j)^2=(\varphi(z_i)-\varphi(z_j))^2\le(z_i-z_j)^2$. For $\Lsym$, set $y=D^{-1/2}z$. Positive homogeneity gives $\varphi(z_i)/\sqrt{d_i}=\varphi(z_i/\sqrt{d_i})=\varphi(y_i)$, so $D^{-1/2}h=\varphi(y)$, and by \eqref{eq:edge}, $h^\top\Lsym h=\varphi(y)^\top L\varphi(y)\le y^\top Ly=z^\top\Lsym z$ by the first case. ReLU is $1$-Lipschitz and positively homogeneous.
% \end{proof}
% 
% \begin{remark}[Not a matrix inequality]
% Lemma~\ref{lem:contraction} does \emph{not} say $S\Lap S\preceq\Lap$ for a fixed gating matrix $S$; it uses that $S$ is the sign pattern of $\Phi\theta$ itself. For example, on two vertices joined by an edge of unit weight, $S=\diag(1,0)$ and $x=(1,1)^\top$ give $(Sx)^\top L(Sx)=1>0=x^\top Lx$; here $S$ is not the sign pattern of $x$.
% \end{remark}
% 
% \begin{proposition}[Exact energy removed by ReLU]
% \label{prop:exactloss}
% For $z\in\R^n$ and $h=\sigma(z)$,
% \[
% z^\top Lz-h^\top Lh=\sum_{\substack{i<j\\ z_i\le0,\ z_j\le0}}w_{ij}(z_i-z_j)^2\;+\;\sum_{\substack{i<j\\ z_a>0\ge z_b,\ \{a,b\}=\{i,j\}}}w_{ij}\,\abs{z_b}\big(\abs{z_b}+2z_a\big)\;\ge\;0 .
% \]
% The same identity holds for $\Lsym$ after replacing $z$ by $D^{-1/2}z$.
% \end{proposition}
% \begin{proof}
% Split the edges by the signs of their endpoints. If both endpoints are active, the edge terms of $z$ and $h$ coincide. If both are inactive, the $h$-term is $0$, so the full $z$-term $(z_i-z_j)^2$ is removed. If $z_a>0\ge z_b$, the $h$-term is $z_a^2$ and the removed energy is $(z_a-z_b)^2-z_a^2=z_b^2-2z_az_b=\abs{z_b}(\abs{z_b}+2z_a)\ge0$, using $z_b=-\abs{z_b}$. For $\Lsym$, apply the argument to $y=D^{-1/2}z$, using $D^{-1/2}h=\sigma(y)$ as in Lemma~\ref{lem:contraction}.
% \end{proof}
% 
% In words, ReLU deletes all energy on edges inside the inactive set and part of the energy on boundary edges, and nothing elsewhere.
% 
% \begin{corollary}[Energy propagation through depth]
% \label{cor:depth}
% Let $e_\ell\in\R^{m_\ell}$ collect the neuron energies $(e_\ell)_j=E(H_\ell e_j)$, and let $(e_0)_k=E(x_k)$, where $x_k\in\R^n$ is the $k$-th input coordinate (the $k$-th row of $X$). Then for $\Lap\in\{L,\Lsym\}$,
% \[
% e_\ell\le\abs{W_\ell}^\top e_{\ell-1}+c_{\one}\abs{b_\ell},\qquad
% E(g)\le\abs{\beta_{1:m_p}}^\top e_p+c_{\one}\abs{\beta_0},
% \]
% and therefore
% \[
% E(g)\le\abs{\beta_{1:m_p}}^\top\Big(\abs{W_p}^\top\cdots\abs{W_1}^\top e_0+c_{\one}\sum_{\ell=1}^{p}\abs{W_p}^\top\cdots\abs{W_{\ell+1}}^\top\abs{b_\ell}\Big)+c_{\one}\abs{\beta_0}.
% \]
% For $\Lap=L$ (so $c_{\one}=0$) this reduces to $E(g)\le\abs{\beta_{1:m_p}}^\top\abs{W_p}^\top\cdots\abs{W_1}^\top e_0$.
% \end{corollary}
% \begin{proof}
% The $j$-th pre-activation of layer $\ell$ is $z=\sum_kW_{\ell,kj}H_{\ell-1}e_k+b_{\ell,j}\one$. By Lemma~\ref{lem:contraction} and Lemma~\ref{lem:seminorm},
% $E(H_\ell e_j)\le E(z)\le\sum_k\abs{W_{\ell,kj}}E(H_{\ell-1}e_k)+\abs{b_{\ell,j}}c_{\one}$. The same triangle inequality applied to $g=H_p\beta_{1:m_p}+\beta_0\one$ gives the bound on $E(g)$. Since $\abs{W_\ell}^\top$ has nonnegative entries it preserves entrywise inequalities, and induction on $\ell$ yields the unrolled bound.
% \end{proof}
% 
% Combining Corollary~\ref{cor:depth} with Lemma~\ref{lem:loss}: low-energy inputs and moderate weights force low $E(g)$, and hence small high-frequency loss. The nonlinearity never adds energy; all growth comes from the weights and readout coefficients.
% 
% \begin{remark}[Large readout coefficients]
% \label{rem:ridge}
% If $Z$ is ill-conditioned, least-squares cancellation can make $\abs{\beta}$ large. Two remedies:
% (i) A conditioning-free bound: since $g\in\col(Z)$, $E(g)^2\le\mu_{\max}(Z)\norm{\Pi_Zf}^2\le\mu_{\max}(Z)\norm{f}^2$, where $\mu_{\max}(Z)$ is the largest eigenvalue of $Q_Z^\top\Lap Q_Z$ for an orthonormal basis $Q_Z$ of $\col(Z)$ (equivalently the largest generalized eigenvalue of $(Z^\top\Lap Z,Z^\top Z)$ when $Z$ has full column rank). This is pessimistic if $\col(Z)$ contains any rough direction, even one unused by $f$.
% (ii) Ridge regression \cite{hoerlkennard1970}: $\beta_\gamma=(Z^\top Z+\gamma I)^{-1}Z^\top f$ satisfies $\norm{\beta_\gamma}_2\le\norm{f}/(2\sqrt\gamma)$, because each singular value $\varsigma$ of $Z$ contributes the factor $\varsigma/(\varsigma^2+\gamma)\le1/(2\sqrt\gamma)$. Then by Cauchy--Schwarz the readout term in Corollary~\ref{cor:depth} is at most $\norm{f}\,\norm{(e_p,c_{\one})}_2/(2\sqrt\gamma)$, for the ridge fit $g_\gamma=Z\beta_\gamma$.
% \end{remark}
% 
% \begin{proposition}[Relative alignment can degrade, but by a controlled factor]
% \label{prop:relative}
% Let $h=\sigma(z)\ne0$ and $\rho=\norm{h}^2/\norm{z}^2=\norm{Sz}^2/\norm{z}^2\in(0,1]$. Then
% \[
% R(h)\le R(z)/\rho,\qquad \norm{\Perp h}^2\le E(z)^2/\lambda_{K+1}\ \ (\lambda_{K+1}>0).
% \]
% \end{proposition}
% \begin{proof}
% $R(h)=E(h)^2/\norm{h}^2\le E(z)^2/(\rho\norm{z}^2)=R(z)/\rho$ by Lemma~\ref{lem:contraction}. The second bound is Lemma~\ref{lem:highfreq} applied to $h$ followed by Lemma~\ref{lem:contraction}.
% \end{proof}
% 
% \begin{example}
% On the path $1-2-3$ with unit weights and $\Lap=L$, take $z=(-1,-1,0.1)^\top$. Then $R(z)=1.21/2.01\approx0.60$, while $h=(0,0,0.1)^\top$ has $R(h)=0.01/0.01=1$. The absolute energy dropped from $1.21$ to $0.01$, but the relative alignment worsened, because the active part carries only $\rho\approx0.005$ of the mass. A mostly-dead neuron can be smooth in absolute terms yet poorly aligned relative to its own size.
% \end{example}

\section{Coverage of the low frequencies}
\label{sec:coverage}

The least-squares error splits into a low-frequency part, controlled by how well $\col(Z)$ contains $\mathrm{span}(U_K)$ as measured by the coverage gap $s_K(Z)$, and a high-frequency part, controlled by the smoothness of $f$.

% \begin{proposition}[Coverage bound]
% \label{prop:coverage}
% Let $s=s_K(Z)$. Then $\norm{P_Kr}\le s\norm{r}$. If $s<1$, then
% \[
% \norm{P_Kr}\le\frac{s}{\sqrt{1-s^2}}\norm{\Perp r},\qquad
% \norm{g-f}^2\le\frac{\norm{\Perp r}^2}{1-s^2}\le\frac{r^\top\Lap r}{(1-s^2)\lambda_{K+1}}\le\frac{2\big(E(g)^2+E(f)^2\big)}{(1-s^2)\lambda_{K+1}} ,
% \]
% the last two inequalities requiring $\lambda_{K+1}>0$. In particular, if $\mathrm{span}(U_K)\subseteq\col(Z)$ then $P_Kr=0$. If $\rank Z<K$ then $s=1$.
% \end{proposition}
% \begin{proof}
% Since $r=-(I-\Pi_Z)f$, we have $(I-\Pi_Z)r=r$. Hence
% \[
% \norm{P_Kr}=\norm{U_K^\top r}=\norm{U_K^\top(I-\Pi_Z)r}\le\norm{U_K^\top(I-\Pi_Z)}_2\norm{r}=s\norm{r}.
% \]
% By Pythagoras, $\norm{r}^2=\norm{P_Kr}^2+\norm{\Perp r}^2\le s^2\norm{r}^2+\norm{\Perp r}^2$, so $(1-s^2)\norm{r}^2\le\norm{\Perp r}^2$, and then $\norm{P_Kr}^2\le s^2\norm{r}^2\le\frac{s^2}{1-s^2}\norm{\Perp r}^2$. The remaining inequalities follow from Lemma~\ref{lem:highfreq} and the triangle inequality as in Lemma~\ref{lem:loss}. If $\rank Z<K$, some unit vector in $\mathrm{span}(U_K)$ is orthogonal to $\col(Z)$, so $s=1$.
% \end{proof}

\begin{corollary}[Target-only coverage bound]
\label{cor:targetonly}
Let $s=s_K(Z)$. Then
\[
\norm{g-f}\le s\norm{P_Kf}+\norm{\Perp f}\le s\norm{f}+\frac{E(f)}{\sqrt{\lambda_{K+1}}},
\]
the last inequality requiring $\lambda_{K+1}>0$.
\end{corollary}
\begin{proof}
Since $r=-(I-\Pi_Z)f$ and $f=P_Kf+\Perp f$, the triangle inequality gives $\norm{r}\le\norm{(I-\Pi_Z)U_KU_K^\top f}+\norm{(I-\Pi_Z)\Perp f}\le s\norm{U_K^\top f}+\norm{\Perp f}$, and $\norm{U_K^\top f}=\norm{P_Kf}$. The second inequality uses $\norm{P_Kf}\le\norm{f}$ and Lemma~\ref{lem:highfreq}.
\end{proof}

\begin{lemma}[Monotonicity of the coverage gap]
\label{lem:monotone}
If $\col(A)\subseteq\col(B)$ then $s_K(B)\le s_K(A)$.
\end{lemma}
\begin{proof}
$\Pi_B\Pi_A=\Pi_A$, so $(I-\Pi_B)=(I-\Pi_B)(I-\Pi_A)$ and $\norm{(I-\Pi_B)U_K}_2\le\norm{I-\Pi_B}_2\norm{(I-\Pi_A)U_K}_2\le s_K(A)$.
\end{proof}

\begin{proposition}[Coverage can always be preserved across ReLU layers]
\label{prop:preserve}
\leavevmode
\begin{enumerate}[label=(\alph*)]
\item For every $z\in\R^n$, $z=\sigma(z)-\sigma(-z)$; hence $z\in\mathrm{span}\{\sigma(z),\sigma(-z)\}$.
\item For $\ell\ge2$, the entries of $H_{\ell-1}$ are nonnegative, so a layer containing the $m_{\ell-1}$ neurons with weights $e_k$ and zero bias reproduces $H_{\ell-1}$ exactly, and $\col([H_\ell,\one])\supseteq\col([H_{\ell-1},\one])$.
\item For $\ell=1$, a layer containing the $2d$ neurons with weights $\pm e_k$ and zero bias satisfies $\col([H_1,\one])\supseteq\col([X^\top,\one])$.
\end{enumerate}
Consequently, if $m_1\ge2d$ and $m_\ell\ge m_{\ell-1}$ for $\ell\ge2$, there exist weights for which $s_K([H_\ell,\one])$ is nonincreasing in $\ell$, with the remaining neurons free to add coverage (Section~\ref{sec:increase} shows when and how fast they do).
\end{proposition}
\begin{proof}
(a) holds entrywise: $\max(t,0)-\max(-t,0)=t$. (b) $\sigma(H_{\ell-1}e_k)=H_{\ell-1}e_k$ since $H_{\ell-1}\ge0$. (c) By (a), $X^\top e_k=\sigma(X^\top e_k)-\sigma(-X^\top e_k)$ lies in $\col(H_1)$. The consequence follows from Lemma~\ref{lem:monotone}.
\end{proof}

\begin{definition}[Captured low-frequency features]
\label{def:NK}
For $H\in\R^{n\times N}$ with orthonormal basis $Q_H$ of $\col(H)$, define
\[
N_K(H)=\tr(\Pi_HP_K)=\norm{U_K^\top Q_H}_F^2 .
\]
\end{definition}

\begin{lemma}[Properties of $N_K$]
\label{lem:NK}
\leavevmode
\begin{enumerate}[label=(\roman*)]
\item $N_K(H)=\sum_i\cos^2\theta_i$, where $\theta_i$ are the principal angles between $\col(H)$ and $\mathrm{span}(U_K)$.
\item $0\le N_K(H)\le\min(K,\rank H)$.
\item For a single nonzero vector, $N_K(h)=\norm{P_Kh}^2/\norm{h}^2\le1$.
\item $\norm{(I-\Pi_H)U_K}_F^2=K-N_K(H)$, so $s_K(H)^2\le K-N_K(H)$ and $s_K(H)^2\ge(K-N_K(H))/K$.
\end{enumerate}
\end{lemma}
\begin{proof}
(i) The singular values of $U_K^\top Q_H$ are the cosines of the principal angles \cite{bjorckgolub1973}. (ii) There are $\min(K,\rank H)$ principal angles and each $\cos^2\theta_i\in[0,1]$. (iii) Take $Q_H=h/\norm{h}$. (iv) $\norm{\Pi_HU_K}_F^2=\tr(U_K^\top\Pi_HU_K)=N_K(H)$ and $\norm{U_K}_F^2=K$, so Pythagoras gives the identity; then $\norm{\cdot}_F^2/K\le\norm{\cdot}_2^2\le\norm{\cdot}_F^2$.
\end{proof}

\section{Optimizing neurons to capture low frequencies}
\label{sec:optimize}

By Lemma~\ref{lem:NK}(iii) a single neuron captures at most one low-frequency dimension; capturing many is a property of a layer. We first bound what a single gated neuron can achieve, then give a fixed-gating formulation for a single neuron and for the marginal gain of adding a neuron to a layer.

\begin{proposition}[Limits imposed by the active set]
\label{prop:activeset}
Let $h\ne0$ be supported on $A\subseteq\{1,\dots,n\}$ (for a ReLU neuron, its active set) and let $B$ be the complement. Let $\ell_i=\norm{U_K^\top e_i}^2$ be the leverage scores of $U_K$ \cite{drineas2012}. Then
\[
N_K(h)\le\norm{U_K[A,:]}_2^2\le\min\Big(1,\sum_{i\in A}\ell_i\Big),\qquad
R(h)\ge\lambda_{\min}(\Lap_{AA}),
\]
where $\Lap_{AA}$ is the principal submatrix on $A$. Moreover $\lambda_{\min}(\Lap_{AA})\le\lambda_{\abs{B}+1}$.
\end{proposition}
\begin{proof}
Write $h_A$ for the restriction of $h$ to $A$. Then $\norm{P_Kh}^2=\norm{U_K[A,:]^\top h_A}^2\le\norm{U_K[A,:]}_2^2\norm{h}^2$. The spectral norm is at most $1$ because $U_K$ has orthonormal columns, and at most the Frobenius norm, whose square is $\sum_{i\in A}\ell_i$. Next, $h^\top\Lap h=h_A^\top\Lap_{AA}h_A\ge\lambda_{\min}(\Lap_{AA})\norm{h}^2$. Finally, Cauchy interlacing \cite{hornjohnson2013} for an $\abs{A}\times\abs{A}$ principal submatrix gives $\lambda_1(\Lap_{AA})\le\lambda_{1+n-\abs{A}}(\Lap)=\lambda_{\abs{B}+1}$.
\end{proof}

\begin{remark}
Since $\sum_i\ell_i=K$, for delocalized eigenvectors $\ell_i\approx K/n$ and a neuron active on $\abs{A}$ vertices captures at most about $K\abs{A}/n$. Small active sets cap low-frequency capture, formalizing why dead or very sparse ReLUs hurt coverage. The bound $R(h)\ge\lambda_{\min}(\Lap_{AA})$ is a Dirichlet eigenvalue: the inactive set $B$ acts as a boundary on which $h(B)=0$, in the spirit of the harmonic-extension theorem \cite[Thm.~11.6.1]{spielmanSpectralAlgebraicGraph}. Conversely, by Proposition~\ref{prop:preserve}(a), the pair $\sigma(u_k),\sigma(-u_k)$, supported on the positive and negative nodal domains of $u_k$, recovers $u_k$; discrete nodal domain theorems \cite{davies2001} bound how many such domains $u_k$ has.
\end{remark}

\begin{proposition}[Fixed-gating formulation for one neuron]
\label{prop:fixedgating}
Fix a $0/1$ diagonal matrix $S$ and let $C_S=\{\theta:(2S-I)\Phi\theta\ge0\}$, a polyhedral cone. For $\theta\in C_S$ we have $\sigma(\Phi\theta)=S\Phi\theta$, and if $S\Phi\theta\ne0$,
\[
N_K\big(\sigma(\Phi\theta)\big)=\frac{\theta^\top A_S\theta}{\theta^\top B_S\theta},\qquad A_S=\Phi^\top SP_KS\Phi,\quad B_S=\Phi^\top S\Phi .
\]
Moreover
\[
\sup_{\theta\in C_S,\ S\Phi\theta\ne0}N_K\big(\sigma(\Phi\theta)\big)\;\le\;\norm{U_K^\top Q_S}_2^2=\cos^2\theta_{\min}\big(\col(S\Phi),\mathrm{span}(U_K)\big),
\]
where $Q_S$ is an orthonormal basis of $\col(S\Phi)$, with equality if a maximizer of the unconstrained ratio lies in $C_S$. The global problem $\max_\theta N_K(\sigma(\Phi\theta))$ equals the maximum of the cone-constrained problems over the finitely many gating patterns realized by $\Phi$.
\end{proposition}
\begin{proof}
If $S_{ii}=1$ and $(\Phi\theta)_i\ge0$ then $\sigma(\Phi\theta)_i=(\Phi\theta)_i=(S\Phi\theta)_i$; if $S_{ii}=0$ and $(\Phi\theta)_i\le0$ then $\sigma(\Phi\theta)_i=0=(S\Phi\theta)_i$. So on $C_S$ the neuron is the linear map $\theta\mapsto S\Phi\theta$, and Lemma~\ref{lem:NK}(iii) with $S^2=S=S^\top$ gives the ratio. Dropping the cone constraint, the ratio ranges over $\norm{P_Kv}^2/\norm{v}^2$ for nonzero $v\in\col(S\Phi)$, whose maximum is $\norm{U_K^\top Q_S}_2^2$, the squared cosine of the smallest principal angle \cite{bjorckgolub1973}. Every $\theta$ lies in $C_{S(\theta)}$, which proves the last claim; the number of realized patterns is finite and, for fixed $\rank\Phi$, polynomial in $n$ \cite{cover1965,pilanciergen2020}.
\end{proof}

\begin{remark}
A maximizer $v^\star=Q_Sy^\star$ of the unconstrained ratio ($y^\star$ a top right singular vector of $U_K^\top Q_S$) is realizable in $C_S$ iff, for one choice of sign, $\pm v^\star_A\ge0$ and the linear program $\{\theta:\Phi_A\theta=\pm v^\star_A,\ \Phi_B\theta\le0\}$ is feasible, where $A,B$ are the active and inactive index sets of $S$. Maximizing a Rayleigh quotient over a cone is a cone-constrained (Pareto) eigenvalue problem \cite{seeger1999}. The cone $C_S$ and the enumeration over patterns are the same objects as in the convex reformulation of two-layer ReLU networks \cite{pilanciergen2020}.
\end{remark}

\begin{proposition}[Marginal gain of a new neuron]
\label{prop:marginal}
Let $H$ have orthonormal basis $Q$, let $h\notin\col(H)$, and set $\tilde h=(I-\Pi_H)h$ and $M=(I-\Pi_H)U_K$. Then
\[
N_K([H,h])-N_K(H)=\frac{\norm{U_K^\top\tilde h}^2}{\norm{\tilde h}^2}=\frac{\norm{M^\top h}^2}{\norm{(I-\Pi_H)h}^2}.
\]
For fixed gating $S$ and $\theta\in C_S$ this is the ratio $\theta^\top\Phi^\top SMM^\top S\Phi\theta\,/\,\theta^\top\Phi^\top S(I-\Pi_H)S\Phi\theta$, so Proposition~\ref{prop:fixedgating} applies verbatim with these matrices.
\end{proposition}
\begin{proof}
Gram--Schmidt gives the orthonormal basis $[Q,q]$ of $\col([H,h])$ with $q=\tilde h/\norm{\tilde h}$, so
\[
N_K([H,h])=\norm{U_K^\top Q}_F^2+\norm{U_K^\top q}^2 .
\] Finally $U_K^\top\tilde h=U_K^\top(I-\Pi_H)h=M^\top h$.
\end{proof}

%\begin{proposition}[Fixed-gating formulation of the coverage gap]
%\label{prop:fixedgap}
%Let $H$ and $M=(I-\Pi_H)U_K$ be as in Proposition~\ref{prop:marginal}, let $\eta_1\ge\eta_2\ge\cdots$ be the singular values of $M$ (so $\eta_1=s_K(H)$), fix $S$ and $C_S$ as in Proposition~\ref{prop:fixedgating}, and let $W_S=(I-\Pi_H)\col(S\Phi)$. For $\theta\in C_S$ with $S\Phi\theta\notin\col(H)$,
%\[
%s_K\big([H,\sigma(\Phi\theta)]\big)^2=\lambda_{\max}\Big(M^\top M-\frac{M^\top S\Phi\theta\,\theta^\top\Phi^\top SM}{\theta^\top\Phi^\top S(I-\Pi_H)S\Phi\theta}\Big).
%\]
%Moreover
%\[
%\inf_{\theta\in C_S,\ S\Phi\theta\notin\col(H)}s_K\big([H,\sigma(\Phi\theta)]\big)\;\ge\;\max\big(\eta_2,\ s_K([H,S\Phi])\big),
%\]
%with equality if a minimizer of the problem without the cone constraint lies in $C_S$; without the cone constraint (and $W_S\ne\{0\}$) the right-hand side is always attained. The global problem $\min_\theta s_K([H,\sigma(\Phi\theta)])$ equals the minimum of the cone-constrained problems over the finitely many gating patterns realized by $\Phi$.
%\end{proposition}
%\begin{proof}
%As in Proposition~\ref{prop:marginal}, $\Pi_{[H,h]}=\Pi_H+qq^\top$ with $q=(I-\Pi_H)h/\norm{(I-\Pi_H)h}$, so $(I-\Pi_{[H,h]})U_K=(I-qq^\top)M$ and $s_K([H,h])^2=\lambda_{\max}(M^\top M-M^\top qq^\top M)$. Since $M^\top(I-\Pi_H)=M^\top$, substituting $h=S\Phi\theta$ gives the formula.

%For a unit vector $w\in W_S$ let $F(w)=\lambda_{\max}\big(M^\top(I-ww^\top)M\big)$; by the above, the values of $F$ are exactly the values of $s_K([H,S\Phi\theta])^2$. Weyl's inequality for the rank-one downdate gives $F(w)\ge\eta_2^2$, as in Theorem~\ref{thm:limits}. Since $ww^\top\preceq\Pi_{W_S}$, $F(w)\ge\norm{(I-\Pi_{W_S})M}_2^2$, and $\Pi_{[H,S\Phi]}=\Pi_H+\Pi_{W_S}$ gives $(I-\Pi_{W_S})M=(I-\Pi_{[H,S\Phi]})U_K$. This proves the lower bound.

%For attainment let $\mu_0=\max(\eta_2,s_K([H,S\Phi]))^2$. If $\mu_0=\eta_1^2$ there is nothing to prove, since $F\le\eta_1^2$. Otherwise fix $\mu\in(\mu_0,\eta_1^2)$ and let $C=MM^\top$. The matrix $A=M^\top M-\mu I$ has one positive and $K-1$ negative eigenvalues. For $c=M^\top w$, interlacing shows $A-cc^\top$ has at least $K-1$ negative eigenvalues, and $\det(A-cc^\top)=\det A\,(1-c^\top A^{-1}c)$, so $F(w)\le\mu$ iff $c^\top A^{-1}c\ge1$. The push-through identity $M(M^\top M-\mu I)^{-1}M^\top=I+\mu(C-\mu I)^{-1}$ turns this into $w^\top(C-\mu I)^{-1}w\ge0$. Let $Q_W,Q_\perp$ be orthonormal bases of $W_S$ and $W_S^\perp$. Then $Q_\perp^\top(C-\mu I)Q_\perp\prec0$, because its largest eigenvalue is $\norm{(I-\Pi_{W_S})M}_2^2-\mu<0$. Since $C-\mu I$ is nonsingular with exactly one positive eigenvalue, Haynsworth inertia additivity \cite{hornjohnson2013} shows that the Schur complement of this block has exactly one positive eigenvalue, and its inverse is $Q_W^\top(C-\mu I)^{-1}Q_W$. Hence some unit $w\in W_S$ has $w^\top(C-\mu I)^{-1}w>0$, that is, $F(w)\le\mu$. Letting $\mu\downarrow\mu_0$ and using compactness of the unit sphere of $W_S$ gives $\min F=\mu_0$. Every unit $w\in W_S$ is $(I-\Pi_H)S\Phi\theta/\norm{(I-\Pi_H)S\Phi\theta}$ for some $\theta$ with $S\Phi\theta\notin\col(H)$. The remaining claims follow as in Proposition~\ref{prop:fixedgating}.
%\end{proof}


\section{Increasing coverage across layers}
\label{sec:increase}

Proposition~\ref{prop:preserve} shows that coverage need not decrease from one layer to the next. This section asks when, and how fast, the remaining neurons of a layer can \emph{increase} it. Fix a layer $\ell$ and $\Phi=[H_{\ell-1},\one]$. For a feature matrix $H$ built in this layer write
\[
M_H=(I-\Pi_H)U_K,\qquad \delta(H)=K-N_K(H)=\norm{M_H}_F^2,\qquad G_H(h)=\frac{\norm{M_H^\top h}^2}{\norm{(I-\Pi_H)h}^2},
\]
so that $\delta(H)$ is the coverage deficit (Lemma~\ref{lem:NK}(iv)) and, by Proposition~\ref{prop:marginal}, $G_H(h)$ is the increase of $N_K$ obtained by appending $h\notin\col(H)$. Since $G_H(h)=\norm{M_H^\top\hat y}^2$ for the unit vector $\hat y=(I-\Pi_H)h/\norm{(I-\Pi_H)h}$, we always have $G_H(h)\le\norm{M_H}_2^2=s_K(H)^2$. We also use that $N_K$ is monotone: if $\col(A)\subseteq\col(B)$ then $\Pi_B-\Pi_A\succeq0$, so $N_K(B)-N_K(A)=\tr\big((\Pi_B-\Pi_A)P_K\big)\ge0$.

\subsection{When can a layer increase coverage?}

What a layer can add is determined by which samples it can still tell apart.

\begin{theorem}[Span of ReLU features]
\label{thm:reluspan}
Let $\mathcal P$ be the partition of $\{1,\dots,n\}$ into classes of samples with identical rows in $H_{\ell-1}$, let $q$ be the number of classes, and let $V_{\mathcal P}\subseteq\R^n$ be the $q$-dimensional subspace of vectors that are constant on each class, with orthogonal projector $\Pi_{\mathcal P}$. Then
\begin{enumerate}[label=(\alph*)]
\item $\sigma(\Phi\theta)\in V_{\mathcal P}$ for every $\theta$;
\item $\mathrm{span}\{\sigma(\Phi\theta):\theta\in\R^m\}=V_{\mathcal P}$. In fact $q$ neurons sharing one weight direction suffice.
\end{enumerate}
In particular, if the rows of $H_{\ell-1}$ are pairwise distinct, ReLU features of layer $\ell$ span $\R^n$.
\end{theorem}
\begin{proof}
(a) Samples with identical rows receive identical pre-activations. (b) Choose one representative per class. Their rows are distinct, so a generic $w\in\R^{m_{\ell-1}}$ (one avoiding the finitely many hyperplanes on which two representatives have equal projection) gives distinct projections, which we order as $t_1<\dots<t_q$. Choose $b_1<t_1$ and $b_k\in(t_{k-1},t_k)$ for $k\ge2$, and let $v_k=\sigma(H_{\ell-1}w-b_k\one)$, the neuron with $\theta=(w,-b_k)$. On class $c$, $v_k$ equals $(t_c-b_k)_+$, which is $0$ for $c<k$ and positive for $c\ge k$. In the basis of class indicators, $v_1,\dots,v_q$ therefore form a triangular matrix with positive diagonal, so they are linearly independent and span the $q$-dimensional space $V_{\mathcal P}$. This is the interpolation construction of \cite{zhang2017}.
\end{proof}

\begin{corollary}[Coverage ceiling]
\label{cor:ceiling}
Samples with identical rows in $H_{\ell-1}$ have identical rows in every later layer. Hence the readout features of every network that agrees with the given one up to layer $\ell-1$ satisfy $\col(Z)\subseteq V_{\mathcal P}$, and
\[
N_K(Z)\le N_K(V_{\mathcal P})=K-\norm{(I-\Pi_{\mathcal P})U_K}_F^2 .
\]
If the rows of $H_{\ell-1}$ are distinct then $V_{\mathcal P}=\R^n$ and the ceiling is $K$. Otherwise, any variation of the low eigenvectors within a collapsed class is lost for all subsequent layers.
\end{corollary}
\begin{proof}
Identical inputs to a layer give identical outputs, so by induction every column of every later $H_{\ell'}$, and the bias column, lies in $V_{\mathcal P}$. Monotonicity of $N_K$ gives the inequality, and Lemma~\ref{lem:NK}(iv) applied to $V_{\mathcal P}$ gives the identity.
\end{proof}

\begin{theorem}[Strict increase of coverage]
\label{thm:strict}
Let $H$ consist of outputs of layer-$\ell$ neurons and possibly the bias column (for instance the copy neurons of Proposition~\ref{prop:preserve}), so that $\col(H)\subseteq V_{\mathcal P}$. Then
\[
N_K(V_{\mathcal P})-N_K(H)=\norm{(\Pi_{\mathcal P}-\Pi_H)U_K}_F^2,
\]
and
\begin{enumerate}[label=(\alph*)]
\item if $N_K(H)<N_K(V_{\mathcal P})$, there exists $\theta$ with $N_K\big([H,\sigma(\Phi\theta)]\big)>N_K(H)$;
\item if $N_K(H)=N_K(V_{\mathcal P})$, no neuron of layer $\ell$, and no choice of later layers, can increase $N_K$ beyond $N_K(H)$.
\end{enumerate}
\end{theorem}
\begin{proof}
Since $\col(H)\subseteq V_{\mathcal P}$, the projectors $\Pi_H$ and $\Pi_{\mathcal P}$ commute and $\Pi_{\mathcal P}-\Pi_H=\Pi_{\mathcal P}(I-\Pi_H)$ is an orthogonal projector, so $N_K(V_{\mathcal P})-N_K(H)=\tr\big((\Pi_{\mathcal P}-\Pi_H)P_K\big)=\norm{(\Pi_{\mathcal P}-\Pi_H)U_K}_F^2$. (a) A neuron $h$ has positive gain iff $M_H^\top h\ne0$; note $h\notin\col(H)$ is then automatic, since $M_H^\top h=U_K^\top(I-\Pi_H)h$. By Theorem~\ref{thm:reluspan}(b), such a neuron exists iff $M_H^\top$ does not vanish on $V_{\mathcal P}$, i.e.\ iff $\Pi_{\mathcal P}M_H=(\Pi_{\mathcal P}-\Pi_H)U_K\ne0$, which is exactly the condition that the gap is positive. (b) This follows from Corollary~\ref{cor:ceiling}.
\end{proof}

\begin{corollary}[A layer can increase coverage]
\label{cor:increase}
Suppose the rows of $H_{\ell-1}$ are pairwise distinct and $N_K(\Phi)<K$. Then there is a layer of width $m_{\ell-1}+1$ (or $2d+1$ when $\ell=1$) with $N_K([H_\ell,\one])>N_K(\Phi)$ and $s_K([H_\ell,\one])\le s_K(\Phi)$.
\end{corollary}
\begin{proof}
Take the copy neurons of Proposition~\ref{prop:preserve}(b) or (c). Together with $\one$ they give $H$ with $\col(H)\supseteq\col(\Phi)$ (with equality when $\ell\ge2$), so $N_K(H)\ge N_K(\Phi)$ and, by Lemma~\ref{lem:monotone}, $s_K(H)\le s_K(\Phi)$. Here $V_{\mathcal P}=\R^n$ and $N_K(V_{\mathcal P})=K$. If $N_K(H)=K$, the copies already give a strict increase over $N_K(\Phi)<K$. Otherwise Theorem~\ref{thm:strict}(a) supplies one more neuron with positive gain, so $N_K([H_\ell,\one])>N_K(H)\ge N_K(\Phi)$. Appending it does not increase $s_K$, by Lemma~\ref{lem:monotone}.
\end{proof}

The copy neurons of Proposition~\ref{prop:preserve} cost $m_{\ell-1}$ (or $2d$) units. For coverage, far fewer suffice.

\begin{proposition}[Preserving coverage with $2K+2$ neurons]
\label{prop:cheap}
Let $r=\min(K,\rank\Phi)$, let $Q_\Phi$ be an orthonormal basis of $\col(\Phi)$, let $y_1,\dots,y_r$ be the top right singular vectors of $U_K^\top Q_\Phi$, and let $p_i=Q_\Phi y_i=\Phi\theta_i$ be the corresponding principal vectors in $\col(\Phi)$. Suppose the rows of $H_{\ell-1}$ are distinct, and let $w$ be such that $\Phi w$ has distinct entries. Then any layer containing the $2r+2$ neurons $\sigma(\pm\Phi\theta_i)$, $i\le r$, and $\sigma(\pm\Phi w)$ satisfies
\[
N_K([H_\ell,\one])\ge N_K(\Phi),\qquad s_K([H_\ell,\one])\le s_K(\Phi),
\]
and $H_\ell$ has pairwise distinct rows.
\end{proposition}
\begin{proof}
By Proposition~\ref{prop:preserve}(a), $p_i=\sigma(p_i)-\sigma(-p_i)\in\col(H_\ell)$, so $W=\mathrm{span}\{p_1,\dots,p_r\}\subseteq\col(H_\ell)$. The matrix $U_K^\top Q_\Phi$ has at most $r$ nonzero singular values $\cos\theta_i$, and $U_K^\top Q_W=U_K^\top Q_\Phi[y_1,\dots,y_r]$ retains all of them, so $N_K(W)=\sum_{i\le r}\cos^2\theta_i=N_K(\Phi)$ by Lemma~\ref{lem:NK}(i). If $r=K$, then $s_K(W)^2=1-\sigma_{\min}(U_K^\top Q_W)^2=1-\sigma_{\min}(U_K^\top Q_\Phi)^2=s_K(\Phi)^2$; if $r<K$, then $\rank\Phi<K$, so some unit vector in $\mathrm{span}(U_K)$ is orthogonal to $\col(\Phi)$ and $s_K(\Phi)=1$. Monotonicity of $N_K$ and Lemma~\ref{lem:monotone} give the two inequalities. A direction $w$ exists because the rows of $\Phi$ are distinct and a generic $w$ avoids finitely many hyperplanes. If rows $i\ne j$ of $H_\ell$ were equal, then $(\Phi w)_i=\sigma(\Phi w)_i-\sigma(-\Phi w)_i$ would equal $(\Phi w)_j$, a contradiction.
\end{proof}

\begin{remark}
\label{rem:cheap}
A layer of width $2K+2+t$ therefore preserves coverage, keeps Theorem~\ref{thm:reluspan} applicable at the next layer, and leaves $t$ neurons free to add coverage. Under the hypotheses of Corollary~\ref{cor:increase}, width $2r+1$ already gives a strict increase: either the $2r$ principal-vector neurons alone give $N_K=K>N_K(\Phi)$, or Theorem~\ref{thm:strict}(a) applies to them. The inequality $N_K([H_\ell,\one])\ge N_K(\Phi)$ is typically strict, because the pieces $\sigma(\pm p_i)$ span more than $p_i$.
\end{remark}

\begin{remark}[Skip connections]
\label{rem:resnet}
Propositions~\ref{prop:preserve} and~\ref{prop:cheap} spend $m_{\ell-1}$, $2d$ or $2K+2$ neurons of every layer only on preserving coverage. Skip connections, as in residual networks \cite{he2016}, do this for free. We consider the concatenated form of \cite{huang2017},
\[
H_\ell=[H_{\ell-1},R_\ell],\qquad R_\ell=\sigma(\Phi\Theta_\ell),\quad \Phi=[H_{\ell-1},\one],
\]
with $\Theta_\ell\in\R^{(m_{\ell-1}+1)\times k_\ell}$, so that the columns of $R_\ell$ are $k_\ell$ neurons of the form \eqref{eq:neuron}. The skip path preserves coverage, while the ReLU branch tries to increase it. Indeed, $\col([H_\ell,\one])\supseteq\col(\Phi)$ for every $\Theta_\ell$, so $s_K$ is nonincreasing (Lemma~\ref{lem:monotone}) and $N_K$ nondecreasing in $\ell$. Rows that are distinct in $H_{\ell-1}$ stay distinct, so the ceiling of Corollary~\ref{cor:ceiling} never drops and Theorem~\ref{thm:reluspan} applies at every layer. The branch contributes exactly the marginal gains $G_\Phi$ of Proposition~\ref{prop:marginal}: all $k_\ell$ branch neurons are free to add coverage, Theorem~\ref{thm:strict}(a) with $H=\Phi$ guarantees that one can unless $N_K(\Phi)=N_K(V_{\mathcal P})$, and Theorem~\ref{thm:greedy} applies with $H^{(0)}=\Phi$. The additive skip $H_\ell=H_{\ell-1}+R_\ell\Omega_\ell$ of residual networks mixes the branch into the existing features, so $\col([H_\ell,\one])$ need not contain $\col(\Phi)$; we leave its analysis to future work.
\end{remark}

\subsection{How fast can a layer increase coverage?}

Theorem~\ref{thm:strict} guarantees a positive gain but not its size. Width $q$ trivially attains the ceiling (Theorem~\ref{thm:reluspan}(b)), and for distinct rows $q=n$, which makes $\col(Z)=\R^n$ and $g=f$. The relevant question is therefore how much coverage $t\ll n$ neurons provide. This depends on how economically ReLU features represent the low eigenvectors.

\begin{definition}[ReLU variation norm]
\label{def:atomic}
Let $\mathcal A_\Phi=\{\sigma(\Phi\theta)/\norm{\sigma(\Phi\theta)}:\sigma(\Phi\theta)\ne0\}$ be the normalized neurons of layer $\ell$, and for $v\in\R^n$ let
\[
\norm{v}_{\mathcal A}=\inf\Big\{\sum_j\abs{a_j}:\ v=\sum_ja_jd_j,\ d_j\in\mathcal A_\Phi\Big\}
\]
(finite sums; $\inf\emptyset=\infty$). By Theorem~\ref{thm:reluspan}, $\norm{v}_{\mathcal A}<\infty$ iff $v\in V_{\mathcal P}$. We say $U_K$ is \emph{$(\kappa,\varepsilon)$-representable} by layer $\ell$ if every unit vector $u\in\mathrm{span}(U_K)$ can be written $u=v+e$ with $\norm{v}_{\mathcal A}\le\kappa$ and $\norm{e}\le\varepsilon$.
\end{definition}

If the rows of $H_{\ell-1}$ are distinct, then $V_{\mathcal P}=\R^n$, so $\norm{u_k}_{\mathcal A}<\infty$ for every $k$. Since $\norm{\cdot}_{\mathcal A}$ is a seminorm, every unit $u=\sum_kc_ku_k$ satisfies $\norm{u}_{\mathcal A}\le\sum_k\abs{c_k}\norm{u_k}_{\mathcal A}\le\sqrt K\max_k\norm{u_k}_{\mathcal A}$. Hence $U_K$ is $(\kappa,0)$-representable with $\kappa=\sqrt K\max_k\norm{u_k}_{\mathcal A}<\infty$, although this $\kappa$ may be very large.

\begin{lemma}[Best single neuron]
\label{lem:bestneuron}
Let $U_K$ be $(\kappa,\varepsilon)$-representable by layer $\ell$, let $H$ be any feature matrix, and let $s=s_K(H)$. Then
\[
G^\ast:=\sup\big\{G_H(\sigma(\Phi\theta)):\ \sigma(\Phi\theta)\notin\col(H)\big\}\ \ge\ \frac{s^2(s-\varepsilon)_+^2}{\kappa^2}.
\]
\end{lemma}
\begin{proof}
For every $d\in\mathcal A_\Phi$ we have $\norm{M_H^\top d}\le\sqrt{G^\ast}\,\norm{(I-\Pi_H)d}\le\sqrt{G^\ast}$; this also holds if $d\in\col(H)$, since then $M_H^\top d=U_K^\top(I-\Pi_H)d=0$. Let $x$ be a unit vector with $M_H^\top M_Hx=s^2x$, and write $U_Kx=v+e$ with $v=\sum_ja_jd_j$, $\sum_j\abs{a_j}\le\kappa+\eta$ for arbitrary $\eta>0$, and $\norm{e}\le\varepsilon$. Since $M_H^\top M_H=U_K^\top(I-\Pi_H)U_K=M_H^\top U_K$,
\[
s^2=\norm{M_H^\top U_Kx}\le\sum_j\abs{a_j}\,\norm{M_H^\top d_j}+\norm{M_H}_2\norm{e}\le(\kappa+\eta)\sqrt{G^\ast}+s\varepsilon .
\]
Let $\eta\to0$ and rearrange.
\end{proof}

\begin{theorem}[Greedy coverage rate]
\label{thm:greedy}
Let $U_K$ be $(\kappa,\varepsilon)$-representable by layer $\ell$ and fix $\alpha\in(0,1]$. Let $H^{(0)}$ be any initial features of layer $\ell$ (for example from Proposition~\ref{prop:preserve} or Proposition~\ref{prop:cheap}), and for $t\ge0$ let $H^{(t+1)}=[H^{(t)},\sigma(\Phi\theta_{t+1})]$, where the appended neuron achieves at least $\alpha G^\ast$ for $H=H^{(t)}$ in Lemma~\ref{lem:bestneuron}. Write $\delta_t=\delta(H^{(t)})$ and $s_t=s_K(H^{(t)})$. Then, as long as $s_t\ge2\varepsilon$ (with the convention $1/0=\infty$),
\[
\delta_t\le\Big(\frac{1}{\delta_0}+\frac{\alpha t}{4K^2\kappa^2}\Big)^{-1},
\]
and for all $t\ge1$,
\[
s_t^2\le\max\Big\{4\varepsilon^2,\ \frac{4K^2\kappa^2}{\alpha t}\Big\}.
\]
Consequently, if the readout features $Z$ contain $H^{(t)}$, Corollary~\ref{cor:targetonly} gives $\norm{g-f}\le s_t\norm{P_Kf}+\norm{\Perp f}$ with $s_t^2$ bounded as above.
\end{theorem}
\begin{proof}
By Lemma~\ref{lem:monotone}, $s_t$ is nonincreasing, so the steps with $s_t\ge2\varepsilon$ form an initial segment. On it, $s_t-\varepsilon\ge s_t/2$, and Lemma~\ref{lem:NK}(iv) with $\rank M_{H^{(t)}}\le K$ gives $s_t^2\ge\delta_t/K$. Lemma~\ref{lem:bestneuron} then gives a gain of at least $\alpha s_t^4/(4\kappa^2)\ge c\,\delta_t^2$ with $c=\alpha/(4K^2\kappa^2)$, so $\delta_{t+1}\le\delta_t-c\delta_t^2$. If $\delta_{t+1}>0$ then $c\delta_t<1$ and
\[
\frac1{\delta_{t+1}}\ge\frac{1}{\delta_t(1-c\delta_t)}\ge\frac{1+c\delta_t}{\delta_t}=\frac1{\delta_t}+c,
\]
and induction gives the bound on $\delta_t$. If $\delta_{t+1}=0$, all later deficits and gaps vanish. Hence on the initial segment $s_t^2\le\delta_t\le1/(ct)=4K^2\kappa^2/(\alpha t)$, and after it $s_t<2\varepsilon$. The final claim is Corollary~\ref{cor:targetonly} combined with Lemma~\ref{lem:monotone}, which gives $s_K(Z)\le s_t$.
\end{proof}

\begin{remark}
\label{rem:greedy}
Theorem~\ref{thm:greedy} is the $O(1/t)$ rate of greedy approximation in Hilbert space \cite{jones1992,barron1993,devoretemlyakov1996}, applied to subspace coverage rather than to a single target. The candidate neurons can be produced by the fixed-gating formulation of Propositions~\ref{prop:fixedgating} and~\ref{prop:marginal}, but the theorem requires an $\alpha$-approximate maximizer of the gain over all gating patterns, which a local method does not certify. The bound is informative only when $\kappa$ is small enough that $4K^2\kappa^2/\alpha\ll n$.
\end{remark}

\begin{example}[Clusters cut off by hyperplanes]
\label{ex:clusters}
Suppose the samples are partitioned into clusters $C_1,\dots,C_K$, and each $C_c$ is cut off from the rest by a hyperplane with a margin in layer-$(\ell-1)$ features: for some $w_c$, with $z=H_{\ell-1}w_c$, no entry of $z$ lies in an interval $(a_c,a_c')$, and $C_c=\{i:z_i\ge a_c'\}$. Then, exactly on the sample,
\[
\mathbb 1_{C_c}=\frac{\sigma(z-a_c\one)-\sigma(z-a_c'\one)}{a_c'-a_c}.
\]
Both ReLU terms vanish off $C_c$ and have entries at most $z_{\max}-a_c$ on $C_c$. Hence the normalized indicator $\chi_c=\mathbb 1_{C_c}/\sqrt{\abs{C_c}}$ satisfies $\norm{\chi_c}_{\mathcal A}\le2\omega_c$, where $\omega_c=(z_{\max}-a_c)/(a_c'-a_c)$ is a spread-to-margin ratio. The $\chi_c$ are orthonormal, so every unit $u\in\mathrm{span}(U_K)$ splits as $u=\Pi_\chi u+(I-\Pi_\chi)u$ with $\norm{\Pi_\chi u}_{\mathcal A}\le2\sqrt K\max_c\omega_c$. Thus $U_K$ is $(\kappa,\varepsilon)$-representable with
\[
\kappa=2\sqrt K\max_c\omega_c,\qquad \varepsilon=\norm{(I-\Pi_\chi)U_K}_2 .
\]
Here $\varepsilon$ measures how far the low eigenvectors are from piecewise constant on the clusters, and Davis--Kahan bounds \cite{daviskahan1970} control it through the between-cluster edge weight relative to $\lambda_{K+1}$. By Theorem~\ref{thm:greedy}, about $16K^3\max_c\omega_c^2/(\alpha s^2)$ greedy neurons reach coverage gap $s\ge2\varepsilon$, independently of $n$.
\end{example}

\subsection{What no layer can do}

\begin{theorem}[Limits per neuron]
\label{thm:limits}
Let $\eta_1\ge\dots\ge\eta_K$ be the singular values of $M_\Phi=(I-\Pi_\Phi)U_K$ (when $\rank\Phi\ge K$, the sines of the principal angles between $\mathrm{span}(U_K)$ and $\col(\Phi)$), and set $\eta_i=0$ for $i>K$. If $\col(Z)\subseteq\col(\Phi)+T$ for a subspace $T$ with $\dim T\le t$, for example when $\ell\ge2$ and $Z$ consists of the copy neurons of Proposition~\ref{prop:preserve}(b), $t$ further neurons and $\one$, then
\[
N_K(Z)-N_K(\Phi)\le\sum_{i\le t}\eta_i^2,\qquad s_K(Z)\ge\eta_{t+1}.
\]
Both bounds are attained, without the ReLU constraint, by taking $T$ spanned by the top $t$ left singular vectors of $M_\Phi$.
\end{theorem}
\begin{proof}
By monotonicity of $N_K$ and Lemma~\ref{lem:monotone}, it suffices to treat $\col(Z)=\col(\Phi)+T$. Let $Q_T$ be an orthonormal basis of $(I-\Pi_\Phi)T$, so $Q_T$ has at most $t$ columns and $\Pi_Z=\Pi_\Phi+Q_TQ_T^\top$. Then $I-\Pi_Z=(I-Q_TQ_T^\top)(I-\Pi_\Phi)$, so $M_Z=(I-Q_TQ_T^\top)M_\Phi$ and
\[
M_Z^\top M_Z=M_\Phi^\top M_\Phi-M_\Phi^\top Q_TQ_T^\top M_\Phi ,
\]
a positive semidefinite downdate of rank at most $t$. Weyl's inequality \cite{hornjohnson2013} gives $\lambda_i(M_Z^\top M_Z)\ge\lambda_{i+t}(M_\Phi^\top M_\Phi)=\eta_{i+t}^2$ for every $i$. Taking $i=1$ gives the bound on $s_K$. Summing over $i\le K$ gives $\delta(Z)\ge\sum_{i>t}\eta_i^2$, and since $\delta(\Phi)=\sum_i\eta_i^2$, this is the bound on $N_K$. For attainment, the left singular vectors of $M_\Phi$ lie in $\col(\Phi)^\perp$, and removing the top $t$ of them leaves exactly the singular values $\eta_{t+1},\eta_{t+2},\dots$.
\end{proof}

\begin{remark}
\label{rem:limits}
Increasing $N_K$ and decreasing $s_K$ are different goals. A single neuron can strictly decrease $s_K$ only if the largest singular value of $M_\Phi$ is simple, and pushing $s_K$ below a level $c$ requires at least as many new neurons as there are $\eta_i>c$. Theorem~\ref{thm:limits} is the unconstrained (Ky Fan) benchmark; Theorem~\ref{thm:greedy} quantifies how closely ReLU neurons approach it. Together with Theorem~\ref{thm:strict}, this is the precise sense in which the neurons left free by Proposition~\ref{prop:preserve} add coverage.
\end{remark}

\section{Concluding remarks}

\begin{remark}[Reduction to the smoothness of the target, and future work]
\label{rem:conclusion}
By Lemma~\ref{lem:NK}(iv), $s_K(Z)^2\le K-N_K(Z)$, so Corollary~\ref{cor:targetonly} gives, for $\lambda_{K+1}>0$,
\[
\norm{g-f}\le\sqrt{K-N_K(Z)}\,\norm{f}+\frac{E(f)}{\sqrt{\lambda_{K+1}}}.
\]
Hence $s_K(Z)\to0$ as $N_K(Z)\to K$, and the error reduces to the smoothness component: once $N_K(Z)=K$, $\norm{g-f}\le E(f)/\sqrt{\lambda_{K+1}}$. By Corollary~\ref{cor:ceiling} this is attainable whenever the rows of $H_{p-1}$ are distinct, and Theorem~\ref{thm:greedy} bounds how many greedily chosen neurons it takes. Two directions remain for future work. First, the remaining term $E(f)/\sqrt{\lambda_{K+1}}$ depends only on $f$ and the graph, so we will investigate how to choose the graph, and hence the Laplacian $\Lap$, to minimize this smoothness component; since $\Lap$ also determines $U_K$, this has to be balanced against the coverage the network can achieve. Second, Theorem~\ref{thm:greedy} assumes an $\alpha$-approximate maximizer of the gain over all gating patterns (Remark~\ref{rem:greedy}); we will develop methods that find maximal-gain neurons using the fixed-gating formulation of Proposition~\ref{prop:fixedgating}, applied to the marginal gain through Proposition~\ref{prop:marginal}, by searching over gating patterns and solving the resulting cone-constrained generalized eigenvalue problems.
\end{remark}

\begin{thebibliography}{99}

\bibitem{spielmanSpectralAlgebraicGraph}
D.~A. Spielman.
\newblock \emph{Spectral and Algebraic Graph Theory}.
\newblock Book draft, Yale University, 2019.

\bibitem{chung1997}
F.~R.~K. Chung.
\newblock \emph{Spectral Graph Theory}, volume~92 of \emph{CBMS Regional Conference Series in Mathematics}.
\newblock American Mathematical Society, 1997.

\bibitem{vonluxburg2007}
U.~von Luxburg.
\newblock A tutorial on spectral clustering.
\newblock \emph{Statistics and Computing}, 17(4):395--416, 2007.

\bibitem{hornjohnson2013}
R.~A. Horn and C.~R. Johnson.
\newblock \emph{Matrix Analysis}.
\newblock Cambridge University Press, 2nd edition, 2013.

\bibitem{golubvanloan2013}
G.~H. Golub and C.~F. Van~Loan.
\newblock \emph{Matrix Computations}.
\newblock Johns Hopkins University Press, 4th edition, 2013.

\bibitem{bjorckgolub1973}
{\AA}.~Bj{\"o}rck and G.~H. Golub.
\newblock Numerical methods for computing angles between linear subspaces.
\newblock \emph{Mathematics of Computation}, 27(123):579--594, 1973.

\bibitem{stewartsun1990}
G.~W. Stewart and J.-G. Sun.
\newblock \emph{Matrix Perturbation Theory}.
\newblock Academic Press, 1990.

\bibitem{daviskahan1970}
C.~Davis and W.~M. Kahan.
\newblock The rotation of eigenvectors by a perturbation.~{III}.
\newblock \emph{SIAM Journal on Numerical Analysis}, 7(1):1--46, 1970.

\bibitem{drineas2012}
P.~Drineas, M.~Magdon-Ismail, M.~W. Mahoney, and D.~P. Woodruff.
\newblock Fast approximation of matrix coherence and statistical leverage.
\newblock \emph{Journal of Machine Learning Research}, 13:3475--3506, 2012.

% \bibitem{hoerlkennard1970}
% A.~E. Hoerl and R.~W. Kennard.
% \newblock Ridge regression: Biased estimation for nonorthogonal problems.
% \newblock \emph{Technometrics}, 12(1):55--67, 1970.

\bibitem{cover1965}
T.~M. Cover.
\newblock Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition.
\newblock \emph{IEEE Transactions on Electronic Computers}, EC-14(3):326--334, 1965.

\bibitem{pilanciergen2020}
M.~Pilanci and T.~Ergen.
\newblock Neural networks are convex regularizers: Exact polynomial-time convex optimization formulations for two-layer networks.
\newblock In \emph{Proceedings of the 37th International Conference on Machine Learning (ICML)}, 2020.

\bibitem{seeger1999}
A.~Seeger.
\newblock Eigenvalue analysis of equilibrium processes defined by linear complementarity conditions.
\newblock \emph{Linear Algebra and its Applications}, 292(1--3):1--14, 1999.

\bibitem{davies2001}
E.~B. Davies, G.~M.~L. Gladwell, J.~Leydold, and P.~F. Stadler.
\newblock Discrete nodal domain theorems.
\newblock \emph{Linear Algebra and its Applications}, 336:51--60, 2001.

% \bibitem{rahaman2019}
% N.~Rahaman, A.~Baratin, D.~Arpit, F.~Draxler, M.~Lin, F.~A. Hamprecht, Y.~Bengio, and A.~Courville.
% \newblock On the spectral bias of neural networks.
% \newblock In \emph{Proceedings of the 36th International Conference on Machine Learning (ICML)}, 2019.

\bibitem{zhang2017}
C.~Zhang, S.~Bengio, M.~Hardt, B.~Recht, and O.~Vinyals.
\newblock Understanding deep learning requires rethinking generalization.
\newblock In \emph{International Conference on Learning Representations (ICLR)}, 2017.

\bibitem{jones1992}
L.~K. Jones.
\newblock A simple lemma on greedy approximation in {H}ilbert space and convergence rates for projection pursuit regression and neural network training.
\newblock \emph{The Annals of Statistics}, 20(1):608--613, 1992.

\bibitem{barron1993}
A.~R. Barron.
\newblock Universal approximation bounds for superpositions of a sigmoidal function.
\newblock \emph{IEEE Transactions on Information Theory}, 39(3):930--945, 1993.

\bibitem{devoretemlyakov1996}
R.~A. DeVore and V.~N. Temlyakov.
\newblock Some remarks on greedy algorithms.
\newblock \emph{Advances in Computational Mathematics}, 5:173--187, 1996.

\bibitem{he2016}
K.~He, X.~Zhang, S.~Ren, and J.~Sun.
\newblock Deep residual learning for image recognition.
\newblock In \emph{Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)}, pages 770--778, 2016.

\bibitem{huang2017}
G.~Huang, Z.~Liu, L.~van~der Maaten, and K.~Q. Weinberger.
\newblock Densely connected convolutional networks.
\newblock In \emph{Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)}, pages 4700--4708, 2017.

\end{thebibliography}

\end{document}