Part 1: Linear Combinations and Convex Interpolation

Linear combinations: In a vector space, any combination $v = c_1 e_1 + c_2 e_2 + \cdots + c_d e_d$ of vectors with scalars $c_i \in \mathbb{R}$ remains in the space. The weights can be any real numbers (positive, negative, or zero). For embeddings $E_a, E_b \in \mathbb{R}^d$: \[ v = \alpha E_a + \beta E_b, \quad \alpha, \beta \in \mathbb{R}. \]

Convex combinations: A convex combination constrains weights to be non-negative and sum to 1: \[ v = \alpha E_a + (1-\alpha) E_b, \quad \alpha \in [0, 1]. \]

The set of all such combinations forms the line segment from $E_a$ to $E_b$. For $\alpha = 0$, $v = E_b$; for $\alpha = 1$, $v = E_a$; for $\alpha = 0.5$, $v$ is the midpoint. In machine learning, convex combinations ensure output vectors remain “within bounds” of input vectors—no wild extrapolations.

Soft interpolation vs. hard selection: Without convexity constraints, we might select one vector (hard choice, $\alpha \in \{0, 1\}$) or extrapolate far beyond (overshoot, $\alpha > 1$). Convex combinations provide smooth, bounded blending—essential in attention mechanisms where we interpolate across many value vectors based on continuous attention weights.

Part 2: Centering via Orthogonal Projection

The zero-mean subspace: Define $S = \{x \in \mathbb{R}^n : \mathbf{1}^\top x = 0\}$, where $\mathbf{1}^T$ is the sum operator. This is a linear subspace (closed under addition and scalar multiplication): - If $\mathbf{1}^\top x = 0$ and $\mathbf{1}^\top y = 0$, then $\mathbf{1}^\top (x + y) = 0$ (closure under addition). - If $\mathbf{1}^\top x = 0$, then $\mathbf{1}^\top (\alpha x) = 0$ (closure under scaling). - $S$ is the kernel of the linear functional $\mathbf{1}^\top$, hence dimension $(n-1)$.

The centering matrix: The orthogonal projector onto $S$ is: \[ P = I - \frac{1}{n} \mathbf{1} \mathbf{1}^\top. \]

This matrix is: - Symmetric: $P^\top = P$ - Idempotent: $P^2 = P$ (applying twice equals applying once) - Orthogonal projector: Eigenvalues are 0 or 1; range is $S$, null space is $\text{span}(\mathbf{1})$

Centering operation: For any vector $x$: \[ x_p = Px = x - \frac{1}{n} \mathbf{1}(\mathbf{1}^\top x) = x - \bar{x} \mathbf{1}, \] where $\bar{x} = \frac{1}{n} \sum_i x_i$ is the mean. Each component is shifted by the mean: $x_{p,i} = x_i - \bar{x}$. Result: $\sum_i x_{p,i} = 0$ (zero sum, zero mean).

Part 3: Why This Matters for ML

Vector space closure ensures stability: When you interpolate between embeddings (or any learned representations), staying within $\mathbb{R}^d$ ensures consistency with downstream layers. Convex combinations guarantee you don’t accidentally escape the embedding space; this is the foundation of attention, which safely mixes information from multiple sources.

Centering removes bias: In regression, PCA, and statistical analysis, centering data removes the mean—equivalent to fitting an unbiased estimator. Without centering, estimates are biased by the data offset. Projection via $P$ automates this preprocessing without explicit mean computation.

Subspaces structure learning: By projecting onto subspaces (zero-mean, orthogonal to noise, low-rank), we encode inductive bias—geometric constraints that guide learning. PCA projects onto the principal subspace (max variance); regression projects onto the column space (linear constraint). These projections are not approximations—they’re structural choices that enable efficient algorithms.

Numerical efficiency: Constructing and applying projection matrices like $P$ is $O(n^2)$ dense, but structure can be exploited. For instance, $P = I - \frac{1}{n} \mathbf{1} \mathbf{1}^\top$ is a rank-1 update, so computing $Px$ requires only $O(n)$ operations (not $O(n^2)$) via direct centering: $Px = x - \bar{x} \mathbf{1}$.

ML Examples and Patterns

