9.118 min read

The Linear Reduction Problem

After centering, the linear reduction problem is: minimize $\|A - V_k V_k^\top A\|_F^2$ over all $m \times k$ matrices $V_k$ with orthonormal columns.

Equivalently, this maximizes the variance captured: $\|V_k^\top A\|_F^2 = \|A\|_F^2 - \|A - V_k V_k^\top A\|_F^2$ . Since $\|A\|_F^2$ is fixed, minimizing the residual is the same as maximizing the captured variance — the key duality behind PCA.

Formal View

Theorem 9.4 — Equivalence: Minimize Residual = Maximize Captured Variance

For centered data matrix

A

and orthonormal

V_k

\|A - V_k V_k^\top A\|_F^2 = \|A\|_F^2 - \|V_k^\top A\|_F^2.

Minimizing reconstruction error is equivalent to maximizing

\|V_k^\top A\|_F^2

Why This Matters

The equivalence between minimizing residuals and maximizing variance is what makes PCA "optimal" in the least-squares sense.

PCA finds directions of maximum variance — the same as directions of minimum error.
Sensor placement: find $k$ locations capturing the most variance in a field.
Visualizing to 2D: maximize variance preserves the most structure.

Learning Resources

PCA: variance vs error

StatQuest

Intuitive explanation of the dual formulations of PCA.

22 min

Frobenius norm and matrix approximation

MIT OpenCourseWare

Matrix norms and the low-rank approximation problem.

45 min

Quiz

Question 1

Minimizing the total reconstruction error is equivalent to maximizing the total variance captured.

Question 2

The reconstruction error $\|A - V_k V_k^\top A\|_F^2$ equals:

Common Mistakes

Thinking we maximize variance of the original data — we maximize variance of the projected data $V_k^\top A$ .
Confusing $V_k^\top A$ (coordinates, $k \times N$ ) with $V_k V_k^\top A$ (projection, $m \times N$ ).