Real systems operate with incomplete information:

• Temperature sensor reads \(72^\circ\text{F} \pm 2^\circ\text{F}\)
• Radar measures distance with noise
• Stock price reflects unknown future earnings
• MRI image contains artifacts

Objective: Given measurements (\(X\)), estimate unknowns (\(Y\))

Uncertainty is inherent, not a nuisance

• Measurement noise
• Model uncertainty
• Finite samples
• Quantization effects

Many estimates of \(Y\) are possible - best needs a definition

Problem:

• \(Y\): quantity of interest (unknown)
• \(X\): observation (known)
• \((X, Y)\): jointly distributed random variables

Predictor function: \(g: \mathbb{R} \to \mathbb{R}\)

Example: Room temperature estimation

• \(Y\): true temperature
• \(X\): sensor reading = \(Y + N\)
• \(N\): measurement noise
• \(g(X) =\) ? Best guess for \(Y\) given reading \(X\)

Among all possible functions \(g\), which one is “best”?

Need:

1. What we mean by “best” (loss function)
2. How to deal with randomness (averaging)

Loss function \(\ell(y, \hat{y})\) measures prediction quality

Common choices:

Risk: Expected loss over joint distribution

Goal: Find \(g^* = \arg\min_g R(g)\)

Squared error leads to the expected value (mean), absolute error the median

Mathematical advantages:

1. Differentiable:

   \[\frac{d}{d\hat{y}}(y - \hat{y})^2 = -2(y - \hat{y})\]

   Smooth objective

2. Unique minimum: Strictly convex \(\Rightarrow\) no local minima

3. Closed-form solutions: Often analytically tractable

4. Decomposition:

   \[\text{MSE} = \text{Bias}^2 + \text{Variance}\]

   Separates systematic error from random scatter

Statistical connection:

Under Gaussian noise \(N \sim \mathcal{N}(0, \sigma^2)\):

Maximum likelihood estimation:

MSE \(\leftrightarrow\) Gaussian MLE

Definition: for estimator \(g\)

Expanding the expectation:

Empirical MSE (from data):

Properties:

• Always non-negative: \(\text{MSE} \geq 0\)
• Zero iff perfect prediction: \(\text{MSE} = 0 \iff P(Y = g(X)) = 1\)
• Units: \([\text{MSE}] = [Y]^2\)

Other forms:

• RMSE = \(\sqrt{\text{MSE}}\) (same units as \(Y\))
• Normalized MSE = MSE/Var(Y)

Hierarchy of function classes:

1. Constant: \(\hat{Y} = c\)

   • Ignores observation X
   • Optimal: \(c^* = \mathbb{E}[Y]\)
   • MSE = Var(Y)

2. Linear (affine): \(\hat{Y} = aX + b\)

   • Two parameters
   • Needs only first and second moments

3. Polynomial: \(\hat{Y} = \sum_{k=0}^p a_k X^k\)

   • Needs moments up to order \(2p\)
   • Overfitting risk

4. Unrestricted: \(\hat{Y} = g(X)\)

   • Any measurable function
   • Needs the full conditional \(p(y|x)\)

Each step up fits more but requires knowing more

Definition: A linear estimator has the form

where \(a, b \in \mathbb{R}\) are constants.

• \(\hat{Y} = 3X + 2\): linear in \(X\)
• \(\hat{Y} = \beta X^2\): not linear - quadratic in \(X\), though linear in \(\beta\)

Parameters:

• \(a\): slope/gain/sensitivity
• \(b\): offset/bias/intercept

Special cases:

• \(b = 0\): Proportional estimator \(\hat{Y} = aX\)
• \(a = 0\): Constant estimator \(\hat{Y} = b\)
• \(a = 1, b = 0\): Direct use \(\hat{Y} = X\)

Affine, strictly: superposition holds only for \(b = 0\)

Vector case: \(\hat{\mathbf{y}} = \mathbf{A}\mathbf{x} + \mathbf{b}\)

Mean \(\mathbb{E}[Y]\): baseline prediction

• Best constant; what to predict without observing \(X\)

Variance \(\text{Var}(Y)\): the error to beat

• MSE of the baseline; total variation to explain

Covariance \(\text{Cov}(X,Y)\): linear link

• Sign sets the slope direction. If zero - no linear relationship improves

Correlation \(\rho \in [-1, 1]\): scale-free link

• \(|\rho| = 1\): exact linear dependence
• \(\rho^2\) = fraction of Var(Y) a line removes

These moments completely determine the optimal linear estimator

Additive noise model:

• \(Y\): true signal (what we want)
• \(N\): noise (corruption)
• \(X\): observation (what we get)
• Independence: \(Y \perp N\)

Signal-to-Noise Ratio (SNR):

For zero-mean:

In dB: \(\text{SNR}_{\text{dB}} = 10\log_{10}(\text{SNR})\)

Linear estimation floor:

• Residual error at every finite SNR
• Equals the overall optimum for Gaussian \(Y, N\); lower is possible otherwise

Sample space \(\Omega\): Set of all possible outcomes

Random variable \(X: \Omega \to \mathbb{R}\)

Maps each outcome to a real number.

Notation convention:

• \(X\) (uppercase): The random variable (a function)
• \(x\) (lowercase): A specific realized value

Discrete example: Die roll

• \(\Omega = \{\omega_1, \omega_2, \omega_3, \omega_4, \omega_5, \omega_6\}\)
• \(X(\omega_i) = i\)
• \(P(X = 3) = 1/6\)

Continuous example: Measurement noise

• \(\Omega\) = all possible noise realizations
• \(X(\omega)\) = voltage at time \(t\)
• \(P(X = 1.5)\) = 0, but \(P(1.4 < X < 1.6) > 0\)

Joint distribution \(p(x, y)\):

Probability (density) that \(X = x\) AND \(Y = y\) simultaneously.

For discrete: \(P(X = x, Y = y)\)

For continuous: \(p(x,y)\) where

What the joint determines:

• How likely are specific \((x, y)\) pairs?
• Are \(X\) and \(Y\) related or independent?
• Everything about marginals and conditionals

Independence means:

Joint factors into product of marginals.

Marginal distribution: Integrate out the unused variable

Conditional distribution: Slice and renormalize

Bayes’ rule is just rearranging:

Conditioning is just:

1. Start with joint \(p(x,y)\)
2. Fix \(x\) to get a slice
3. Divide by \(p(x)\) to make it integrate to 1

Discrete:

Continuous:

Interpretation: Center of mass of the distribution

Expectation of a function:

Example: Die roll

\(\mathbb{E}[X] = 1 \cdot \frac{1}{6} + 2 \cdot \frac{1}{6} + \cdots + 6 \cdot \frac{1}{6} = 3.5\)

3.5 is not a possible outcome - it is the long-run average

Linearity:

This holds even if \(X\) and \(Y\) are dependent.

Why? Just rearranging sums/integrals:

Example: Sum of two dice

\(\mathbb{E}[X_1 + X_2] = \mathbb{E}[X_1] + \mathbb{E}[X_2] = 3.5 + 3.5 = 7\)

i.e., Don’t need to enumerate all 36 outcomes.

Definition:

where \(\mu = \mathbb{E}[X]\)

Equivalent form:

When to use which:

• Definition: Intuition (average squared deviation from mean)
• Equivalent form: Calculation (often simpler)

Standard deviation: \(\sigma = \sqrt{\text{Var}(X)}\)

Same units as \(X\) (variance has squared units)

Properties:

• \(\text{Var}(X) \geq 0\)
• \(\text{Var}(aX + b) = a^2 \text{Var}(X)\)
• Adding a constant shifts the mean, not the spread

Definition:

Equivalent form:

Interpretation:

• \(\text{Cov} > 0\): When \(X\) is above its mean, \(Y\) tends (on average) to be above its mean
• \(\text{Cov} < 0\): When \(X\) is above its mean, \(Y\) tends to be below its mean
• \(\text{Cov} = 0\): No linear relationship

Correlation (normalized covariance):

\(\text{Cov}(X,Y) = 0\) does NOT imply independence.

\(X \sim \mathcal{N}(0,1)\) with \(Y = X^2\): clearly dependent, but \(\text{Cov}(X, Y) = 0\).

Exception: jointly Gaussian \((X,Y)\) - zero covariance implies independence

For two random variables:

If uncorrelated (\(\text{Cov}(X,Y) = 0\)):

Compare with (linear) expectation:

• \(\mathbb{E}[X + Y] = \mathbb{E}[X] + \mathbb{E}[Y]\) always
• \(\text{Var}(X + Y) = \text{Var}(X) + \text{Var}(Y)\) only if uncorrelated

General form:

Appears in portfolio diversification, error propagation, averaged measurements

Joint distribution \((X, Y) \sim p(x,y)\) contains all information.

Bayes’ rule:

Once we observe \(X = x\), the distribution of \(Y\) changes from \(p(y)\) to \(p(y|x)\).

Example: Temperature sensor, \(X = Y + N\)

• Prior: \(Y \sim \mathcal{N}(70, 10^2)\); noise \(N \sim \mathcal{N}(0, 5^2)\)
• Observe: \(X = 75\) (sensor reading)
• Posterior: \(Y|X{=}75 \sim \mathcal{N}(74, 4.5^2)\)

Conditioning reduces uncertainty on average: \(\mathbb{E}[\text{Var}(Y|X)] \leq \text{Var}(Y)\) - a particular observation can widen the spread

Discrete case:

Definition: The conditional expectation of \(Y\) given \(X = x\) is:

Discrete case:

Continuous case:

Facts:

1. \(\mathbb{E}[Y|X=x]\) is a number (for fixed \(x\))
   • expected value when \(X\) equals \(x\)
2. \(g(x) = \mathbb{E}[Y|X=x]\) is a deterministic function
3. \(\mathbb{E}[Y|X]\) is a random variable (function of \(X\))

Example: \(Y = X + N\), \(N \sim \mathcal{N}(0,1)\), independent \(X\) and \(N\)

Example: Binary communication channel

• \(X \in \{0, 1\}\): transmitted bit
• \(Y \in \{0, 1\}\): received bit
• Channel flips bit with probability \(p = 0.1\)

Joint distribution:

Conditional distributions:

Conditional expectations:

MSE for different predictors:

• \(\hat{X} = \mathbb{E}[X|Y]\): MSE = 0.09
• \(\hat{X} = Y\) (identity): MSE = 0.10
• \(\hat{X} = 0.5\) (constant): MSE = 0.25

Result: \(\mathbb{E}[X|Y]\) achieves minimum MSE

Joint Gaussian: \((X, Y) \sim \mathcal{N}(\mu, K)\)

Parameters:

Conditional mean:

Conditional variance:

Linear in \(x\), spread independent of \(x\)

Figure: \(\mu = (1, 2)\), \(\sigma_X = 2\), \(\sigma_Y = 3\); at \(\rho = 0.8\) the slope is \(1.2\) and the spread \(1.8\), at \(\rho = 0\) the slope is \(0\) and the spread the full \(3\)

Computing \(\mathbb{E}[Y|X=x]\) requires \(p(y|x)\)

From Bayes:

When tractable:

1. Known parametric families (Gaussian, exponential)
2. Discrete with small state space
3. Special structures (independence, Markov)

When intractable (often no closed form):

1. Complex nonlinear relationships
2. High dimensions
3. Unknown distributions

Example: Nonlinear sensor

where \(N \sim \mathcal{N}(0, 0.1)\)

Computing \(\mathbb{E}[Y|X=x]\) requires:

1. Joint density \(p(x,y)\)
2. Marginal \(p(x) = \int p(x,y)dy\)
3. Conditional \(p(y|x) = p(x,y)/p(x)\)
4. Integration \(\mathbb{E}[Y|X=x] = \int y p(y|x) dy\)

Law of Total Expectation:

Proof:

where \(g(x) = \mathbb{E}[Y|X=x]\)

Intuition: Average of conditional averages = unconditional average

Example: Class grades

• Section A: mean 85, 30 students
• Section B: mean 75, 20 students
• Overall mean = \(\frac{30 \cdot 85 + 20 \cdot 75}{50} = 81\)

Property: For any function \(h(X)\):

Proof: Fix \(X = x\). Then \(h(X) = h(x)\) is a constant:

Special cases:

1. \(\mathbb{E}[X \cdot Y | X] = X \cdot \mathbb{E}[Y|X]\)
2. \(\mathbb{E}[f(X) + Y | X] = f(X) + \mathbb{E}[Y|X]\)
3. \(\mathbb{E}[X^2Y | X] = X^2\mathbb{E}[Y|X]\)

Example: Signal processing

Only \(\mathbb{E}[Y|X]\) is needed, not \(\mathbb{E}[XY|X]\)

But functions of \(Y\) do not factor out:

Definition:

Computing formula:

Measures remaining uncertainty after observing \(X\)

Law of Total Variance:

• First term: Average conditional variance (irreducible)
• Second term: Variance of conditional means (explained)

Interpretation:

Minimum MSE: \(\mathbb{E}[\text{Var}(Y|X)]\), and no predictor does better

Goal: Find the best predictor of \(Y\) given \(X\)

Function space:

Optimization problem:

Infinite-dimensional optimization

• Search over all possible functions
• No parametric form assumed
• No finite parameter vector to solve for

Strategy: Decompose the problem by conditioning on \(X\)

1. Fix \(X = x\), solve pointwise optimization
2. Combine solutions for all \(x\)
3. Verify global optimality

Decomposition:

Why this helps:

• Outside expectation: Average over \(X\)
• Inside expectation: For each fixed \(X = x\)

When \(X = x\) is fixed:

• \(g(X) = g(x)\) is just a number
• \(Y|X=x\) has distribution \(p(y|x)\)
• We minimize: \(\mathbb{E}[(Y - g(x))^2|X=x]\)

This transforms the problem:

• From: Find optimal function \(g\)
• To: For each \(x\), find optimal constant \(g(x)\)

Solution approach:

1. Fix \(x\), find best constant predictor
2. This gives us \(g^*(x)\) for each \(x\)
3. The function \(g^*\) is our MMSE estimator

Step 1: Express MSE using conditional expectation

Step 2: For fixed \(X = x\), \(g(X) = g(x)\) is a constant

where \(a = g(x)\)

Step 3: Minimize over \(a\)

Solution: \(a^* = \mathbb{E}[Y|X=x]\)

Step 4: Since this holds for all \(x\):

Therefore:

Orthogonality principle: Optimal error orthogonal to any function of \(X\):

for any measurable \(h\).

1. Uniqueness: Only one function satisfies this \(\Rightarrow\) unique MMSE

2. Optimality test: If \(\mathbb{E}[\epsilon \cdot h(X)] \neq 0\), can reduce MSE by adjusting estimate in direction of \(h(X)\)

3. Computational foundation:

   • Linear case \(\to\) normal equations
   • Adaptive filters \(\to\) orthogonalize error
   • Kalman filter \(\to\) innovation orthogonality

4. Geometric meaning: MMSE = projection in Hilbert space

Proof: \(\mathbb{E}[(Y - \mathbb{E}[Y|X])|X] = 0\) by definition, multiplying by \(h(X)\) preserves this.

Cannot extract more information from \(X\)

We solved pointwise: For each \(x\), found \(g^*(x) = \mathbb{E}[Y|X=x]\)

