7. Foundations IV: Function Spaces, Orthonormal Bases, Spectral SVD, and Minimax Complexity

Learning Objectives. By the end of this chapter, you will be able to treat functions as vectors in a Hilbert Space ($L^2$) with inner product $\langle f, g \rangle = \mathbb{E}[f(X)g(X)]$; construct Orthonormal Polynomial and Harmonic Bases (Chebyshev, Hermite, and Fourier atoms) via Gram-Schmidt orthogonalization; explain why Grid Discretization suffers the Curse of Dimensionality ($\varepsilon^{-d}$) while Spectral Smoothness ($C_f$) and Compositional Depth ($2^D$) escape it; compute eigenvalues, Trace ($\mathrm{tr},G$), Frobenius Norm ($|G|_F$), and the Participation Ratio / Effective Dimension ($d_{\mathrm{eff}} = (\mathrm{tr},G)^2 / |G|_F^2$) of a Gram matrix; and derive Le Cam’s Two-Point Minimax Lower Bound as a game between the Statistician and Nature.

Step 1 — Intuition and the Real-World Paradox

A Million Parameters That Only Know Three Directions

Suppose an engineering team trains a wide neural network or polynomial regression with $p = 1\text{,}000$ features $\phi_1(x), \phi_2(x), \dots, \phi_{1000}(x)$ and boasts that their model has a “1,000-dimensional representation.”

When an auditor inspects the $1\text{,}000$ feature columns evaluated on the dataset, however, she notices that features $\phi_4$ through $\phi_{1000}$ are nearly collinear copies of the first three features ($\phi_1, \phi_2, \phi_3$). Even though the parameter vector $\boldsymbol{\theta} \in \mathbb{R}^{1000}$ occupies $1\text{,}000$ floating-point slots in RAM, $99.7%$ of the variance of the feature matrix lives along just three orthogonal axes!

Worse still: when you try to fit a curve using raw monomial powers $1, x, x^2, x^3, x^4, x^5$ on $[0, 1]$, look at how similar $x^4$ and $x^5$ are—their correlation on $[0, 1]$ is $0.996$! Because the basis functions point in almost the same direction, changing the coefficient of $x^4$ by $+1\text{,}000$ and the coefficient of $x^5$ by $-1\text{,}000$ barely changes the prediction inside $[0, 1]$, but causes the polynomial to explode to $\pm \infty$ the instant $x$ steps outside $[0, 1]$ (Runge’s Phenomenon).

How do we build basis functions that are strictly perpendicular (orthonormal) to each other? How do we measure the true effective number of dimensions $d_{\mathrm{eff}}$ a model actually uses, regardless of how many parameters it claims on paper? And how do we prove mathematically that no algorithm in the universe can estimate a target faster than a fundamental minimax floor?

Those four questions are the exact prerequisites for Chapter 8 (The Almost-Perfect Machine $M=(T, \Phi, \theta)$ and First-Class Authentic Model Form $\delta(x) + \hat{S}^\ast$). Let us build each concept step by step from elementary geometry.

Step 2 — Foundations and Mathematical Formalization

7.1 Functions as Vectors: Inner Products and Orthonormal Bases in $L^2$

In Chapter 1, we saw that two vectors $\mathbf{u}, \mathbf{v} \in \mathbb{R}^n$ are orthogonal ($\mathbf{u} \perp \mathbf{v}$) if their dot product $\langle \mathbf{u}, \mathbf{v} \rangle = \sum_{i=1}^n u_i v_i = 0$, and orthonormal if they also have unit length $|\mathbf{u}|_2 = 1$.

Can we apply the exact same geometric idea to continuous functions $f(x)$ and $g(x)$? Yes! Define the $L^2(P_X)$ inner product between two functions $f, g$ as the expected value of their product when $X$ is drawn from distribution $P_X$:

$$\langle f, g \rangle_{L^2} = \mathbb{E}[f(X)g(X)] = \int f(x)g(x),dP_X(x), \qquad |f|_{L^2} = \sqrt{\langle f, f \rangle_{L^2}} = \sqrt{\mathbb{E}[f(X)^2]}$$

Definition 7.1 (Orthonormal Basis of Functions)

A family of basis functions (“atoms”) ${\psi_0(x), \psi_1(x), \psi_2(x), \dots}$ is orthonormal with respect to $P_X$ if every pair of distinct functions is perpendicular and every function has unit energy:

$$\langle \psi_j, \psi_k \rangle_{L^2} = \mathbb{E}[\psi_j(X)\psi_k(X)] = \delta_{jk} = \begin{cases} 1 & \text{if } j = k, \ 0 & \text{if } j \ne k. \end{cases}$$

Look at the miracle that happens when we expand an unknown target function $f(x) = \sum_{k=0}^K c_k \psi_k(x)$ in an orthonormal basis:

1. No Matrix Inversion Needed: Because the columns are already mutually perpendicular, the design Gram matrix is the identity matrix ($G = I$)! To find coefficient $c_j$, we simply take the inner product of $f$ with $\psi_j$: $$c_j = \langle f, \psi_j \rangle_{L^2} = \mathbb{E}[f(X)\psi_j(X)]$$
2. Independent Coefficients (Zero Collinearity): Adding a new basis function $\psi_{K+1}(x)$ to the model does not change any of the previously estimated coefficients $c_0, \dots, c_K$!
3. Parseval’s Energy Identity: The total squared norm (energy) of the function is the exact sum of its squared coefficients (the infinite-dimensional Pythagorean Theorem): $$|f|_{L^2}^2 = \mathbb{E}[f(X)^2] = \sum_{k=0}^K c_k^2$$

Three Canonical Orthonormal Families Used in Stochology

Depending on the domain of $X$, three orthonormal families appear repeatedly across this book:

1. Probabilists’ Orthonormal Hermite Polynomials (for Gaussian-like $Z \sim \mathcal{N}(0, 1)$, used in Chapter 6 Lens 4 for Nonlinear ICP / NILE): Starting from $1, z, z^2, z^3$ and applying Gram-Schmidt orthogonalization against the standard Gaussian density gives: $$\psi_0(z) = 1, \quad \psi_1(z) = z, \quad \psi_2(z) = \frac{z^2 - 1}{\sqrt{2}}, \quad \psi_3(z) = \frac{z^3 - 3z}{\sqrt{6}}$$ Check orthogonality of $\psi_0$ and $\psi_2$: since $\mathbb{E}[Z^2] = 1$, $\mathbb{E}[\psi_0(Z)\psi_2(Z)] = \frac{\mathbb{E}[Z^2] - 1}{\sqrt{2}} = 0$!
2. Chebyshev Polynomials $T_k(x) = \cos(k \arccos x)$ on $[-1, 1]$ (used in Chapter 8 for Authentic Symbolic Forms): By the trigonometric identity $\cos((k+1)\theta) + \cos((k-1)\theta) = 2\cos\theta \cos(k\theta)$, they obey the exact 3-term recurrence: $$T_0(x) = 1, \quad T_1(x) = x, \quad T_2(x) = 2x^2 - 1, \quad T_{k+1}(x) = 2x T_k(x) - T_{k-1}(x)$$ Unlike raw powers $x^k$ that bunch up near $\pm 1$ and explode outside the interval, every Chebyshev polynomial $T_k(x)$ oscillates evenly between $-1$ and $+1$ across $[-1, 1]$.
3. Fourier Sinusoids $\cos(\omega x), \sin(\omega x)$ (used in Chapters 8 and 11 for Barron spaces and SIREN wave networks): Different frequencies $\omega \ne \omega’$ are orthogonal over a period, decomposing any signal into amplitude, frequency, and phase.

7.2 Escaping the Curse of Dimensionality: Spectral Smoothness ($C_f$) and Depth ($2^D$)

