The multiplicative complexity of the Discrete Fourier Transform

We show how to compute the multiplicative complexity of the Discrete Fourier Transform on any set of data points.     

Minimal Hermite-Type Eigenbasis of the Discrete Fourier Transform

There exist many ways to build an orthonormal basis of \(\mathbb {R}^N\), consisting of the eigenvectors of the discrete Fourier transform (DFT). In this paper we show that there is only one such orthonormal eigenbasis of the DFT that is optimal in the sense of an appropriate uncertainty principle. Moreover, we show that these optimal eigenvectors of the DFT are direct analogues of the Hermite functions, that they also satisfy a three-term recurrence relation and that they converge to Hermite functions as N increases to infinity.

     

Abelian semi-simple algebras and algorithms for the Discrete Fourier Transform

In this paper we show how to use the theory of abelian semi-simple algebras to structure the Nussbaumer-Quandalle algorithm for the two-dimensional Discrete Fourier Transform.     

Roundoff Error Analysis of the Recursive Moving Window Discrete Fourier Transform

This paper presents both worst case and average case analysis of roundoff errors occuring in the floating point computation of the recursive moving window discrete Fourier transform (DFT) with precomputed twiddle factors. We show the strong influence of precomputation errors – both within the initial fast Fourier transform (FFT) and the recursion – on the numerical stability. Numerical simulations confirm the theoretical results.     

Fast Discrete Fourier Transform on Local Fields of Zero Characteristic

For the discrete Fourier transform with respect to the system of characters of a local field with zero characteristic, we propose a fast algorithm. We find the complexity of the algorithm.     

On the Fourier Transform of Causal Distributions

We extend the distributional Bochner formula [1, p. 72, Theorem 26] to certain kinds of distributions. Theorem I.1 gives a formula [Eq. (I.1.14)] which makes it possible to obtain easily the Fourier transform of distributions of the form As applications of the formula (I.1.14) we evaluate the Fourier transforms of the distributions G_α(P±i0, m, n) [Eq. (I.4.1)] and H_α(P±i0,n) [Eq. (II.1.1)]. It follows from Theorem II.3 that H_zk(P±i0,n) is, for 2K≠n+2r, r=0,1..., an elementary solution of the n-dimensional ultrahyperbolic operator iterated k times.     

Numerical Approximation of Probability Mass Functions via the Inverse Discrete Fourier Transform

First passage distributions of semi-Markov processes are of interest in fields such as reliability, survival analysis, and many others. Finding or computing first passage distributions is, in general, quite challenging. We take the approach of using characteristic functions (or Fourier transforms) and inverting them to numerically calculate the first passage distribution. Numerical inversion of characteristic functions can be unstable for a general probability measure. However, we show they can be quickly and accurately calculated using the inverse discrete Fourier transform for lattice distributions. Using the fast Fourier transform algorithm these computations can be extremely fast. In addition to the speed of this approach, we are able to prove a few useful bounds for the numerical inversion error of the characteristic functions. These error bounds rely on the existence of a first or second moment of the distribution, or on an eventual monotonicity condition. We demonstrate these techniques with two examples.     

The duality property of the Discrete Fourier Transform based on Simpson's rule

The classical Discrete Fourier Transform (DFT) satisfies a duality property that transforms a discrete time signal to the frequency domain and back to the original domain. In doing so, the original signal is reversed to within a multiplicative factor, namely the dimension of the transformation matrix. In this paper, we prove that the DFT based on Simpson's method satisfies a similar property and illustrate its effect on a real discrete signal. The duality property is particularly useful in determining the components of the transformation matrix as well as components of its positive integral powers. Copyright © 2012 John Wiley & Sons, Ltd.     

On the maximal multiplicative complexity of a family of bilinear forms

The number of nonscalar multiplications required to evaluate a general family of bilinear forms is investigated. An upper bound is obtained which is about half that obtained from naive arguments. In certain cases the best possible upper bound is obtained.     

Sampling Theorem and Discrete Fourier Transform on the Riemann Sphere

