  $\newcommand{\MatA}{\mathcal{M}}$ $\newcommand{\eps}{\varepsilon}$
$\newcommand{\NSize}{\mathsf{N}{}}$ $\newcommand{\MatB}{\mathcal{B}}$
$\newcommand{\Fnorm}[1]{\left\| {#1} \right\|_F}$
$\newcommand{\PrcOpt}[2]{\mu_{\mathrm{opt}}\pth{#1, #2}}$
$\newcommand{\pth}[1]{\left(#1\right)}$
  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 $\Fnorm{\MatA -
\MatB}^2 \leq (1+\eps) \PrcOpt{\MatA}{k}$, where $\NSize = n d$ is the input
size, and $\PrcOpt{\MatA}{k}$ 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.
