Sparse interpolation, the FFT algorithm and FIR filters

Citation

Briani M, Cuyt A & Lee W (2017) Sparse interpolation, the FFT algorithm and FIR filters. In: Gerdt V, Koepf W, Seiler W & Vorozhtsov E (eds.) Computer Algebra in Scientific Computing - 19th International Workshop, CASC 2017, Beijing, China, September 18-22, 2017, Proceedings. Lecture Notes in Computer Science (LNCS), 10490. 19th International Workshop on Computer Algebra in Scientific Computing, Beijing, China, 18.09.2017-22.09.2017. Cham, Switzerland: Springer International Publishing, pp. 27-39. https://doi.org/10.1007/978-3-319-66320-3

Abstract
In signal processing, the Fourier transform is a popular method to analyze the frequency content of a signal, as it decomposes the signal into a linear combination of complex exponentials with integer frequencies. A fast algorithm to compute the Fourier transform is based on a binary divide and conquer strategy. In computer algebra, sparse interpolation is well-known and closely related to Prony's method of exponential fitting, which dates back to 1795. In this paper we develop a divide and conquer algorithm for sparse interpolation and show how it is a generalization of the FFT algorithm. In addition, when considering an analog as opposed to a discrete version of our divide and conquer algorithm, we can establish a connection with digital filter theory.

Journal
LNCS