Using coherent-state techniques, we prove a sampling theorem for Majorana’s (holomorphic) functions on the Riemann sphere and we provide an exact reconstruction formula as a convolution product of N samples and a given reconstruction kernel (a sinc-type function). We also discuss the effect of over- and under-sampling. Sample points are roots of unity, a fact which allows explicit inversion formulas for resolution and overlapping kernel operators through the theory of Circulant Matrices and Rectangular Fourier Matrices. The case of band-limited functions on the Riemann sphere, with spins up to J, is also considered. The connection with the standard Euler angle picture, in terms of spherical harmonics, is established through a discrete Bargmann transform.      

Linear Complexity,k-Error Linear Complexity,and the Discrete Fourier Transform

Complexity measures for sequences of elements of a finite field play an important role in cryptology. We focus first on the linear complexity of periodic sequences. By means of the discrete Fourier transform, we determine the number of periodic sequences S with given prime period length N and linear complexity L_N, 0(S)=c as well as the expected value of the linear complexity of N-periodic sequences. Cryptographically strong sequences should not only have a large linear complexity, but also the change of a few terms should not cause a significant decrease of the linear complexity. This requirement leads to the concept of the k-error linear complexity L_N, k(S) of sequences S with period length N. For some k and c we determine the number of periodic sequences S with given period length N and L_N, k(S)=c. For prime N we establish a lower bound on the expected value of the k-error linear complexity.     

On the Windowed Fourier Transform and Wavelet Transform of Almost Periodic Functions

We present the windowed Fourier transform and wavelet transform as tools for analyzing persistent signals, such as bounded power signals and almost periodic functions. We establish the analogous Parseval-type identities. We consider discretized versions of these transforms and construct generalized frame decompositions. Finally, we bring out some relations with shift-invariant operators and linear systems.     

The Multiplicative Complexity and Algorithm of the Generalized Discrete Fourier Transform (GFT)

1.IntroductionSincethefastFouriertransformwasproposed,greatinterestsforfastalgorithmshavebeenaroused.Inthisarea,therehavebeenmanyachievements,whichhavgreatlystimulatedthedevelopmentofdigitalsignalprocessingandotherfields.Thecompu-tationalcomplekityistostudywhatthebestalgorithInwinbeforagivenproblem.TherearemanystandardsforaPpraisingwhetheranaJgorithmisgoodorbad.Innumericalcomputation,acommonstandardisthenumberofmultiplications,thatis,wesayanalgorithm'isgoodorbadifthenumberofmultiplicationsis…     

On the Order of Magnitude of the Double Fourier Transform

Mathematical Notes -     

Weighted integrability of multiplicative Fourier transforms

We study the relationship between the weighted integrability of a function and that of its multiplicative Fourier transform (MFT). In particular, for the MFT we prove an analog of R. Boas’ conjecture related to the Fourier sine and cosine transforms. In addition, we obtain a sufficient condition under which a contraction of an MFT is also an MFT. For the moduli of continuity ω satisfying N.K. Bari’s condition, we present a criterion for determining whether a function with a nonnegative MFT belongs to the class H ^ω .     

On Twisted Fourier Analysis and Convergence of Fourier Series on Discrete Groups

We study norm convergence and summability of Fourier series in the setting of reduced twisted group C ^*-algebras of discrete groups. For amenable groups, Følner nets give the key to Fejér summation. We show that Abel-Poisson summation holds for a large class of groups, including e.g. all Coxeter groups and all Gromov hyperbolic groups. As a tool in our presentation, we introduce notions of polynomial and subexponential H-growth for countable groups w.r.t. proper scale functions, usually chosen as length functions. These coincide with the classical notions of growth in the case of amenable groups.     

On the Fast Fourier Transform Inversion of Probability Generating Functions

The fast Fourier transform can be used to invert z transforms(including probability generating functions), but this applicationhas received little attention or use. This correspondence makesa case for the FFT as a standard numerical tool in queuing andother statistical analyses in order to obtain probability densityfunctions quickly and easily. Round-off and aliasing errorsare discussed briefly for the queuing analyst without a signalprocessing background. Several variations are described whichextend the accuracy and the utility of the method.     

Generalization of the multiplicative Fourier transform and its properties

We consider a new class of functions on the semiaxis for which the multiplicative Fourier transform can be defined. We prove equalities of Parseval type, an inversion formula and a condition for the validity of representation in the form of the multiplicative Fourier transform.