Low Rank Matrix Approximation in Linear Time

$$ $$ $$ $$ $$ $$ $$ Given a matrix $\text{MatA}$ with $n$ rows and $d$ columns, and fixed $k$ and $\text{eps}$, we present an algorithm that in linear time (i.e., $O(\text{NSize})$) computes a $k$-rank matrix $\text{MatB}$ with approximation error $\Fnorm{\MatA - \MatB}^2 \leq (1+\eps) \PrcOpt{\MatA}{k}$,where$\NSize = n d$ is the input size, and $\text{PrcOpt}\text{MatA}k$ is the minimum error of a $k$-rank approximation to $\text{MatA}$. This algorithm succeeds with constant probability, and to our knowledge it is the first linear-time algorithm to achieve multiplicative approximation.