Butterfly factorization via randomized matrix-vector multiplications

This paper presents an adaptive randomized algorithm for computing the butterfly factorization of an $m\times n$ matrix with $m\approx n$ provided that both the matrix and its transpose can be rapi...