**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Publication# pyFFS: A Python Library for Fast Fourier Series Computation and Interpolation with GPU Acceleration

Eric Bezzam, Paul Hurley, Sepand Kashani, Matthieu Martin Jean-André Simeoni, Martin Vetterli

2022

Journal paper

2022

Journal paper

Abstract

Fourier transforms are an often necessary component in many computational tasks, and can be computed efficiently through the fast Fourier transform (FFT) algorithm. However, many applications involve an underlying continuous signal, and a more natural choice would be to work with e.g. the Fourier series (FS) coefficients in order to avoid the additional overhead of translating between the analog and discrete domains. Unfortunately, there exists very little literature and tools for the manipulation of FS coefficients from discrete samples. This paper introduces a Python library called pyFFS for efficient FS coefficient computation, convolution, and interpolation. While the libraries SciPy and NumPy provide efficient functionality for discrete Fourier transform coefficients via the FFT algorithm, pyFFS addresses the computation of FS coefficients through what we call the fast Fourier series (FFS). Moreover, pyFFS includes an FS interpolation method based on the chirp Z-transform that can make it more than an order of magnitude faster than the SciPy equivalent when one wishes to perform interpolation. GPU support through the CuPy library allows for further acceleration, e.g. an order of magnitude faster for computing the 2-D FS coefficients of 1000 x 1000 samples and nearly two orders of magnitude faster for 2-D interpolation. As an application, we discuss the use of pyFFS in Fourier optics. pyFFS is available as an open source package at https://github.com/imagingofthings/pyFFS, with documentation at https://pyffs.readthedocs.io.

Official source

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 concepts

Loading

Related publications

Loading

Related publications (32)

Loading

Loading

Loading

Related concepts (17)

Algorithm

In mathematics and computer science, an algorithm (ˈælɡərɪðəm) is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algo

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

Fourier series

A Fourier series (ˈfʊrieɪ,_-iər) is an expansion of a periodic function into a sum of trigonometric functions. The Fourier series is an example of a trigonometric series, but not all trigonometric s

In recent work, methods from the theory of modular forms were used to obtain Fourier uniqueness results in several key dimensions (d = 1, 8, 24), in which a function could be uniquely reconstructed from the values of it and its Fourier transform on a discrete set, with the striking application of resolving the sphere packing problem in dimensions d = 8 and d = 24. In this short note, we present an alternative approach to such results, viable in even dimensions, based instead on the uniqueness theory for the KleinGordon equation. Since the existing method for the Klein-Gordon uniqueness theory is based on the study of iterations of Gauss-type maps, this suggests a connection between the latter and methods involving modular forms. The derivation of Fourier uniqueness from the Klein-Gordon theory supplies conditions on the given test function for Fourier interpolation, which are hoped to be optimal or close to optimal.

2021The Square Kilometre Array (SKA) will form the largest radio telescope ever built, generating on the order of one terabyte of data per second. To reduce the data flow sent to the central processor, hierarchical designs have been proposed: the data is primarily collected in groups of antennas, and summed coherently by beamforming. Historically, Fourier analysis has played a prominent role in radio astronomy interferometry, legitimated by the celebrated van Cittert-Zernike theorem. We show that, in the case of modern hierarchical designs, beamformed data has a less intimate, and thus more complicated relationship to the Fourier domain. Unsatisfactory attempts have been proposed to compensate, which implicitly retain the Fourier framework, and are limited to directive beamforming. We show that when stepping away from Fourier, we can embed the data in a more natural domain originating from the telescope configuration and the specific beamforming technique. This leads to a new, more accurate, imaging pipeline. Standard techniques such as w-projection, and gridding are no longer needed, as the reconstruction is performed on the celestial sphere. The proposed imager operates in two steps. First, a preconditioning based on the Gram-Schmidt orthogonalization procedure is performed, in order to facilitate the computation of the pseudoinverse sky estimate. Then, from this, the LASSO estimate is approximated very efficiently. The quality of this approximation is shown to be linked directly to the effective support of the instrument point spread function. Due to the greater flexibility of this framework, information-maximising beamforming techniques such as randomised beamforming can be readily incorporated. Moreover, we use the Bonferroni method to construct global confidence intervals onto the Gram-Schmidt least squares estimate, and use them to test the statistical significance of each pixel. The complexity of the proposed technique is assessed and compared to the the state-of-the-art combined CLEAN and A-projection algorithm. In the case of LOFAR, we show that our algorithm can be from 2 to 34 times faster. The accuracy and sensitivity of the new technique is also shown, for simulated data, to be superior.

2015Let K be a totally real number field of degree n >= 2. The inverse different of K gives rise to a lattice in Rn. We prove that the space of Schwartz Fourier eigenfunctions on R-n which vanish on the "component-wise square root" of this lattice, is infinite dimensional. The Fourier non-uniqueness set thus obtained is a discrete subset of the union of all spheres root mS(n-1) for integers m >= 0 and, as m -> infinity, there are similar to c(K)m(n-1) many points on the m-th sphere for some explicit constant c(K), proportional to the square root of the discriminant of K. This contrasts a recent Fourier uniqueness result by Stoller (2021) Using a different construction involving the codifferent of K, we prove an analogue for discrete subsets of ellipsoids. In special cases, these sets also lie on spheres with more densely spaced radii, but with fewer points on each. We also study a related question about existence of Fourier interpolation formulas with nodes "root Lambda" for general lattices Lambda subset of R-n. Using results about lattices in Lie groups of higher rank we prove that if n >= 2 and a certain group Gamma(Lambda) >= PSL2.(R)(n) is discrete, then such interpolation formulas cannot exist. Motivated by these more general considerations, we revisit the case of one radial variable and prove, for all n >= 5 and all real lambda >= 2, Fourier interpolation results for sequences of spheres root 2m/lambda Sn-1, where m ranges over any fixed cofinite set of non-negative integers. The proof relies on a series of Poincare type for Hecke groups of infinite covolume and is similar to the one in Stoller (2021).