Rapid factorization of structured matrices via randomized sampling

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.