In this paper we develop algorithms for approximating matrix multiplication
with respect to the spectral norm. Let A\in{\RR^{n\times m}} and B\in{\RR^{n
\times p}} be two matrices and \eps>0. We approximate the product A^\top B
using two down-sampled sketches, \tilde{A}\in{\RR^{t\times m}} and
\tilde{B}\in{\RR^{t\times p}}, such that \norm{\tilde{A}^\top \tilde{B} -
A^\top B} \leq \eps \norm{A}\norm{B} with constant probability. We use two
different sampling procedures for constructing \tilde{A} and \tilde{B}; one of
them is done by i.i.d.