Premium
Iterative Sparse FFT for M‐sparse Vectors: Deterministic versus Random Sampling
Author(s) -
Plonka Gerlind,
von Wulffen Therese
Publication year - 2021
Publication title -
pamm
Language(s) - English
Resource type - Journals
ISSN - 1617-7061
DOI - 10.1002/pamm.202000134
Subject(s) - vandermonde matrix , fast fourier transform , mathematics , sparse matrix , row , divide and conquer algorithms , sampling (signal processing) , matrix (chemical analysis) , algorithm , iterative method , stability (learning theory) , computer science , filter (signal processing) , computer vision , eigenvalues and eigenvectors , physics , materials science , quantum mechanics , database , machine learning , composite material , gaussian
In a recent paper [3] we have proposed a deterministic stable sparse FFT algorithm for M ‐sparse vectors of length N = 2 J with runtime ( M 2 log 2 N ) which generalizes the approach in [2]. Our method is based on a divide‐and‐conquer technique and requires to solve an equation system of Vandermonde type at each iteration step. To ensure numerical stability of the algorithm, the number of rows of the employed Vandermonde matrices at each step has been chosen adaptively in [3]. In this paper, we compare the results of [3] with a random sampling approach for determining the rows of the coefficient matrix.