Deterministic sparse FFT algorithms

In this paper we consider sparse signals ${\bf x}\in {\bf C}^N$ which are known to vanish outside a support interval of length bounded by m < N. For the case that m is known, we propose a deterministic algorithm of complexity ${\cal O}(m\log m)$ for reconstruction of x from its discrete Fourier transform $\widehat{\bf x}\in {\bf C}^N.$ (© 2015 Wiley‐VCH Verlag GmbH & Co. KGaA, Weinheim)

• Publication year

  2015

• Venue

  PAMM

• Publication date

  2015-10-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1002/PAMM.201510323
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Sparse FFT for Functions with Short Frequency Support

  2017cited by this paper
• Deterministic sparse FFT for M-sparse vectors

  2017cited by this paper
• A sparse fast Fourier algorithm for real non-negative vectors

  2016cited by this paper
• Efficient Spectral Estimation by MUSIC and ESPRIT with Application to Sparse FFT

  2016influential reference
• A deterministic sparse FFT algorithm for vectors with small support

  2015cited by this paper
• (Nearly) Sample-Optimal Sparse Fourier Transform

  2014cited by this paper
• Super-resolution, Extremal Functions and the Condition Number of Vandermonde Matrices

  2014cited by this paper
• Recent Developments in the Sparse Fourier Transform: A compressed Fourier transform for big data

  2014cited by this paper
• GHz-wide sensing and decoding using the sparse Fourier transform

  2014cited by this paper
• Sample-Optimal Fourier Sampling in Any Constant Dimension

  2014cited by this paper
• Deterministic Sparse Fourier Approximation Via Approximating Arithmetic Progressions

  2014cited by this paper
• Prony methods for recovery of structured functions

  2014cited by this paper
• Parameter estimation for nonincreasing exponential sums by Prony-like methods

  2013cited by this paper
• Adaptive Sub-Linear Time Fourier Algorithms

  2013cited by this paper
• Computing a k-sparse n-length Discrete Fourier Transform using at most 4k samples and O(k log k) complexity

  2013cited by this paper
• A generalized Prony method for reconstruction of sparse sums of eigenfunctions of linear operators

  2013cited by this paper
• A Multiscale Sub-linear Time Fourier Algorithm for Noisy Data

  2013cited by this paper
• A sparse Prony FFT

  2013influential reference
• Improved bounds on Restricted isometry for compressed sensing

  2013cited by this paper
• Faster GPS via the sparse fourier transform

  2012cited by this paper
• Compressive, collaborative spectrum sensing for wideband Cognitive Radios

  2012cited by this paper
• On the Problem of Parameter Estimation in Exponential Sums

  2012cited by this paper
• Nearly optimal sparse fourier transform

  2012cited by this paper
• MRS Sparse-FFT: Reducing Acquisition Time and Artifacts for In Vivo 2D Correlation Spectroscopy

  2012cited by this paper
• Simple and practical algorithm for sparse Fourier transform

  2012cited by this paper
• On the Accuracy of Solving Confluent Prony Systems

  2011cited by this paper
• Nonlinear Approximation by Sums of Exponentials and Translates

  2011cited by this paper
• Nonlinear approximation by sums of nonincreasing exponentials

  2011cited by this paper
• Deterministic Sparse Fourier Approximation via Fooling Arithmetic Progressions.

  2010cited by this paper
• Combinatorial Sublinear-Time Fourier Algorithms

  2010cited by this paper
• Parameter estimation for exponential sums by approximate Prony method

  2010cited by this paper
• Improved Approximation Guarantees for Sublinear-Time Fourier Algorithms

  2010cited by this paper
• A Tutorial on Fast Fourier Sampling

  2008cited by this paper
• On perfect conditioning of Vandermonde matrices on the unit circle

  2007cited by this paper
• Sampling Moments and Reconstructing Signals of Finite Rate of Innovation: Shannon Meets Strang–Fix

  2007cited by this paper
• Improved time bounds for near-optimal sparse Fourier representations

  2005cited by this paper
• On approximation of functions by exponential sums

  2005cited by this paper
• Stable signal recovery from incomplete and inaccurate measurements

  2005cited by this paper
• Near-optimal sparse fourier representations via sampling

  2002cited by this paper
• Sampling signals with finite rate of innovation

  2002cited by this paper
• Fast Fourier Transforms for Nonequispaced Data: A Tutorial

  2001cited by this paper
• Calculating the Maximum Modulus of a Polynomial Using Steckin's Lemma

  1999cited by this paper
• Computational Frameworks for the Fast Fourier Transform

  1992cited by this paper
• Matrix pencil method for estimating parameters of exponentially damped/undamped sinusoids in noise

  1990cited by this paper
• ESPRIT-estimation of signal parameters via rotational invariance techniques

  1989cited by this paper
• Fast QR factorization of Vandermonde matrices

  1989cited by this paper
• Multiple emitter location and signal Parameter estimation

  1986cited by this paper
• Hilbert’s inequality

  1974cited by this paper
• Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform

  1973cited by this paper
• Linear algebra and geometry

  1969cited by this paper
• An algorithm for the machine calculation of complex Fourier series

  1965cited by this paper

• Electrogastrogram Analysis of Unclear Stomach Pain

  2023cites this paper
• A sparse multidimensional FFT for real positive vectors

  2016influential citation
• A sparse multi-dimensional Fast Fourier Transform with stability to noise in the context of image processing and change detection

  2016cites this paper