Fast Fourier transform

A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). Fourier analysis converts a signal from its original domain (often time or space) to a representation in the frequency domain and vice versa. The DFT is obtained by decomposing a sequence of values into components of different frequencies. This operation is useful in many fields, but computing it directly from the definition is often too slow to be practical. An FFT rapidly computes such transformations by factorizing the DFT matrix into a product of sparse (mostly zero) factors. As a result, it manages to reduce the complexity of computing the DFT from O\left(N^2\right), which arises if one simply applies the definition of DFT, to O(N \log N), where N is the data size. The difference in speed can be enormous, esp

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (100)

Related publications

Related people (41)

Related people

Related units (30)

Related units

Related concepts (83)

Related concepts

Related courses (107)

Related courses

Related lectures (272)

Related lectures

Discrete Fourier transform

In mathematics, the discrete Fourier transform (DFT) converts a finite sequence of equally-spaced samples of a function into a same-length sequence of equally-spaced samples of the discrete-time F

Fourier transform

In physics and mathematics, the Fourier transform (FT) is a transform that converts a function into a form that describes the frequencies present in the original function. The output of the transfo

Cooley–Tukey FFT algorithm

The Cooley–Tukey algorithm, named after J. W. Cooley and John Tukey, is the most common fast Fourier transform (FFT) algorithm. It re-expresses the discrete Fourier transform (DFT) of an arbitrary c

FIN-472: Computational finance

Participants of this course will master computational techniques frequently used in mathematical finance applications. Emphasis will be put on the implementation and practical aspects.

EE-205: Signals and systems (for EL&IC)

This class teaches the theory of linear time-invariant (LTI) systems. These systems serve both as models of physical reality (such as the wireless channel) and as engineered systems (such as electrical circuits, filters and control strategies).

MATH-205: Analysis IV

Learn the basis of Lebesgue integration and Fourier analysis

Shift-Invariant and Sampling Spaces Associated With the Fractional Fourier Transform Domain

Ayush Bhandari

Shift-invariant spaces play an important role in sampling theory, multiresolution analysis, and many other areas of signal and image processing. A special class of the shift-invariant spaces is the class of sampling spaces in which functions are determined by their values on a discrete set of points. One of the vital tools used in the study of sampling spaces is the Zak transform. The Zak transform is also related to the Poisson summation formula and a common thread between all these notions is the Fourier transform.

2012

Perturbed Fourier uniqueness and interpolation results in higher dimensions

Martin Peter Stoller

We obtain new Fourier interpolation and uniqueness results in all dimensions, extending methods and results by the first author and M. Sousa [11] and the second author [12]. We show that the only Schwartz function which, together with its Fourier transform, vanishes on surfaces close to the origin-centered spheres whose radii are square roots of integers, is the zero function. In the radial case, these surfaces are spheres with perturbed radii, while in the non-radial case, they can be graphs of continuous functions over the sphere. As an applica-tion, we translate our perturbed Fourier uniqueness results to perturbed Heisenberg uniqueness for the hyperbola, using the interrelation between these fields introduced and studied by Bakan, Hedenmalm, Montes-Rodriguez, Radchenko and Via-zovska [1].(c) 2022 Published by Elsevier Inc.

ACADEMIC PRESS INC ELSEVIER SCIENCE2022

Fourier uniqueness and interpolation in Euclidean space

Martin Peter Stoller

We prove that every Schwartz function in Euclidean space can be completely recovered given only its restrictions and the restrictions of its Fourier transform to all origin-centered spheres whose radii are square roots of integers. In particular, the only Schwartz function which, together with its Fourier transform, vanishes on these spheres, is the zero function. We show that this remains true if we replace the spheres by surfaces or discrete sets of points which are sufficiently small perturbations of these spheres. In a complementary, opposite direction, we construct infinite dimensional spaces of Fourier eigenfunctions vanishing on on certain discrete subsets of those spheres. The proofs combine harmonic analysis, the theory of modular forms and algebraic number theory.

EPFL2022