Given a matrix M with n rows and d columns, and
fixed k and µ, we present an algorithm that in
linear time(i.e., O( N)) computes a k-rank matrix
B with approximation error || M -
B ||2
<=(1+µ) P(M, k) , where N = n * d is the input size,
and P( M,
k) is the minimum error of a k-rank approximation
to M.
This algorithm succeeds with constant
probability, and to our knowledge it is the first linear time
algorithm to achieve multiplicative approximation.