  This paper introduces the interpolative butterfly factorization for nearly
optimal implementation of several transforms in harmonic analysis, when their
explicit formulas satisfy certain analytic properties and the matrix
representations of these transforms satisfy a complementary low-rank property.
A preliminary interpolative butterfly factorization is constructed based on
interpolative low-rank approximations of the complementary low-rank matrix. A
novel sweeping matrix compression technique further compresses the preliminary
interpolative butterfly factorization via a sequence of structure-preserving
low-rank approximations. The sweeping procedure propagates the low-rank
property among neighboring matrix factors to compress dense submatrices in the
preliminary butterfly factorization to obtain an optimal one in the butterfly
scheme. For an $N\times N$ matrix, it takes $O(N\log N)$ operations and
complexity to construct the factorization as a product of $O(\log N)$ sparse
matrices, each with $O(N)$ nonzero entries. Hence, it can be applied rapidly in
$O(N\log N)$ operations. Numerical results are provided to demonstrate the
effectiveness of this algorithm.