Centering in PCA:

import numpy as np
from numpy.linalg import svd

X = np.random.randn(100, 10)  # 100 samples, 10 features
X_centered = X - X.mean(axis=0)  # Center each column
U, s, Vt = svd(X_centered, full_matrices=False)
# Principal components: Vt[0], Vt[1], ... (rows of Vt)

Convex combinations in attention:

def attention(Q, K, V, scale=1.0):
    scores = (Q @ K.T) * scale
    weights = softmax(scores, axis=-1)  # Convex combination weights
    output = weights @ V  # Weighted sum of values
    return output, weights

Standardization for neural networks:

def standardize(X):
    mean = X.mean(axis=0)
    std = X.std(axis=0) + 1e-8
    return (X - mean) / std

Batch normalization (mini-batch approximation):

def batch_norm(X, gamma, beta, epsilon=1e-5):
    mean = X.mean(axis=0)
    var = X.var(axis=0)
    X_norm = (X - mean) / np.sqrt(var + epsilon)
    return gamma * X_norm + beta  # Learned scale/shift

Connection to Linear Algebra Theory

Affine and convex geometry: Points in affine spaces (lines, planes, hyperplanes) are expressed via affine combinations. Convex combinations constrain us to convex sets—line segments, polytopes, convex hulls. In machine learning, convex sets encode feasible regions (e.g., simplex for probabilities, unit ball for regularization).

Orthogonal complements: The zero-mean subspace $S$ is the orthogonal complement of $\text{span}(\mathbf{1})$. Any vector $x$ decomposes uniquely as: \[ x = \bar{x} \mathbf{1} + (x - \bar{x} \mathbf{1}) = \text{const} + \text{centered}, \] where the constant part is parallel to $\mathbf{1}$ and the centered part is orthogonal. This orthogonal decomposition is the foundation of ANOVA (variance partitioning) and factor analysis.

Spectral properties of projection matrices: The eigendecomposition of $P = I - \frac{1}{n} \mathbf{1} \mathbf{1}^\top$ reveals: - Eigenvalue 0 with eigenvector $\mathbf{1}$ (constant direction—null space) - Eigenvalue 1 with eigenvectors orthogonal to $\mathbf{1}$ (range—zero-mean subspace) - $\text{rank}(P) = n - 1$, $\text{trace}(P) = n - 1$

This spectral structure is key to understanding PCA, where non-zero singular values correspond to directions of maximum variance.

Gram-Schmidt orthogonalization: Centering is the first step of Gram-Schmidt when building an orthonormal basis. Starting with $\{e_1, \ldots, e_n\}$, the first orthogonal vector is $e_1 - \bar{e}_1 \mathbf{1}$ (center it), then normalize. Subsequent vectors are orthogonalized against both constant and previous directions.

Numerical and Implementation Notes

Shape discipline: Always check: - $E_a, E_b \in \mathbb{R}^d$: Linear combination $v = \alpha E_a + (1-\alpha) E_b$ has shape $(d,)$ - $\mathbf{1} \in \mathbb{R}^{n \times 1}$: Outer product $\mathbf{1} \mathbf{1}^\top$ has shape $(n, n)$ - $P \in \mathbb{R}^{n \times n}$: Projection $Px$ has shape $(n,)$ for $x \in \mathbb{R}^n$

Gotcha 1: Affine vs. convex vs. linear combinations. Linear allows any weights; affine requires weights to sum to 1 (but can be negative); convex requires non-negative weights summing to 1. Mixing them up leads to invalid interpretations (e.g., claiming $v = 2 E_a - E_b$ is a convex combination—it’s not).

Gotcha 2: Centering matrix rank. $P = I - \frac{1}{n} \mathbf{1} \mathbf{1}^\top$ has rank $n-1$, not $n$. This means $P$ has a non-trivial null space (the constant vector $\mathbf{1}$). Rank-deficiency must be respected in numerical algorithms (e.g., avoid inverting $P$; use pseudoinverse or projection directly).

Gotcha 3: Numerical stability of centering. For very large or very small numbers, computing $\bar{x} = \frac{1}{n} \sum_i x_i$ via direct summation can lose precision (catastrophic cancellation). Use Welford’s algorithm or two-pass centering:

