Butterfly Factorization Via Randomized Matrix-Vector Multiplications
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 rapidly applied to arbitrary vectors. The resulting factorization is composed of $\mathcal{O}(\log n)$ sparse factors, each containing $\mathcal{O}(n)$ nonzero entries. …