  Matrices with low-rank structure are ubiquitous in scientific computing.
Choosing an appropriate rank is a key step in many computational algorithms
that exploit low-rank structure. However, estimating the rank has been done
largely in an ad-hoc fashion in large-scale settings. In this work we develop a
randomized algorithm for estimating the numerical rank of a (numerically
low-rank) matrix. The algorithm is based on sketching the matrix with random
matrices from both left and right; the key fact is that with high probability,
the sketches preserve the orders of magnitude of the leading singular values.
We prove a result on the accuracy of the sketched singular values and show that
gaps in the spectrum are detected. For an $m\times n$ $(m\geq n)$ matrix of
numerical rank $r$, the algorithm runs with complexity $O(mn\log n+r^3)$, or
less for structured matrices. The steps in the algorithm are required as a part
of many low-rank algorithms, so the additional work required to estimate the
rank can be even smaller in practice. Numerical experiments illustrate the
speed and robustness of our rank estimator.
