|
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)
|
|
|
|
| |
|