  Randomized sampling has recently been demonstrated to be an efficient
technique for computing approximate low-rank factorizations of matrices for
which fast methods for computing matrix vector products are available. This
paper describes an extension of such techniques to a wider class of matrices
that are not themselves rank-deficient, but have off-diagonal blocks that are.
Such matrices arise frequently in numerical analysis and signal processing, and
there exist several methods for rapidly performing algebraic operations
(matrix-vector multiplications, matrix factorizations, matrix inversion,
\textit{etc}) on them once low-rank approximations to all off-diagonal blocks
have been constructed. The paper demonstrates that if such a matrix can be
applied to a vector in O(N) time, where the matrix is of size $N\times N$, and
if individual entries of the matrix can be computed rapidly, then in many
cases, the task of constructing approximate low-rank factorizations for all
off-diagonal blocks can be performed in $O(N k^{2})$ time, where $k$ is an
upper bound for the numerical rank of the off-diagonal blocks.
