  We study algorithms for estimating the statistical leverage scores of
rectangular dense or sparse matrices of arbitrary rank. Our approach is based
on combining rank revealing methods with compositions of dense and sparse
randomized dimensionality reduction transforms. We first develop a set of fast
novel algorithms for rank estimation, column subset selection and least squares
preconditioning. We then describe the design and implementation of leverage
score estimators based on these primitives. These estimators are also effective
for rank deficient input, which is frequently the case in data analytics
applications. We provide detailed complexity analyses for all algorithms as
well as meaningful approximation bounds and comparisons with the
state-of-the-art. We conduct extensive numerical experiments to evaluate our
algorithms and to illustrate their properties and performance using synthetic
and real world data sets.
