#eth/cil/theory

Eckart Young Theorem

By pruning the singular values below

σ_{k}

in the SVD representation, we get an optimal rank

k

approximation of a matrix

Formal definition:

Given

A \in R^{n \times m}

with SVD

A = U Σ V^{T}

. Then for all

1 \leq k \leq min n, m

$\begin{aligned} A_{k} & := U diag (σ_{1}, \dots, σ_{k}) V^{T} \\ \in \arg min {| | A - B | |_{F} : rank (B) \leq k} \end{aligned}$

The squared error of low rank approximations can be expressed as:

| | A - A_{k} | |_{F}^{2} = \sum_{i = k + 1}^{rank (A)} σ_{i}^{2}

Proof:

A - A_{k} = U diag (0, \dots, 0, \dots, σ_{k + 1}, \dots, σ_{min {n, m}}) V^{T}