Low-rank approximations

Give M×N matrix C and a positive integer k, we wish to find an M×N matrix Ck of rank at most k，so as to minimize the Frobenius norm of the matrix difference X=C−Ck ，defined to be

Thus, the Frobenius norm of X measures the discrepancy between Ck and C; our goal is to find a matrix Ck that minimizes this discrepancy, while constraining Ck to have rank at most k. If r is the rank of C, clearly Cr=C and the Frobenius norm of the discrepancy is zero in this case. When k is far smaller than r, we refer to Ck as a low-rank approximation.

---

SVD

1. Given C, constuct its SVD int the form of C=UΣVT.
2. Derive from Σ the matrix Σk formed by replacing by zeros the r−k smallest sigular values on the diagnal of Σ.
3. Compute and output Ck=UΣkVT as the rank-k approximation to C.

http://nlp.stanford.edu/IR-book/html/htmledition/low-rank-approximations-1.html