Low Rank Matrix Approximation in Linear Time

newcommandMatAM newcommandepsvarepsilon newcommandNSizemathsfN newcommandMatBB newcommandFnorm[1]left| #1 right|F newcommandPrcOpt[2]μoptpth#1, #2 newcommandpth[1]left(#1right) Given a matrix MatA with n rows and d columns, and fixed k and eps, we present an algorithm that in linear time (i.e., O(NSize )) computes a k-rank matrix MatB with approximation error FnormMatA - MatB2 ≤ (1+eps) PrcOptMatAk, where NSize = n d is the input size, and PrcOptMatAk is the minimum error of a k-rank approximation to MatA. This algorithm succeeds with constant probability, and to our knowledge it is the first linear-time algorithm to achieve multiplicative approximation.