Prologue: Data Compression, PCA & Residue Analysis (IITM MLT L5)

1. Recap from Parts 1–2

Setup. You have data points \(x_1, \dots, x_n \in \mathbb{R}^d\). Assume the data is centered, so \(\frac{1}{n}\sum_i x_i = 0\).

Representing a point with a line. Take a unit vector \(w\) with \(\|w\| = 1\). The projection of \(x_i\) onto the line through \(w\) is \((x_i^\top w)\,w\). So each point is stored as a single scalar coefficient \(x_i^\top w\), plus the shared vector \(w\).

Choosing the best line. Pick the \(w\) that minimizes the average reconstruction error:

Equivalent form. Expand the error for one point:

2. Residue analysis

Residues after the first line. Let \(w_1\) be the best line. The residue of each point is what the line fails to capture:

Key property: residues are orthogonal to \(w_1\).

Repeating the procedure. Treat the residues \(\{r_i\}\) as a new dataset and find the best line for them. Call it \(w_2\). Since every \(r_i \perp w_1\), the optimal \(w_2\) is also orthogonal to \(w_1\). Compute new residues and continue.

Result after \(d\) rounds. You get an orthonormal set \(w_1, \dots, w_d\). Each point is represented exactly:

3. Data compression

Stopping early. Suppose that after \(k\) rounds the residues are approximately zero. That means the data essentially lies in a \(k\)-dimensional subspace.

Storage cost.

• Original data: \(n \cdot d\) numbers.
• Compressed data: \(k \cdot d\) numbers for the basis vectors, plus \(n \cdot k\) numbers for the coefficients. Total \(k(d + n)\).

The savings are large when \(k \ll d\).

The tradeoff. A smaller \(k\) gives more compression but a larger reconstruction error. The residue norms after step \(k\) measure exactly what is lost.

4. Connection to PCA (eigenvectors)

First direction. Use a Lagrangian on \(\max_w w^\top C w\) subject to \(w^\top w = 1\). Setting the gradient to zero gives

Later directions (deflation). The covariance matrix of the residues is

Conclusion. The greedy residue procedure is exactly Principal Component Analysis (PCA). The vectors \(w_k\) are the principal components, which are the eigenvectors of the covariance matrix sorted by eigenvalue.

5. Interpreting the eigenvalues

Eigenvalue as variance. For each component,

Error after keeping \(k\) components.

Choosing \(k\). Keep the smallest \(k\) such that the fraction of variance explained is high enough:

6. PCA algorithm summary

1. Center the data by subtracting the mean from every point.
2. Compute the covariance matrix \(C = \frac{1}{n}\sum_i x_i x_i^\top\).
3. Find the eigenvalues and eigenvectors of \(C\), and sort them so \(\lambda_1 \geq \dots \geq \lambda_d\).
4. Choose \(k\) using the variance-explained criterion.
5. Represent each point as \(\big(x_i^\top w_1, \dots, x_i^\top w_k\big) \in \mathbb{R}^k\).

Key takeaways

• Residues are orthogonal to earlier directions. Finding lines on residues one after another produces an orthonormal basis.
• The greedy procedure equals the eigen-decomposition of \(C\). Greedy residue-fitting is PCA.
• Eigenvalues measure variance. The eigenvalue of each direction is the variance it captures, and the dropped eigenvalues add up to the compression error.
• Compression works when variance is concentrated. If a few directions hold most of the variance, the data can be compressed with little loss.

Q1. Why is the optimal \(w\) an eigenvector?

A quick correction first: \((x_i^\top w)\,w\) is not the eigenvector. It is the projection of \(x_i\) onto the line. What turns out to be an eigenvector is the optimal direction \(w\) that defines that line. Here is the chain of reasoning.

Step 1: Write the reconstruction error for one point

The point \(x_i\) is approximated by its projection \((x_i^\top w)w\). Using \(\|w\|=1\):

Step 2: Average over all points

The first term doesn't depend on \(w\). So minimizing the error is the same as maximizing \(\frac{1}{n}\sum_i (x_i^\top w)^2\).

Step 3: Rewrite the objective using the covariance matrix

Since \((x_i^\top w)^2 = (w^\top x_i)(x_i^\top w) = w^\top (x_i x_i^\top) w\),

The problem is now:

Step 4: Solve with a Lagrange multiplier

The Lagrangian is

