Kernel Matrix Approximations by Sums of Exponentials and Stability of Fast Structured Transforms

Abstract

Abstract. Sum-of-exponentials (SoE) expansions provide an efficient strategy for performing some matrix transforms. In this paper, we show that they can also serve as a valuable way to compute structured approximations to some kernel matrices. We first illustrate that some existing fast transforms (Hilbert, Gauss, etc.) are essentially using generalized sequentially semiseparable (SSS) structures for which the stability has been in question. We then give comprehensive analysis of the stability of transforms via general SSS structures and rigorously prove that such transforms may have numerical errors growing exponentially, while the use of SoE expansions leads to polynomial error growth. Moreover, we give a way to further reduce the error growth to polylogarithmic via the use of hierarchical tree structures, as supported by stability analysis that extends some previous results. Our analysis reveals the following two key components that ensure the stability of rank-structured transforms and other algorithms: algorithm architecture and norm bounds of the generators of the structure. It concretely confirms the following long-standing speculations: sequential structured matrix (like SSS) algorithms are potentially unstable, even if relevant generators have bounded norms; and hierarchical structured algorithms are stable as long as relevant generator norms are bounded. SoE expansion is then just an effective way to further control the norms of the generators.