Low-rank approximations

Give matrix and a positive integer , we wish to find an matrix of rank at most ，so as to minimize the Frobenius norm of the matrix difference ，defined to be

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

SVD

1. Given , constuct its SVD int the form of .
2. Derive from the matrix formed by replacing by zeros the smallest sigular values on the diagnal of .
3. Compute and output as the rank- approximation to .

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