Why Naive Grid Approximation Fails in High Dimensions ($\varepsilon^{-d}$)

Suppose we want to approximate an arbitrary $1$-Lipschitz function $f: [0, 1]^d \to \mathbb{R}$ to accuracy $\varepsilon = 0.1$ using a lookup table (or local histogram / nearest-neighbor grid):

• In $d = 1$ dimension, we slice $[0, 1]$ into $1/\varepsilon = 10$ bins.
• In $d = 2$ dimensions, a $10 \times 10$ grid requires $10^2 = 100$ bins.
• In $d = 100$ dimensions, a grid of resolution $0.1$ per axis requires $\varepsilon^{-d} = 10^{100}$ bins—more than the $10^{80}$ atoms in the observable universe!

This exponential explosion $M \asymp \varepsilon^{-d}$ is Richard Bellman’s Curse of Dimensionality. How can any model learn in $d = 100$ dimensions? Only if the target function $f$ possesses structural regularity that avoids filling the whole $d$-dimensional cube:

1. Spectral Smoothness (Barron’s Theorem): If $f(x)$ has a Fourier transform $\hat{f}(\boldsymbol{\omega})$ whose frequency-weighted $L^1$ norm $C_f = \int |\boldsymbol{\omega}|_1 |\hat{f}(\boldsymbol{\omega})|,d\boldsymbol{\omega}$ is finite, Andrew Barron (1993) proved that a superposition of $m$ ridge atoms $\sum_{j=1}^m a_j \sigma(\mathbf{w}_j^\top \mathbf{x} + b_j)$ achieves mean-squared error: $$\mathbb{E}!\left[\left(f(X) - f_m(X)\right)^2\right] \le \frac{C_f^2}{m}$$ Notice that the approximation rate $O(1/m)$ is independent of the ambient dimension $d$!
2. Compositional Hierarchy (Telgarsky’s $2^D$ Folding): Why use multiple layers $f_D \circ f_{D-1} \circ \dots \circ f_1(x)$ instead of one wide layer? Consider the simple piecewise-linear “tent map” on $[0, 1]$: $$\Delta(x) = \max(0, ; 1 - |2x - 1|)$$
   • A single application $\Delta(x)$ folds the interval $[0, 1]$ once, creating $1$ peak and $2^1 = 2$ linear slopes.
   • Composing it with itself $\Delta(\Delta(x))$ folds the folded interval again, creating $2$ peaks and $2^2 = 4$ linear slopes.
   • Composing $D$ layers $\Delta^{\circ D}(x)$ uses only $O(D)$ parameters, yet creates $2^{D-1}$ peaks and $2^D$ linear segments! Because addition adds oscillations ($m_1 + m_2$) whereas composition multiplies oscillations ($2^D$), any shallow network of depth $1$ or $2$ requires exponentially many neurons ($\Omega(2^{D/2})$) to approximate the sawtooth function generated by $D$ composed layers.

7.3 Gram Matrices, Eigenvalues, and Effective Dimension ($d_{\mathrm{eff}}$)

Suppose a model maps $n$ input observations $x_1, \dots, x_n$ into $m$ feature columns via an $n \times m$ feature matrix $\Phi$, where $\Phi_{ik} = \phi_k(x_i)$. How do we audit whether those $m$ features are genuinely independent directions or redundant copies of a few variables?

We form the $m \times m$ empirical Gram (feature covariance) matrix:

$$G = \frac{1}{n} \Phi^\top \Phi \qquad \left(G_{jk} = \frac{1}{n}\sum_{i=1}^n \phi_j(x_i)\phi_k(x_i)\right)$$

Let $\lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_m \ge 0$ be the eigenvalues of $G$ (each $\lambda_k$ measures the variance captured along the $k$-th principal orthogonal axis). Now recall two linear-algebra identities that can be computed in $\mathcal{O}(m^2)$ time without even running an eigenvalue solver:

1. The Trace of $G$ equals the sum of its eigenvalues: $$\mathrm{tr}(G) = \sum_{k=1}^m G_{kk} = \sum_{k=1}^m \lambda_k$$
2. The squared Frobenius norm of $G$ equals the sum of its squared eigenvalues: $$|G|_F^2 = \sum_{j=1}^m \sum_{k=1}^m G_{jk}^2 = \mathrm{tr}(G^2) = \sum_{k=1}^m \lambda_k^2$$

Taking the ratio of $(\mathrm{tr},G)^2$ to $|G|_F^2$ gives the Participation Ratio / Effective Dimension (effective_dimension in crates/stochology-lenses/src/machine.rs):

$$d_{\mathrm{eff}}(G) = \frac{(\mathrm{tr},G)^2}{|G|_F^2} = \frac{\left(\sum_{k=1}^m \lambda_k\right)^2}{\sum_{k=1}^m \lambda_k^2} \in [1, m]$$

Let us test $d_{\mathrm{eff}}(G)$ on the two extreme cases to see why it works like an X-ray of model complexity:

• Case A — Complete Collinear Collapse (all $m$ features are multiples of a single direction): Only one eigenvalue is non-zero ($\lambda_1 > 0, ; \lambda_2 = \dots = \lambda_m = 0$). Then: $$d_{\mathrm{eff}}(G) = \frac{(\lambda_1 + 0)^2}{\lambda_1^2 + 0} = \mathbf{1.0}$$ Even if $m = 10\text{,}000$, $d_{\mathrm{eff}}$ immediately reports that the representation is 1-dimensional!
• Case B — Perfect Orthonormal Basis (all $m$ features are orthogonal with equal variance $\lambda_1 = \dots = \lambda_m = c$): Then: $$d_{\mathrm{eff}}(G) = \frac{(m c)^2}{m c^2} = \frac{m^2 c^2}{m c^2} = \mathbf{m}$$ The representation utilizes $100%$ of its $m$ dimensions!

7.4 The Minimax Game: Why No Algorithm Can Beat the Information Floor

Finally, how do we judge whether an estimation error $\mathbb{E}[|\hat{\theta} - \theta|^2]$ is as small as physically possible?

Abraham Wald and Lucien Le Cam formulated statistical estimation as a zero-sum game between the Statistician and Nature:

• The Statistician chooses an estimator $\hat{\theta}(D_n)$ that maps $n$ noisy observations $D_n = (X_1, \dots, X_n)$ to a parameter guess.
• Nature chooses the true parameter $\theta \in \Theta$ to make the Statistician’s error as large as possible.

The Minimax Risk is the error of the best possible estimator against the hardest possible parameter $\theta \in \Theta$:

$$\mathcal{R}_n^\ast(\Theta) = \inf_{\hat{\theta}} \sup_{\theta \in \Theta} \mathbb{E}_\theta!\left[|\hat{\theta}(D_n) - \theta|_2^2\right]$$

Le Cam’s Two-Point Method (Intuitive Derivation)

How can we prove a lower bound on $\mathcal{R}_n^\ast(\Theta)$ that holds for every conceivable algorithm (neural networks, Bayesian posteriors, random forests, or alien computers)?

1. Pick two candidate parameters $\theta_0, \theta_1 \in \Theta$ separated by distance $\Delta = |\theta_0 - \theta_1|_2$.
2. If $\theta_0$ and $\theta_1$ are chosen close enough that the KL divergence between their $n$-sample data distributions $P_{\theta_0}^{\otimes n}$ and $P_{\theta_1}^{\otimes n}$ is small—specifically, $n , D_{\mathrm{KL}}(P_{\theta_0} ,|, P_{\theta_1}) \le \frac{1}{2}$—then the two data distributions overlap heavily.
3. Because the data distributions overlap, any estimator $\hat{\theta}$ faces an unavoidable testing error probability of at least $p_{\mathrm{err}} \ge \frac{1}{4}$, incurring squared error at least $(\Delta/2)^2$.
4. Since $D_{\mathrm{KL}}(P_{\theta_0} ,|, P_{\theta_1}) \asymp \frac{\Delta^2}{\sigma^2}$, setting $n \frac{\Delta^2}{\sigma^2} \asymp 1$ gives the maximum indistinguishable separation $\Delta^2 \asymp \frac{\sigma^2}{n}$, and across $d$ independent coordinates (by Fano’s / Assouad’s Lemma):