Question: Is this globally optimal over all functions?

Two concerns:

1. We optimized separately at each \(x\)
2. Maybe coupling across different \(x\) values helps?

MSE decomposes additively

Each term \(\mathbb{E}[(Y - g(x))^2|X=x]\) depends only on \(g(x)\), not on \(g(x')\) for \(x' \neq x\).

Therefore:

• Minimizing each term separately minimizes the sum
• No coupling can improve the solution
• Pointwise optimization = Global optimization

Idea: Prediction at \(x\) doesn’t help prediction at \(x'\)

Claim: No function can beat \(\mathbb{E}[Y|X]\)

Proof: For any function \(g\):

Add and subtract \(\mathbb{E}[Y|X]\):

Expand the square:

The cross term vanishes:

Because \(\mathbb{E}[Y|X] - g(X)\) is a function of \(X\) and:

for any \(h(X)\) (orthogonality).

Therefore:

Minimum achievable MSE:

Result:

Proof:

For fixed \(X = x\):

Therefore:

Irreducible: no predictor can remove conditional variance

Special cases:

• \(X\) and \(Y\) independent: \(\text{MSE}_{\min} = \text{Var}(Y)\)
• \(Y = f(X)\) deterministic: \(\text{MSE}_{\min} = 0\)

A single outlier can dominate the sample MSE:

If \(y_k\) is an outlier: \((y_k - \hat{y}_k)^2 \gg (y_i - \hat{y}_i)^2\) for \(i \neq k\)

Effect on the estimate:

• Under contamination, the conditional mean shifts toward the outlier component
• The fit stops representing the majority of data

Example: Sensor failure

• 99 readings: \(Y \approx X + \varepsilon\), \(\varepsilon \sim \mathcal{N}(0, 0.1^2)\)
• 1 reading: \(Y = 100\) (sensor spike)

The mean absorbs the spike; typical-case error grows.

Alternative loss functions:

• Absolute error: \(|Y - \hat{Y}|\) (median)
• Huber loss: Quadratic for small errors, linear for large
• Trimmed MSE: Ignore largest errors

When outliers are present:

1. Median regression (LAD):

   \[\min_g \mathbb{E}[|Y - g(X)|]\]

   Solution: \(g^*(x) = \text{median}(Y|X=x)\)

2. Huber regression:

   \[\min_g \mathbb{E}[\ell_\delta(Y - g(X))]\]

   where \(\ell_\delta(e) = \begin{cases} \frac{1}{2}e^2 & |e| \leq \delta \\ \delta|e| - \frac{\delta^2}{2} & |e| > \delta \end{cases}\)

3. Trimmed mean: Remove top/bottom α% before computing \(\mathbb{E}[Y|X]\)

Definition: For vectors \(\mathbf{x}, \mathbf{y} \in \mathbb{R}^n\)

Geometric interpretation:

where \(\theta\) is the angle between vectors.

Special cases:

• \(\theta = 0^\circ\): \(\langle \mathbf{x}, \mathbf{y} \rangle = \|\mathbf{x}\|\|\mathbf{y}\|\) (aligned)
• \(\theta = 90^\circ\): \(\langle \mathbf{x}, \mathbf{y} \rangle = 0\) (orthogonal)
• \(\theta = 180^\circ\): \(\langle \mathbf{x}, \mathbf{y} \rangle = -\|\mathbf{x}\|\|\mathbf{y}\|\) (opposed)

Norm from inner product:

Problem: Given \(\mathbf{y}\) and subspace \(\mathcal{S}\), find \(\hat{\mathbf{y}} \in \mathcal{S}\) that minimizes

Solution: \(\hat{\mathbf{y}} = \text{Proj}_{\mathcal{S}}(\mathbf{y})\)

Projection onto a line (1D subspace):

Given direction \(\mathbf{u}\) with \(\|\mathbf{u}\| = 1\):

Projection onto span of \(\{\mathbf{u}_1, \mathbf{u}_2\}\):

If \(\mathbf{u}_1 \perp \mathbf{u}_2\) and both unit vectors:

The error is what remains:

Theorem: \(\hat{\mathbf{y}}\) minimizes \(\|\mathbf{y} - \hat{\mathbf{y}}\|^2\) over \(\mathcal{S}\)

if and only if

Why orthogonality implies optimality:

Suppose error \(\mathbf{e} = \mathbf{y} - \hat{\mathbf{y}}\) is not orthogonal to \(\mathcal{S}\).

Then \(\mathbf{e}\) has a component along \(\mathcal{S}\).

Moving \(\hat{\mathbf{y}}\) in that direction reduces \(\|\mathbf{e}\|\).

Contradiction: \(\hat{\mathbf{y}}\) wasn’t optimal.

Orthogonality conditions:

For \(\mathcal{S} = \text{span}\{\mathbf{v}_1, ..., \mathbf{v}_k\}\):

This gives \(k\) equations to solve for \(\hat{\mathbf{y}}\).

Random variable inner product:

Define \(\langle X, Y \rangle = \mathbb{E}[XY]\)

For zero-mean variables:

Orthogonal random variables:

(For zero-mean: \(\text{Cov}(X,Y) = 0\))

The connection:

This is why linear algebra solves estimation problems.

Curse of dimensionality:

To compute \(\mathbb{E}[Y|X]\), need \(p(y|x)\)

Density estimation convergence:

• Rate: \(N^{-4/(d+4)}\) for \(d\)-dimensional data
• 10% relative error: \(d{=}10 \to N \approx 10^6\); \(d{=}100 \to N \approx 10^{26}\)

Consequence:

• Modern data is high-dimensional
• Never have enough samples for nonparametric methods
• Must accept suboptimality for tractability

Linear class advantages:

• Only need second moments: \(O(d^2)\) parameters
• Sample complexity: \(O(d^2)\) vs \(O(e^d)\)

MMSE requires \(p(y|x)\) to compute \(\mathbb{E}[Y|X]\)

Reality: We rarely know conditional distributions

What we often have:

• Sample data: \((x_1, y_1), ..., (x_n, y_n)\)
• First and second moments

Practical solution: Restrict to linear predictors

1. Only need means, variances, covariance
2. Optimal for Gaussian
3. Optimal whenever \(\mathbb{E}[Y|X]\) is linear

Function class:

New optimization problem:

From infinite to finite:

• Before: Search over all functions
• Now: Search over 2 parameters

Expanding the MSE:

MSE is quadratic in \((a, b)\)

• Unique minimum (if Var\((X) > 0\))
• Closed-form solution via derivatives
• No iterative optimization needed

Step 1: Find optimal \(b\) for fixed \(a\)

Take derivative with respect to \(b\):

Solving for \(b\):

Interpretation:

• Offset ensures zero mean error
• Forces predictor through \((\mathbb{E}[X], \mathbb{E}[Y])\)
• Adjusts for non-zero means

Substituting back:

Step 2: Find optimal \(a\) using \(b^* = \mathbb{E}[Y] - a\mathbb{E}[X]\)

Substitute into MSE:

Define centered variables:

• \(\tilde{Y} = Y - \mathbb{E}[Y]\)
• \(\tilde{X} = X - \mathbb{E}[X]\)

Then: \(\text{MSE}(a) = \mathbb{E}[(\tilde{Y} - a\tilde{X})^2]\)

Take derivative:

Solution:

Note: \(\mathbb{E}[\tilde{X}\tilde{Y}] = \text{Cov}(X,Y)\) and \(\mathbb{E}[\tilde{X}^2] = \text{Var}(X)\)

Alternative approach: Require error orthogonal to predictors

From MMSE theory: optimal error satisfies

for functions \(h\) in the predictor class.

For linear predictors \(\hat{Y} = aX + b\):

Predictor class = span\(\{1, X\}\)

Orthogonality conditions:

1. \(\mathbb{E}[(Y - aX - b) \cdot 1] = 0\)

   \[\mathbb{E}[Y] - a\mathbb{E}[X] - b = 0\]
   \[\boxed{b = \mathbb{E}[Y] - a\mathbb{E}[X]}\]

2. \(\mathbb{E}[(Y - aX - b) \cdot X] = 0\)

   \[\mathbb{E}[XY] - a\mathbb{E}[X^2] - b\mathbb{E}[X] = 0\]

Substitute \(b\) and solve:

Same answer, different route

• Calculus: minimize MSE directly
• Orthogonality: project onto subspace

Orthogonality generalizes to vectors without derivatives.

Complete solution:

Alternative forms:

Using correlation \(\rho = \frac{\text{Cov}(X,Y)}{\sigma_X \sigma_Y}\):

Standardized form: If \(\mathbb{E}[X] = \mathbb{E}[Y] = 0\) and \(\sigma_X = \sigma_Y = 1\):

Minimum MSE:

Explained variance:

Correlation measures linear predictability, not dependence

Properties:

1. Only needs first and second moments
2. Always exists (if Var\((X) > 0\))
3. Unique solution
4. Orthogonal errors: \(\mathbb{E}[(Y - \hat{Y})X] = 0\)

Restriction can only lose:

Performance gap:

Measures nonlinearity of \(\mathbb{E}[Y|X]\).

When are they equal?

if and only if \(\mathbb{E}[Y|X]\) is linear in \(X\).

For jointly Gaussian \((X,Y)\):

• \(\mathbb{E}[Y|X]\) is linear
• LMMSE = MMSE
• No performance loss from restriction

Uniform-Quadratic example:

• \(X \sim \text{Uniform}(-2, 2)\)
• \(Y = X^2 + N\), \(N \sim \mathcal{N}(0, 0.5^2)\)

MMSE estimator:

Nonlinear in \(X\)

Linear MMSE (suboptimal): slope \(\text{Cov}(X,Y)/\text{Var}(X) = \mathbb{E}[X^3]/\text{Var}(X) = 0\)

Performance gap:

• MSE\(_{\text{MMSE}}\) = \(\sigma_N^2\) = 0.25
• MSE\(_{\text{linear}}\) = Var(\(X^2\)) + \(\sigma_N^2 \approx 1.67\)

The gap is Var(\(X^2\)) - the part of \(\mathbb{E}[Y|X]\) no line can follow

MMSE (unrestricted):

LMMSE (restricted):

LMMSE error may still correlate with \(X^2, X^3, \sin(X), ...\)

This correlation is unexploited information—structure in \((X, Y)\) that linear predictors cannot capture.

When LMMSE achieves MMSE:

If \(\mathbb{E}[Y|X]\) is already linear in \(X\):

• LMMSE error \(\perp\) all \(h(X)\) automatically
• No nonlinear structure to exploit
• Gaussian \((X,Y)\) guarantees this

Bivariate Gaussian \((X, Y) \sim \mathcal{N}(\mu, K)\)

Parameters:

where \(k_{XY} = \rho\sigma_X\sigma_Y\)

Joint density:

where \(z_x = \frac{x-\mu_X}{\sigma_X}\) and \(z_y = \frac{y-\mu_Y}{\sigma_Y}\) are standardized variables

Fully determined by first and second moments

• 5 parameters: \(\mu_X, \mu_Y, \sigma_X^2, \sigma_Y^2, \rho\)
• All higher moments determined by these

Result: \(Y|X=x\) is Gaussian

Conditional mean:

Conditional variance (constant):

Therefore:

Observations:

1. \(\mathbb{E}[Y|X=x]\) is linear in \(x\)
2. \(\text{Var}(Y|X=x)\) does not depend on \(x\)
3. Conditional distribution is still Gaussian

Endpoints:

• \(\rho = 0\): \(\mathbb{E}[Y|X=x] = \mu_Y\) - no information from observation
• \(|\rho| = 1\): \(\text{Var}(Y|X) = 0\) - perfect prediction

Regression line:

passes through \((\mu_X, \mu_Y)\) with slope \(\rho\sigma_Y/\sigma_X\)

Method 1: Complete the square

Start with joint density, condition on \(X = x\):

Method 2: Linear projection

Find \(a, b\) minimizing \(\mathbb{E}[(Y - aX - b)^2]\):

• \(a^* = \text{Cov}(X,Y)/\text{Var}(X) = \rho\sigma_Y/\sigma_X\)
• \(b^* = \mathbb{E}[Y] - a^*\mathbb{E}[X] = \mu_Y - a^*\mu_X\)

Method 3: Schur complement

Using block matrix operations on \(K\):

(all methods give same result)

For jointly Gaussian \((X, Y)\):

Why equal?

• MMSE: \(\hat{Y}_{\text{MMSE}} = \mathbb{E}[Y|X]\)
• For Gaussian: \(\mathbb{E}[Y|X]\) is linear
• LMMSE: Best linear predictor

Minimum MSE:

Implications:

1. No need to consider nonlinear predictors
2. Second moments sufficient for optimal prediction
3. Closed-form solution

Maximum entropy property: Among all distributions with given mean and covariance, Gaussian has maximum entropy

Central Limit Theorem: Sum of many independent effects \(\to\) Gaussian

Preserved under linear operations: If \((X,Y)\) Gaussian and \(Z = aX + bY + c\):

• \(Z\) is Gaussian
• \((X,Z)\) jointly Gaussian
• \((Y,Z)\) jointly Gaussian

Sufficient statistics: For Gaussian, sample mean and covariance are sufficient

• No information lost by summarizing with \((\bar{X}, \bar{Y}, S_{XX}, S_{YY}, S_{XY})\)

Problem: the statistics are unknown

LMMSE needs: \(\text{Cov}(X,Y)\) and \(\text{Var}(X)\)

Solution: Learn from streaming data

Population gradient:

Widrow-Hoff: replace the expectation with its one-sample estimate

\(x_i y_i\), \(x_i^2\): rank-one instantaneous estimates of \(\mathbb{E}[XY]\), \(\mathbb{E}[X^2]\)

LMS update rule:

where \(e_i = y_i - \hat{y}_i\) is prediction error and \(\eta\) the step size (sometimes write \(\mu\))

Convergence: \(a_i \to a^*_{\text{LMMSE}}\) as \(i \to \infty\)

Convergence condition (in the mean):

Too large \(\eta\) \(\Rightarrow\) divergence

Steady-state error:

Misadjustment (small \(\eta\)): \(M = \frac{\eta \mathbb{E}[X^2]}{2}\)

Trade-off:

• Small \(\eta\): Slow convergence, low steady-state error
• Large \(\eta\): Fast convergence, high steady-state error

Time constant:

iterations to converge

Advantages:

• No matrix operations
• Adapts to changing statistics
• Simple hardware implementation

Relation: LMS = stochastic gradient descent for MSE

Theory (Population)

Given joint distribution \(p(x,y)\):

Linear MMSE solution:

Practice (Sample)

Given data \(\{(x_i, y_i)\}_{i=1}^n\):

Sample estimates:

Convergence: \(\hat{a} \to a^*\) as \(n \to \infty\) (law of large numbers)

This is linear regression

Population risk (unknown):

Empirical risk (computable):

Optimization:

Sample optimization gives sample LMMSE

Linear model limitations:

Can only model linear relationships

Feature transformation:

where \(\boldsymbol{\phi}(x) = [\phi_0(x), \phi_1(x), ..., \phi_K(x)]^T\)

Still linear MMSE in feature space:

• Design matrix: \(\Phi_{ij} = \phi_j(x_i)\)
• Solution: \(\mathbf{w}^* = (\Phi^T\Phi)^{-1}\Phi^T\mathbf{y}\)

Example: Polynomial features

Now can fit parabolas while still using linear methods

Batch gradient descent:

Gradients:

Update:

One sample per step recovers LMS: the single-sample gradient step is exactly the LMS update; minibatches interpolate between the two

LMMSE \(\neq\) MMSE when \(\mathbb{E}[Y|X]\) is nonlinear.

Single neuron:

where \(\sigma\) is activation (ReLU, sigmoid, etc.)

Without activation: Linear regression

With activation: Nonlinear transform

Deep network: Composition of layers

Objective: \(\frac{1}{n}\sum_i (y_i - \hat{y}_i)^2\) (same MSE)

Backpropagation: Chain rule for gradients

Random vector: \(\mathbf{X} = [X_1, X_2, ..., X_p]^T\)

Mean vector:

Covariance matrix:

Element structure:

Properties:

• Symmetric: \(\mathbf{K}_{XX} = \mathbf{K}_{XX}^T\)
• Positive semi-definite: \(\mathbf{a}^T \mathbf{K}_{XX} \mathbf{a} \geq 0\)
• Diagonal elements = variances
• Off-diagonal = covariances

Definition: \(\mathbf{A}\) is positive definite if

Equivalent conditions:

• All eigenvalues \(\lambda_i > 0\)
• \(\mathbf{A} = \mathbf{B}^T\mathbf{B}\) for some invertible \(\mathbf{B}\)
• All leading principal minors positive

Geometric interpretation:

The set \(\{\mathbf{x} : \mathbf{x}^T \mathbf{A} \mathbf{x} = 1\}\) is an ellipsoid.

• Principal axes: eigenvectors of \(\mathbf{A}\)
• Axis lengths: \(1/\sqrt{\lambda_i}\)

Covariance ellipse: for Gaussian data, \((\mathbf{x} - \boldsymbol{\mu})^T \mathbf{K}_{XX}^{-1} (\mathbf{x} - \boldsymbol{\mu}) = c^2\) contains about 95% of the data at \(c \approx 2.45\) - the shape of a data cloud is its covariance

Scalar case:

Given: \(X\) (single predictor), predict \(Y\)

Vector case:

Given: \(\mathbf{X} = [X_1, X_2, ..., X_p]^T\) (multiple predictors)

Example: Predict temperature \(Y\) from:

• \(X_1\) = humidity sensor
• \(X_2\) = pressure sensor
• \(X_3\) = wind speed

Matrix notation:

where \(\mathbf{a} = [a_1, a_2, ..., a_p]^T\) are weights

Minimize MSE over linear predictors:

Taking derivatives:

Substituting \(b\) and simplifying:

Define:

• \(\mathbf{K}_{XX} = \mathbb{E}[\mathbf{X}\mathbf{X}^T] - \mathbb{E}[\mathbf{X}]\mathbb{E}[\mathbf{X}]^T\) (covariance matrix)
• \(\mathbf{k}_{XY} = \mathbb{E}[\mathbf{X}Y] - \mathbb{E}[\mathbf{X}]\mathbb{E}[Y]\) (cross-covariance vector)

Reminder (vector derivatives, \(\mathbf{A}\) symmetric):

Normal equations:

Solution (if \(\mathbf{K}_{XX}\) invertible):

LMMSE predictor:

Minimum MSE:

Variance reduction = \(\mathbf{k}_{XY}^T \mathbf{K}_{XX}^{-1} \mathbf{k}_{XY} \geq 0\)

• \(\mathbf{K}_{XX}^{-1}\) is positive definite
• Adding predictors never raises the MSE; zero gain only when \(\mathbf{k}_{XY} = \mathbf{0}\)

Column space perspective:

Data matrix columns: \(\mathbf{x}_1, \mathbf{x}_2, ..., \mathbf{x}_p\)

LMMSE = Projection:

Orthogonality:

Equivalently: \(\mathbf{X}^T(\mathbf{y} - \mathbf{X}\mathbf{a}) = \mathbf{0}\) - the normal equations in sample form, \(\mathbf{X}^T\mathbf{X}\mathbf{a} = \mathbf{X}^T\mathbf{y}\)

Projection matrix:

Properties:

• \(\mathbf{P}^2 = \mathbf{P}\) (idempotent)
• \(\mathbf{P}^T = \mathbf{P}\) (symmetric)
• \(\text{rank}(\mathbf{P}) = p\) (dimension of \(\mathcal{S}\))

Joint Gaussian distribution:

\(\begin{bmatrix} \mathbf{X} \\ \mathbf{Y} \end{bmatrix} \sim \mathcal{N}\left(\begin{bmatrix} \boldsymbol{\mu}_X \\ \boldsymbol{\mu}_Y \end{bmatrix}, \begin{bmatrix} \mathbf{K}_{XX} & \mathbf{K}_{XY} \\ \mathbf{K}_{YX} & \mathbf{K}_{YY} \end{bmatrix}\right)\)

Probability density:

where \(\mathbf{z} = \begin{bmatrix} \mathbf{x} - \boldsymbol{\mu}_X \\ \mathbf{y} - \boldsymbol{\mu}_Y \end{bmatrix}\)

Linear operations preserve Gaussianity

If \(\mathbf{Z} = \mathbf{A}\mathbf{X} + \mathbf{b}\), then:

Marginals are Gaussian:

Given joint Gaussian, conditional is also Gaussian:

Conditional mean (MMSE estimator):

Conditional covariance (error covariance):

The subtracted term is the Schur complement - the uncertainty removed by observing \(\mathbf{X}\)

Observations:

1. Conditional mean is linear in \(\mathbf{x}\)
2. Conditional covariance does not depend on \(\mathbf{x}\)
3. For Gaussian: MMSE = Linear MMSE

Direct inversion issues:

1. Ill-conditioning: When predictors highly correlated

   • \(\text{cond}(\mathbf{K}_{XX}) = \frac{\lambda_{\max}}{\lambda_{\min}} \gg 1\)
   • Small changes \(\to\) large parameter changes

2. Rank deficiency: perfect collinearity, or a sample estimate \(\hat{\mathbf{K}}_{XX}\) with \(p > n\)

   • \(\mathbf{K}_{XX}\) not invertible
   • Infinitely many solutions

Solutions:

1. QR decomposition: \(\mathbf{X} = \mathbf{Q}\mathbf{R}\)

   • More stable than normal equations
   • \(\mathbf{a} = \mathbf{R}^{-1}\mathbf{Q}^T\mathbf{y}\)

2. SVD: \(\mathbf{X} = \mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^T\)

   • Handles rank-deficient cases
   • Pseudoinverse: \(\mathbf{X}^+ = \mathbf{V}\boldsymbol{\Sigma}^+ \mathbf{U}^T\)

3. Regularization:

   • Ridge: Add \(\lambda \mathbf{I}\) to \(\mathbf{K}_{XX}\)
   • Makes problem well-posed
   • Trades bias for stability

Multiple responses:

Linear model:

where \(\mathbf{W} \in \mathbb{R}^{p \times m}\) is the weight matrix

MSE matrix:

Minimize trace (total MSE):

Solution:

where \(\mathbf{K}_{XY} = \mathbb{E}[\mathbf{X}\mathbf{Y}^T] - \mathbb{E}[\mathbf{X}]\mathbb{E}[\mathbf{Y}]^T\)

Solves as \(m\) separate LMMSE problems - one per output

Computational cost:

When \(\mathbf{K}_{XX}\) has off-diagonal terms:

• Matrix inversion requires \(O(p^3)\) operations
• All variables coupled in solution
• Numerical instability for ill-conditioned matrices

Eigendecomposition approach:

Any symmetric positive semi-definite matrix:

where:

• \(\mathbf{U} = [\mathbf{u}_1, \mathbf{u}_2, ..., \mathbf{u}_p]\) orthonormal
• \(\boldsymbol{\Lambda} = \text{diag}(\lambda_1, \lambda_2, ..., \lambda_p)\)
• \(\lambda_1 \geq \lambda_2 \geq ... \geq \lambda_p \geq 0\)

Eigenvectors are orthogonal

This orthogonality simplifies coordinate transformation.

Coordinate transformation:

Covariance in new coordinates:

Result: Diagonal covariance matrix

Components of \(\mathbf{Z}\) are uncorrelated:

Inverse transform (reconstruction):

Since \(\mathbf{U}\) is orthonormal: \(\mathbf{U}^T\mathbf{U} = \mathbf{I}\)

Given covariance:

Find eigenvalues: Solve \(\det(\mathbf{K} - \lambda\mathbf{I}) = 0\)

Block structure simplifies:

• Upper \(2 \times 2\) block: \(\lambda_{1,2} = 6 \pm 4\)
• Lower \(1 \times 1\) block: \(\lambda_3 = 3\)

Result: \(\lambda_1 = 10, \lambda_2 = 3, \lambda_3 = 2\)

Find eigenvectors: Solve \((\mathbf{K} - \lambda_i\mathbf{I})\mathbf{v} = 0\)

Result: \(\mathbf{K}_{ZZ} = \text{diag}(10, 3, 2)\)

Coupled problem:

Every component of \(\mathbf{a}\) depends on every entry of \(\mathbf{K}_{XX}\)

In the KL basis \(\mathbf{Z} = \mathbf{U}^T\mathbf{X}\):

\(\mathbf{K}_{ZZ} = \boldsymbol{\Lambda}\), so the normal equations diagonalize:

Each coefficient solved independently

Cost: eigendecomposition is \(O(p^3)\), like inversion - the gain is structure, not speed

• Conditioning read off the spectrum: small \(\lambda_i\) inflate \(a_{z,i}\)
• Per-component regularization:

• Truncating small-\(\lambda_i\) components: principal-component regression

Not all dimensions equally informative

Eigenvalues measure variance (information) per dimension.

Truncated representation: Keep only first \(k < p\) components:

Selection criterion: Retain fraction \(\alpha\) of total variance:

Common choice: \(\alpha = 0.95\) or \(0.99\)

Reconstruction error:

Error equals sum of discarded eigenvalues.

Applications:

• Principal Component Analysis (PCA)
• Data compression
• Denoising (discard noisy dimensions)