Publication
Title
Sparse interpolation, the FFT algorithm and FIR filters
Author
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 Pronys 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.
Language
English
Source (journal)
Lecture notes in computer science. - Berlin, 1973, currens
Source (book)
CASC 2017: Computer Algebra in Scientific Computing
Proceedings 19th International Workshop, CASC 2017, September 18-22, 2017, Beijing, China
Source (series)
Theoretical computer science and general issues ; 10490
Publication
Cham : Springer , 2017
ISBN
978-3-319-66319-7
Volume/pages
(2017) , p. 27-39
Full text (Publisher's DOI)
Full text (open access)
Full text (publisher's version - intranet only)
UAntwerpen
Faculty/Department
Research group
Project info
Sub-Nyquist underwater communication.
Publication type
Subject
Affiliation
Publications with a UAntwerp address
External links
Record
Identification
Creation 01.10.2018
Last edited 15.07.2021
To cite this reference