Approximation of the high-frequency Helmholtz kernel by nested directional interpolation

We present a data-sparse approximation scheme for integral operators associated with the Helmholtz equation in the high-frequency regime. The technique combines the directional approximation with nested tensor interpolation to achieve polylogarithmic-linear complexity. We rigorously prove that the directional interpolation converges exponentially with the asymptotically optimal rate and that the nested interpolation, which is required to obtain an efficient hierarchical algorithm, preserves the exponential convergence.