Take the gradient with respect to \(w\). Since \(C\) is symmetric, \(\nabla_w (w^\top C w) = 2Cw\):

This is the eigenvector equation. Any stationary point \(w\) must be an eigenvector of \(C\).

Step 5: Find which eigenvector is the best one

Plug an eigenvector back into the objective:

The objective value at an eigenvector equals its eigenvalue. To maximize, pick the eigenvector with the largest eigenvalue \(\lambda_1\).

Alternative check without calculus

\(C\) is symmetric and positive semidefinite. So it has an orthonormal eigenbasis \(u_1,\dots,u_d\) with eigenvalues \(\lambda_1 \ge \dots \ge \lambda_d \ge 0\).

Write any unit vector as \(w = \sum_j a_j u_j\) with \(\sum_j a_j^2 = 1\). Then

Equality holds when \(a_1 = 1\) and all other \(a_j = 0\), that is, when \(w = u_1\). This shows directly that the top eigenvector is the global maximizer, not just a stationary point.

Summary

Q2. PCA in the multivariable setup

I'll take "multivariable setup" to mean projecting onto a \(k\)-dimensional subspace all at once, instead of finding one line at a time. This is the general form of PCA, and the one-line case is just \(k=1\).

1. Setup

You have centered data \(x_1,\dots,x_n \in \mathbb{R}^d\). Stack them as rows of a matrix \(X \in \mathbb{R}^{n\times d}\). The covariance matrix is

You want a \(k\)-dimensional subspace (\(k < d\)) that best represents the data.

2. Representing a subspace

Describe the subspace by a matrix \(W = [w_1 \cdots w_k] \in \mathbb{R}^{d\times k}\) with orthonormal columns:

For each point:

• The coefficients (the compressed code) are \(z_i = W^\top x_i \in \mathbb{R}^k\). These are the \(k\) dot products \(x_i^\top w_j\).
• The reconstruction is \(\hat{x}_i = W z_i = WW^\top x_i\).

\(P = WW^\top\) is the orthogonal projection matrix onto the subspace. It satisfies \(P^2 = P\) and \(P^\top = P\).

For \(k=1\), this reduces to \((x_i^\top w)\,w\), which is exactly what you had before.

3. Reconstruction error

The error for one point is

This uses the fact that \(I-P\) is also a projection, so \((I-P)^\top(I-P) = I-P\).

The term \(x_i^\top WW^\top x_i\) equals \(\|W^\top x_i\|^2\). Averaging over all points:

4. The trace objective

Rewrite the second term using the trace trick, \(a^\top a = \operatorname{tr}(aa^\top)\):

So PCA in the multivariable form is the problem

Interpretation: maximize the total variance captured across \(k\) orthonormal directions.

5. Solving it

Lagrangian. The constraint \(W^\top W = I_k\) is a \(k \times k\) symmetric matrix equation, so the multiplier is a symmetric matrix \(\Lambda\):

Stationarity. Using \(\nabla_W \operatorname{tr}(W^\top C W) = 2CW\):

Diagonalizing. \(\Lambda\) is symmetric, so \(\Lambda = Q D Q^\top\) with \(Q\) orthogonal. Set \(\tilde W = WQ\). Then

Each column of \(\tilde W\) is an eigenvector of \(C\). So the optimal subspace is spanned by \(k\) eigenvectors of \(C\).

Which eigenvectors. At such a solution, \(\operatorname{tr}(W^\top C W) = \operatorname{tr}(\Lambda) = \) the sum of the chosen eigenvalues. To maximize this, choose the eigenvectors of the \(k\) largest eigenvalues:

This result is Ky Fan's theorem. It is the \(k\)-dimensional version of the bound \(w^\top C w \le \lambda_1\) from the one-line case.

6. Subtle point: the subspace is unique, the basis is not

If \(W\) is optimal, then \(WR\) is also optimal for any \(k\times k\) orthogonal matrix \(R\):

The objective only "sees" the projection matrix \(WW^\top\), and \((WR)(WR)^\top = WW^\top\). So:

• The joint optimization determines only the subspace.
• Choosing the eigenvectors themselves as the basis is a convention. In that basis, the coordinates \(z_i\) are uncorrelated, because \(W^\top C W = \operatorname{diag}(\lambda_1,\dots,\lambda_k)\).
• The greedy residue method from the lecture lands on exactly this eigenvector basis.