# Two-pass: safer
mean = x.sum() / len(x)
x_centered = x - mean
# Or use NumPy (numerically stable)
x_centered = x - np.mean(x, keepdims=True)

Gotcha 4: Outer product vs. matrix multiply. one @ one.T computes the full $n \times n$ outer product (requires $O(n^2)$ memory). For large $n$, avoid constructing $P$ explicitly; instead, apply centering directly via x - x.mean(). This is $O(n)$ memory and just as accurate.

Gotcha 5: Symmetry and stability of $P$. The centering matrix is symmetric and idempotent ($P^2 = P$), so eigenvalues are real (0 or 1). This ensures stable computation; no ill-conditioning from complex eigenvalues.

Numerical and Shape Notes

Verification checks:

• Convex combinations: For $\alpha \in [0, 1]$, plot $v(\alpha)$ on the line segment between $E_a$ and $E_b$. Verify $v(0) = E_b$, $v(1) = E_a$, $v(0.5)$ is midpoint.

• Centering properties:

  • $\mathbf{1}^\top P x = 0$ (sum is zero)
  • $\text{mean}(Px) = 0$ (mean is zero)
  • $P^2 = P$ (idempotency)
  • $P^\top = P$ (symmetry)

• Rank deficiency: $\text{rank}(P) = n - 1$. Verify via SVD: U, s, Vt = svd(P), count non-zero singular values.

Cost analysis:

• Convex combination: $O(d)$ operations for vectors in $\mathbb{R}^d$
• Centering matrix construction: $O(n^2)$ memory for full matrix storage
• Centering application (direct): $O(n)$ operations via $x - \bar{x} \mathbf{1}$
• Centering application (via $P$ matrix): $O(n^2)$ operations if materializing $P$

For large $n$, prefer direct centering over explicit $P$.

Memory efficiency:

• Full matrix $P$: $O(n^2)$ storage
• Implicit representation: $O(n)$ storage (just $n$ values)
• Use: x_centered = x - x.mean() instead of x_centered = P @ x

Pedagogical Significance

This example is the foundational demonstration of vector space and subspace structure:

Key takeaways:

1. Linear combinations are fundamental: Any point in a vector space can be expressed as a weighted sum of basis vectors.
2. Convexity constrains combinations: Weights summing to 1 (with non-negativity) ensure convex sets (line segments, polytopes).
3. Projection enforces constraints: Orthogonal projection onto subspaces (like mean-zero) is efficient and numerically stable.
4. Centering is ubiquitous in ML: Nearly all preprocessing involves centering (PCA, normalization, regression).
5. Projection matrices are elegant: Symmetric, idempotent matrices elegantly encode geometric operations.

Common misconceptions:

• “Convex combinations are just linear combinations”: No—convex requires weights in $[0, 1]$ summing to 1, ensuring closure under convex operations.
• “Centering is optional”: No—it’s essential for PCA, standardization, and proper statistical inference.
• “Projection matrices are slow”: No—they’re $O(n^2)$ dense operations, but the structure enables efficient algorithms (e.g., sparse centering for large $n$).
• “Interpolation is approximate”: No—convex combinations are exact (for finite-dimensional spaces).

Connection to other examples: Example 70 (Projection), Example 73 (Eigenvectors), Example 75 (SVD/PCA), Example 76 (Least Squares), Example 80 (Attention).

Why pedagogically powerful: It isolates two core geometric operations—linear combinations and projection—in minimal code. The convex interpolation shows intuition (moving between points on a line segment); the centering projection shows power (enforcing zero-sum constraint via matrix multiplication). These operations appear in every ML algorithm: attention (convex combinations), PCA (projection + decomposition), regression (centering + solving). Students see that vector spaces are not abstract—they’re the foundation of modern ML’s geometric operations. This is the gateway to understanding subspaces, projections, and decompositions that dominate all subsequent chapters.

• Shape discipline: check dimensions before manipulating formulas.
• Numerical note: prefer stable primitives (lstsq, QR/SVD, Cholesky for SPD) over explicit inverses.
• Interpretation: relate algebraic steps to geometry (subspaces, projections) and to ML behavior (generalization, stability).