$$\inf_{\hat{\theta}} \sup_{\theta \in \Theta} \mathbb{E}_\theta!\left[|\hat{\theta}(D_n) - \theta|_2^2\right] \ge c , \frac{d,\sigma^2}{n}$$

With these four pillars—Orthonormal Bases in $L^2$, Compositional Folding $2^D$, Spectral Effective Dimension $d_{\mathrm{eff}}$, and Minimax Information Floors—you are ready to enter Chapter 8 and construct the $(\varepsilon, \delta)$-Almost-Perfect Machine and First-Class Authentic Model Form.

Step 3 — Auditable Laboratory in Rust and Exercises

All spectral, compositional, and minimax diagnostics developed in this chapter are implemented in pure Rust in crates/stochology-lenses/src/machine.rs and crates/stochology-lenses/src/invariance.rs:

• effective_dimension(&gram, m): Computes $\mathrm{tr}(G)$, $|G|_F^2$, and $d_{\mathrm{eff}} = (\mathrm{tr},G)^2 / |G|_F^2$ directly from any $m \times m$ Gram matrix.
• TelgarskyDepthAudit: Evaluates iterated tent maps $\Delta^{\circ D}(x)$, counting exact linear segments $2^D$ and comparing deep vs. shallow approximation error.
• hermite_basis_3(z) (invariance.rs): Evaluates the probabilists’ orthonormal Hermite basis ${\psi_1(z), \psi_2(z), \psi_3(z)}$ for nonlinear invariance testing.

Run Gate G8 and Lab 3 to verify these foundations:

cargo run --release --bin gates
cargo run --release --bin labs -- --lenses

Exercises

1. Gram-Schmidt Orthogonalization by Hand: Let $X$ take values ${-1, 0, +1}$ with equal probability $1/3$ each.
   • Verify that $\psi_0(x) = 1$ and $\psi_1(x) = \sqrt{\frac{3}{2}},x$ are orthonormal: $\mathbb{E}[\psi_0(X)^2] = 1$, $\mathbb{E}[\psi_1(X)^2] = 1$, and $\mathbb{E}[\psi_0(X)\psi_1(X)] = 0$.
   • Starting from $g(x) = x^2$, subtract its projection onto $\psi_0(x)$ ($\mathbb{E}[X^2] = \frac{2}{3}$) and normalize to construct the quadratic orthonormal atom $\psi_2(x) = \frac{3}{\sqrt{2}}!\left(x^2 - \frac{2}{3}\right)$.
2. Computing Effective Dimension $d_{\mathrm{eff}}$: Suppose a 3-feature model has diagonal Gram eigenvalues $\boldsymbol{\lambda} = (9, 1, 0)$.
   • Compute $\mathrm{tr}(G) = \sum \lambda_k$ and $|G|_F^2 = \sum \lambda_k^2$.
   • Show that $d_{\mathrm{eff}}(G) = \frac{10^2}{82} \approx 1.22$, revealing that despite having $3$ nominal features, the representation effectively uses only $1.22$ dimensions.
3. Telgarsky Sawtooth Counting: Trace the iterated tent map $\Delta(\Delta(x))$ on $x \in {0, 0.25, 0.50, 0.75, 1.0}$ where $\Delta(x) = 1 - |2x - 1|$. How many times does $\Delta(\Delta(x))$ cross the horizontal line $y = 0.5$? How many crossings does $\Delta^{\circ 10}(x)$ have?