9.128 min read

Matrix Formulation of Linear Reduction

The linear reduction problem in matrix form: minimize $\|A - V_k V_k^\top A\|_F^2$ over $m \times k$ matrices $V_k$ with $V_k^\top V_k = I_k$ .

Since $V_k V_k^\top$ is the projection matrix onto the column space of $V_k$ , this asks: what rank- $k$ projection minimizes the Frobenius distance between $A$ and its projection? The Frobenius norm $\|M\|_F^2 = \sum_{ij} m_{ij}^2 = \text{tr}(M^\top M)$ measures the total squared size.

Formal View

Definition 9.3 — Linear Reduction as Matrix Approximation

The linear reduction problem:

\min_{V_k : V_k^\top V_k = I_k} \|A - V_k V_k^\top A\|_F^2,

equivalent to finding the best rank-

k

projection

P_k = V_k V_k^\top

minimizing

\|A - P_k A\|_F^2

$\|M\|_F^2 = \sum_{ij} m_{ij}^2 = \operatorname{tr}(M^\top M)$ .

Why This Matters

Framing as Frobenius-norm matrix approximation unlocks the Eckart-Young theorem.

Image compression: minimize $\|\text{Image} - \text{Rank-}k \text{ Approx}\|_F^2$ .
Collaborative filtering: best low-rank approximation to user-item matrix.
Noise reduction: small singular values capture noise; truncating them cleans the signal.

Learning Resources

Low-rank matrix approximation

MIT OpenCourseWare

Strang on Frobenius norm and the best rank-$k$ approximation.

45 min

Frobenius norm explained

Steve Brunton

Matrix norms and their role in approximation.

20 min

Quiz

Question 1

The Frobenius norm $\|M\|_F^2$ equals:

Question 2

$V_k V_k^\top$ is the orthogonal projection onto the column space of $V_k$ when $V_k$ has orthonormal columns.

Common Mistakes

Confusing Frobenius norm with spectral norm (largest singular value).
Thinking $V_k V_k^\top = I$ — true only if $k = m$ ; for $k < m$ , it is a rank- $k$ projection.