Fast Low Rank Approximation via Random Projections

Gugan Thoppe
Karthyek Rajhaa A M
Friday, 19 Apr 2013, 14:30 to 16:00
A-212 (STCS Seminar Room)
Given an m x n matrix A, we define the rank-k approximation of A as a matrix B of same size and of rank at most k such that A and B are close in the Frobenius norm. In this talk, we will first give a geometric interpretation of this problem and relate it to the singular value of decomposition (SVD) of the matrix A. We will then use this knowledge to understand why a fast low rank approximation algorithm is to be expected. If time permits, we will see some applications of low rank approximations to a class of fixed point and minimization problems.