The subspace is unique as long as \(\lambda_k > \lambda_{k+1}\).

7. Error and choosing \(k\)

The minimum reconstruction error is the sum of the dropped eigenvalues:

Pick \(k\) so that the explained variance \(\dfrac{\sum_{j\le k}\lambda_j}{\sum_{j\le d}\lambda_j}\) reaches your threshold.

8. Matrix form with SVD

Take the SVD of the data matrix, \(X = U\Sigma V^\top\). Then

• The principal directions are the columns of \(V\).
• The eigenvalues are \(\lambda_j = \sigma_j^2/n\).
• The compressed data is \(Z = XW = XV_k = U_k\Sigma_k\), an \(n\times k\) matrix.
• The reconstruction \(\hat X = U_k \Sigma_k V_k^\top\) is the best rank-\(k\) approximation of \(X\) in Frobenius norm (Eckart–Young theorem).

In practice, PCA is computed through the SVD rather than by forming \(C\). This is more numerically stable.

Summary

If by "multivariable" you meant something else, such as PCA on multivariate Gaussian data or the probabilistic view of PCA, tell me and I'll cover that instead.

Q3. Why eigenvectors of the covariance matrix?

There are three ways to see it. Each answers "why" at a different level: why the covariance matrix shows up, why the optimum must be an eigenvector, and why it is the top one.

1. Why the covariance matrix appears at all

The objective is the average of \((x_i^\top w)^2\). Squaring a dot product gives

Averaging over points just averages the matrices \(x_i x_i^\top\), which produces \(C\). So the reconstruction error depends on the data only through its second moments.

This means two datasets with the same \(C\) get the same principal components. PCA cannot see anything beyond \(C\). Since the problem lives entirely in \(C\), the answer has to be expressed in terms of \(C\)'s own structure, which is its eigenvectors.

2. Why the optimum must be an eigenvector: the "no improving rotation" argument

Suppose \(w\) is optimal, and think about what \(Cw\) means.

Gradient direction. The gradient of \(w^\top C w\) is \(2Cw\). So \(Cw\) points in the direction that increases the variance fastest.

What you are allowed to move. You must stay on the unit sphere. So you can only move \(w\) in directions perpendicular to \(w\). Moving along \(w\) itself just rescales \(w\), which the constraint forbids.

Condition at the optimum. At a maximum, no allowed move can increase the variance. So \(Cw\) must have zero component perpendicular to \(w\):

Conclusion. \(Cw\) points along \(w\), which means \(Cw = \lambda w\). Being an eigenvector is precisely the condition "no small rotation of the line increases the captured variance." The Lagrange multiplier equation is a formal way of writing this same statement.

Geometric meaning. \(Cw\) is the covariance between the data and its projection on \(w\):

It shows which way the data "pulls" when you project onto \(w\). If \(Cw\) had a sideways component, the data would be correlated with a direction perpendicular to \(w\). Tilting \(w\) toward that direction would capture more variance. Eigenvectors are exactly the directions with no sideways pull.

3. Why it is the top eigenvector: in the eigenbasis the problem decouples

\(C\) is symmetric, so it has orthonormal eigenvectors \(u_1,\dots,u_d\). In that basis, \(C\) is diagonal: there are no cross terms.

Write \(w = \sum_j a_j u_j\) with \(\sum_j a_j^2 = 1\). Then

The weights \(a_j^2\) are non-negative and sum to 1. So the variance along \(w\) is a weighted average of the eigenvalues.

A weighted average is largest when all the weight sits on the largest value. So you set \(a_1 = 1\), which gives \(w = u_1\). Any mixing with other eigenvectors averages in smaller eigenvalues and lowers the variance.

Picture. The level sets of \(w^\top C w\) are ellipsoids whose axes point along the eigenvectors. The eigenvalues set how far the data spreads along each axis. The best single line is the longest axis.

For \(k\) directions. The same logic applies. With orthonormal \(w_1,\dots,w_k\), each eigenvalue \(\lambda_j\) gets a total weight between 0 and 1, and the total weight across all eigenvalues is exactly \(k\). The sum is maximized by putting full weight on the \(k\) largest eigenvalues.

In one line

The objective is a quadratic form in \(C\). Eigenvectors are the directions where \(C\) has no cross-coupling, so at an eigenvector no rotation can capture more variance. Variance along any direction is a weighted average of the eigenvalues, so the best direction is the one with the largest eigenvalue.