Matrix coherence measures the extent to which the singular vectors are
correlated with the standard basis. A more refined concept is that of
statistical leverage, which is quantified by the diagonal elements of the
projection matrix onto the best rank-k approximation to an input matrix. Both
can be computed in the time required to compute an orthogonal basis for the
input matrix, and both are of central importance in numerous machine learning
and data analysis applications. Our main result is a randomized algorithm to
approximate the statistical leverage scores (and thus the coherence) of an
arbitrary matrix in time qualitatively faster than this naive algorithm. Our
analysis boils down to computing quickly a relative-error approximation to an
underconstrained least-squares approximation.