Low-Rank Approximation

Low-rank approximation replaces a matrix with another matrix that has fewer independent directions. It is a compression and denoising idea: preserve the strongest shared structure and discard smaller directions, measured by a chosen norm.

Defining math

If $A=U\Sigma V^{\top }$ is the SVD, its rank-$k$ truncation is

$$A_k=U_k{\Sigma }_k{V}_k^{\top }.$$

Here $U_k$ contains the first $k$ left singular vectors, $V_k$ contains the first $k$ right singular vectors, and ${\Sigma }_k$ keeps the largest $k$ singular values. The approximation keeps the directions with the most matrix energy and removes the remaining singular directions.

The Eckart-Young theorem says this is optimal in Frobenius norm:

$$A_k=\arg \underset{\mathrm{rank}(B)\le k}{\min }\Vert A-B{\Vert }_F.$$

The candidate matrix $B$ ranges over all matrices with rank at most $k$, and $\Vert \cdot {\Vert }_F$ measures entrywise squared reconstruction error. The theorem says truncated SVD is not just a convenient compression rule; it is the best rank-$k$ reconstruction under this norm.

The error is exactly the energy in discarded singular values,

$$\Vert A-A_k{\Vert }_F=\sqrt{\sum _{i=k+1}^r{\sigma }_i^2}.$$

This mechanism is related to truncated SVD, but learned recommender factors usually optimize observed entries rather than decomposing a fully observed matrix.

Worked example

Take the $4\times 3$ matrix $A=\left[\begin{array}{ccc}3& 1& 1\\ -1& 3& 1\\ 0& 2& 4\\ 2& 0& 2\end{array}\right]$. Computed numerically, its singular values are $\sigma \approx (5.657,3.742,2.000)$. By the error formula above, the Frobenius error of the best rank-$k$ approximation is the energy in the discarded singular values.

Keeping two singular directions discards only ${\sigma }_3=2.0$, so $\Vert A-A_2{\Vert }_F=2.0$. Keeping one direction discards ${\sigma }_2=3.742$ and ${\sigma }_3=2.0$, giving

$$\Vert A-A_1{\Vert }_F=\sqrt{3.742^2+2.0^2}\approx \mathrm{4.243.}$$

Caveats

Low rank is an assumption. It can erase rare but important directions, and missing entries are not zeros. For sparse interaction data, use a model whose loss matches the observation process, not raw SVD on an arbitrary filled matrix.

References

• MIT OpenCourseWare: 18.06 Linear Algebra

Nav

Section — Mathematical Foundations

← Singular Value Decomposition Calculus →