Homework 3

Overview

Two analytic problems on linear MMSE estimation and the eigenstructure of a covariance matrix, followed by polynomial regression by direct solution of the normal equations, with and without \(\ell_2\) regularization.

Getting Started

Download the starter code: hw3-starter.zip

unzip hw3-starter.zip
cd hw3-starter

q1/ and q2/ are empty directories for your PDFs. q3/ contains regression.py, with a docstring stating how it is run and what it prints or writes, and a test_interfaces.py that runs the script and checks its output files. Run it from inside q3/:

python -m pytest test_interfaces.py

Problem 1: Linear MMSE Estimation

Consider the problem of estimating a scalar random variable \(Y\) from a vector observation \(\mathbf{X} \in \mathbb{R}^n\). We want to find the linear MMSE estimator \(\hat{Y} = \mathbf{w}^T\mathbf{X}\) that minimizes the mean squared error (MSE), \(\mathbb{E}[(Y - \hat{Y})^2]\).

a. Given two zero-mean jointly Gaussian random variables \(X\) and \(Y\) with covariance matrix

find the linear MMSE estimator \(\hat{Y} = w^*X\) for \(Y\) given \(X\). That is, find the optimal weight \(w^*\) that minimizes the MSE.

b. Calculate the minimum mean squared error (MMSE) achieved by the optimal estimator \(\hat{Y} = w^*X\).

c. Show that for jointly Gaussian random variables, the linear MMSE estimator found in part (a) is equivalent to the conditional expectation \(\mathbb{E}[Y|X]\). In other words, prove that \(w^*X = \mathbb{E}[Y|X]\).

d. Now suppose \(X\) and \(Y\) are not jointly Gaussian but have the same covariance matrix \(\mathbf{K}\) as above. Find the linear MMSE estimator \(\hat{Y} = \tilde{w}X\) in this case. Is the MMSE achieved by \(\tilde{w}\) different from the jointly Gaussian case in part (b)? Explain why or why not.

Deliverables

See Submission. q1.pdf contains your worked solution, typeset or scanned. Show all work and box final answers.

Problem 2: Eigenanalysis of Covariance Matrix and PCA

Consider a zero-mean random vector \(\mathbf{X} \in \mathbb{R}^3\) with covariance matrix

a. Find the eigenvalues \(\lambda_k\) and orthonormal eigenvectors \(\mathbf{e}_k\) of \(\mathbf{K}\).

b. Show that the covariance matrix \(\mathbf{K}\) can be expressed in terms of its eigenvalues and eigenvectors using the spectral decomposition (this is a special case of Mercer’s theorem):

c. Express \(\mathbf{X}\) using its Karhunen-Loève expansion (KL expansion), i.e.

where \(Z_k\) are uncorrelated random variables with zero mean and variance equal to the corresponding eigenvalues \(\lambda_k\). This expansion is closely related to Principal Component Analysis (PCA), where the eigenvectors of the covariance matrix are called principal components and the eigenvalues represent the variance, often interpreted as “power,” captured by each component.

d. Suppose you want to approximate \(\mathbf{X}\) using only its two dominant eigenmodes (i.e. the two principal components with the largest eigenvalues). Write the approximation \(\tilde{\mathbf{X}}\) in terms of the eigenvectors and eigenvalues of \(\mathbf{K}\). This is an example of dimensionality reduction using PCA.

e. What is the mean squared error (MSE) of the approximation in (d), i.e.

Express your answer in terms of the eigenvalues. This MSE is related to the concept of reconstruction error in PCA and the total variance captured by the selected principal components.

Deliverables

See Submission. q2.pdf contains your worked solution, typeset or scanned. Show all work and box final answers.

Problem 3: Polynomial Regression

Many signal processing applications require separating a clean signal from noisy measurements. In this problem, you will implement polynomial regression using direct matrix calculations to recover a signal corrupted by additive noise.

Part A: Least-Squares Fit

Generate synthetic data by combining a signal \(f(t)\) with Gaussian noise:

where \(f(t) = 0.5 + 0.4t - 0.3t^2 + 0.2t^3\) and \(n(t) \sim \mathcal{N}(0,0.1)\) is white Gaussian noise. Sample 1000 points uniformly on \([0,1]\). Store both \(f(t)\) and \(y(t)\).

Perform a 70-30 split of your data points into training (first 700 points) and testing (remaining 300 points) sets. For each polynomial degree in \(d = \{3, 5, 7, 9\}\):

• Construct the design matrix \(\mathbf{X}\) where row \(i\) is \([1, t_i, t_i^2, ..., t_i^d]\) using the training data.
• Calculate regression coefficients \(\mathbf{w}\) by solving \((\mathbf{X}^T\mathbf{X})\mathbf{w} = \mathbf{X}^T\mathbf{y}\) using matrix multiplication and back-substitution. Check (and comment) whether \((\mathbf{X}^T\mathbf{X})\) is poorly conditioned.
• Evaluate the mean-square error (MSE) on both the training set and test set using these coefficients.

Plot fitted polynomials against the true signal using test data points. Generate a figure showing training and test MSE versus polynomial degree.

Part B: Regularization

Add \(\ell_2\) regularization with degree \(d=5\) by solving:

for \(\alpha = \{ 0.1, 1.0, 10.0 \}\). Check (and comment) whether \((\mathbf{X}^T\mathbf{X} + \alpha I)\) is poorly conditioned. Plot training and test MSE versus \(\alpha\). Save your best model coefficients (based on test MSE) to coeff.txt using np.savetxt('coeff.txt', w).

Part C: Bias-Variance Decomposition

Consider the MSE decomposition for polynomial regression:

Use your results from Part A and Part B to explain how polynomial degree and regularization strength affect this decomposition. Relate the behavior of your fitted polynomials to regions of high bias (underfitting) versus high variance (overfitting). Use specific examples to argue whether regularization is effective in reducing overfitting or not.

Deliverables

See Submission. regression.py is your implementation and coeff.txt holds the coefficients saved in Part B. q3.pdf contains the fitted-polynomial figures, the MSE plots, your conditioning comments, and the Part C discussion.

README.md
.gitignore
requirements.txt
q1/
└── q1.pdf
q2/
└── q2.pdf
q3/
├── regression.py
├── test_interfaces.py
├── coeff.txt
└── q3.pdf