Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

Low-Rank Matrix Approximation

-A common problem in many areas of large-scale machine learning involves deriving a useful and efficient approximation of a large matrix.

-This matrix may be the Gram matrix associated to a positive definite kernel in kernel-based algorithms in classification, dimensionality reduction, or some other large matrix arising in other learning tasks such as clustering, collaborative filtering, or matrix completion.

-For these large-scale problems, the number of matrix entries can be in the order of tens of thousands to millions. So we need to find alternative ways to approximate these SVD matricies

Exercises

  1. State the Eckart–Young theorem and verify it numerically on a random 50×5050\times50 matrix by comparing ∥A−Ak∥F\|A-A_k\|_F with σk+1\sigma_{k+1}.

  2. Show that ∥A−Ak∥F2=∑i>kσi2\|A-A_k\|_F^2=\sum_{i>k}\sigma_i^2, and deduce that the error decreases monotonically in kk.

  3. Show that the best rank-one approximation of AA in Frobenius norm is σ1u1v1⊤\sigma_1u_1v_1^\top, and compute the relative error for a matrix of your choice.

References