  A few matrix-vector multiplications with random vectors are often sufficient
to obtain reasonably good estimates for the norm of a general matrix or the
trace of a symmetric positive semi-definite matrix. Several such probabilistic
estimators have been proposed and analyzed for standard Gaussian and Rademacher
random vectors. In this work, we consider the use of rank-one random vectors,
that is, Kronecker products of (smaller) Gaussian or Rademacher vectors. It is
not only cheaper to sample such vectors but it can sometimes also be much
cheaper to multiply a matrix with a rank-one vector instead of a general
vector. In this work, theoretical and numerical evidence is given that the use
of rank-one instead of unstructured random vectors still leads to good
estimates. In particular, it is shown that our rank-one estimators multiplied
with a modest constant constitute, with high probability, upper bounds of the
quantity of interest. Partial results are provided for the case of lower
bounds. The application of our techniques to condition number estimation for
matrix functions is illustrated.
