An analysis of a butterfly algorithm

Butterfly algorithms are an effective multilevel technique to compress discretizations of integral operators with highly oscillatory kernel functions. The particular version of the butterfly algorithm presented in Candès, et al. (2009) realizes the transfer between levels by Chebyshev interpolation. We present a refinement of the analysis given in Demanet, et al. (2012) for this particular algorithm.