A new form of discrete real Fourier transform and its potential applications
ISSN: 2689-7636
##### Annals of Mathematics and Physics
Research Article       Open Access      Peer-Reviewed

# A new form of discrete real Fourier transform and its potential applications

### Grzegorz Plewa*

National Centre for Nuclear Research, Interdisciplinary Division for Energy Analyses, Wolodyjowskiego 83, 02-724, Warsaw, Poland
*Corresponding authors: Grzegorz Plewa, National Centre for Nuclear Research, Interdisciplinary Division for Energy Analyses, Wolodyjowskiego 83, 02-724, Warsaw, Poland, E-mail: grzegorz.plewa@ncbj.gov.pl
Received: 01 November, 2022 | Accepted: 23 November, 2022 | Published: 24 November, 2022

Cite this as

Plewa G (2022) A new form of discrete real Fourier transform and its potential applications. Ann Math Phys 5(2): 160-166. DOI: 10.17352/amp.000060

© 2022 Plewa G. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.

The paper will present a new version of a real discrete Fourier transform, based on a symmetric frequencies combination of sine and cosine functions. Basic aspects of the construction as well as the potential applications will be discussed. This will include elements of the standard Fourier analysis as well as applications to the class of differential equations in string theory.

### Introduction

A Fourier transform, FT [1,2] is a simple and interesting tool. Over the years, it has found applications in many fields. The simplicity and power of the transform lie in the ability to decompose an input expression into a series of periodic functions. The standard continuous FT can be defined as follows:

Here x(t) is a function to be transformed, while $\stackrel{˜}{x}\left(k\right)$ the function transforms, the complex Fourier coefficients. The equations above present a one-dimensional version of the transform. Generalization to arbitrary dimensions is trivial. In eq. (1) a non-standard convention was adopted, skipping coefficients by taking the following form of the Dirac Delta function

The Fourier transform plays an essential role in the signal analysis [3,4]. For instance, it can be used to determine a constituent pitch in a musical waveform. The constituent frequencies will are represented by non-zero transform coefficients $\stackrel{˜}{x}\left(k\right)$ . Having specified the transform, the original signal can be easily reproduced using eq. (1).

Decomposition into a series of differentiable functions is also useful in solving differential equations of various types and the transform could provide a convenient ansatz for the solution. Consider the relativistic Klein-Gordon equation [5,6]:

$\left(\square +{m}^{2}\right)\psi \left(x\right)=o,$

where $\hslash =c=1$ and $x=t,\stackrel{\to }{x}$ . It is easy to check that the equation above is satisfied by a four-dimensional version of the transform (1)

leading to the mass-shell constraint for the four-momentum P:

In general, the solution to (4) can be expressed as a combination of e-ipx and eipx. This is a starting point for constructing a scalar field in quantum field theory [6].

Eq. (4) illustrates the main advantages of taking a combination of the exponential function. Being the simplest one from a differential point of view, it is infinitely many times differentiable. Hence, it provides a useful ansatz for the solution. This remains partially true even for more complicated equations, where some further modifications of sine and cosine terms may be required. In particular, in [7] it was shown that certain combinations of sine functions provide an ansatz for numerical solutions of a class of differential equations in quantum cosmology.

The discrete equivalent of the form (1), discrete Fourier transform DFT, also called as fast Fourier transform (FFT), reads

Where t = 0,…,T-1 ; T is the number of the discrete label parametrizing xt.

The discrete transform is given by eqs. (7)-(8) is a direct equivalent of the continuous form (1)-(2) in the sense that in both cases the original quantity was expressed as a sum of oscillating functions multiplied by some coefficients. In the case of DTF, this is an ordinary finite sum. In the case of FT, the sum is replaced by the integral. There is also an additional multiplier 1/T in eq. (8), ensuring a good normalization of the transform1. A discrete transform is a convenient tool in numerical analysis based on a finite discrete number of steps and samples.

Despite the complex DFT being a powerful tool, in some cases one could be interested in even further improvement, constructing a real discrete Fourier transform. Such a transformation could be a preferred choice when the problem is real. In this paper it will be shown making the transformation real and modifying it, leads to the simplification of many problems.

The main goal of this paper will be to provide a new version of discrete real Fourier transformation, constructed in such a way that is real, it shares some features of the complex DFT. What these features are and why they are so important will be analyzed in more depth, based on specific examples.

The plan of the paper is the following.

Section 1 is the introduction, presenting basic aspects and applications of the Fourier transform.

In section 2 a class of optimization problems will be discussed, focusing on certain types of constraints. It will be shown that the standard discrete transform simplifies the form, however, increasing the number of variables. A symmetry simplifying the problem will be identified and a new version of the real Fourier transform will be suggested.

In section 3 the new version of the discrete Fourier transform will be constructed. The basic properties as well as alternative formulation will be discussed.

In section 4 the derived formulas will be verified, finding concrete applications in data analysis and a certain class of differential equations in string theory.

Section 5 will summarize the results.

##### Towards a modified version of DFT

Consider another example, a class of linear optimization problem (LP) in the form

$min\text{ }f\left({x}_{t},{y}_{t},...\right)$

$const{r}_{1}\left({x}_{t},{y}_{t},...\right)=0,$

$const{r}_{2}\left({x}_{t},{y}_{t},...\right)=o,...$

Where f stands for a linear combination of discrete variables xt, yt, possibly with some parameters, labeled by index $t\in \left\{0,...,T-1\right\}$ . The problem (9) is to find a minimum of the form f, satisfying the constraints constr1, constr2,... By assumption, all the variables and parameters will be real. For the sake of convenience, t the label will be associated with time.

Suppose that one of the constraints takes the form

Where ∆xt is another real variable. Consider the Fourier transform of the constraint (10). Using (7), one finds

$\sum _{t=0}^{T-1}\left({c}_{n}\text{ }{e}^{-2\pi in/T}-{c}_{n}-\Delta {c}_{n}\right)\mathrm{exp}\left(\frac{2\pi in}{T}\right)=o,$

Where cn and ∆cn are DFT Fourier transforms of xt and ∆xt. Eq. (11) implies

Note that the formula above is non-recursive, while the original one, given by eq (10) is recursive. In the case of eq. (10) to get the constraint in the next moment of time, the previous one is required. On the other hand, in the case of eq. (12) there are no such correlations. This makes a significant simplification of the problem. If all the constraints were of this form, problem (9) could easily be decomposed into smaller sub-problems.

The source of the simplification is the response of the exponential function:

However, the fact that one or more of the constraints take a simpler form does not mean the problem (9) will be simpler. If it is real, the Fourier transform will introduce complex variables and possibly complex parameters (if transforming the whole of the original problem). In particular, cn, ∆cn are complex, while the original variables, xt and ∆xt are real. This doubles the number of variables after transformation because cn, ∆cn will contain real and imaginary parts2. In what follows, the number of variables will be doubled in the Fourier formulation of the problem. The complex DFT provides an interesting simplification of the form of some relations, however, the price would be a greater number of variables (unknowns) in the corresponding complex formulation.

A way out is to consider a real transformation, a real equivalent of complex DFT. This would eliminate complex variables right from the beginning. The idea of real discrete Fourier transform (RDTF) is not new and has been already discussed. In particular, the following [2] defines

The inverse transform specifying the remaining coefficients cn has also a simple form given explicitly in [2]. The problem is, the transform (14) has a much worse response. In particular, applying (14) to the constraint (10) no simplification will be obtained. Instead, a far more complicated formula will get in the result.

Fortunately, there is another option: modification of the real transform. It would be interesting to construct it in such a way that some aspects of the symmetry (13) will still be present. In what follows, the main requirement for the construction will be to simplify the constraint (10).

Consider a family of transforms, given by a general linear transformation Ltn:

Keeping in mind eq. (13), the following symmetry is required:

Translation in time (13) is reflected by new values of the coefficients cn∆t. However, it does not affect the transformation matrix Ltn. For this reason, the transform Ltn will be called translationally invariant. The standard DFT is an example of such an invariant transform, while (14) is not. It is straightforward to check that the transform given by eqs. (16)-(17) simplifies the constraint (10), making it non-recursive.

##### Real transform

A. Translationally invariant real Fourier transform: The real Fourier transform satisfying eq. (17) can be constructed starting with the following combination of sine and cosine functions:

where $t\in \left\{0,...,T-1\right\}$ and N is an additional parameter of the transform, the analog of N in (15). In contrast to eq. (15), it will be not fixed. Note that we will get the exact result only if N > T/2. Otherwise the number of transform parameters, the coefficients an, bn, will be smaller than the number of xt.

The transform is symmetric in frequencies in the sense that sine and cosine functions are defined on the same set of discrete frequencies (there is no bo term, however, because sin(0) = 0). It is easy to check that the form (18) is translationally invariant in the sense of eq. (17). Hence, it will simplify eq. (10) making it non-recursive.

Compared with the standard DFT or (14) the base frequency of the transform is two times smaller, i.e. instead of $\mathrm{sin}/\mathrm{cos}\left(2n\pi t/N\right)$ we get $\mathrm{sin}/\mathrm{cos}\left(n\pi t/N\right)$ . This is to avoid some peculiar periodicities t3. On the other hand, this reduction makes construction harder. For example, one finds the following relation:

Where δnm is the Kronecker delta. On the other hand, lowering the frequency one finds

$\sum _{k=0}^{N-1}\left[\mathrm{cos}\left(\frac{n\pi k}{N}\right)\mathrm{cos}\left(\frac{m\pi k}{N}\right)+\mathrm{sin}\left(\frac{n\pi k}{N}\right)\mathrm{sin}\left(\frac{m\pi k}{N}\right)\right]=$

To get the inverse transform of eq. (18), i.e. to find the Fourier coefficients in eq. (18) one can use the more complicated relation (20), combining it with some rotations. This results in the following Fourier coefficients

and

Note that the last equations are much more complicated than the corresponding formulas for DFT and RDFT. This may cause some further limitations in practical applications. It will be shown later in the paper that, at least for some applications, this is not a problem. Also note, that the response of the transform is still worse than the complex DFT. This is something that cannot be overcome by constructing a real transform.

As mentioned, N is a transformation parameter. It specifies the number of transform coefficients. If the number is smaller than the number of moments of time T, i.e. N < T/2, there is no chance to reproduce the exact result from the transform4. In such a case the transform will provide a non-linear approximation, resulting in some internal additional periodicities. The smallest N, the worse the precision. If N < T/2 the number of transform coefficients and so sine and cosine terms, will be greater than the number required to reproduce the original data. The transform will reproduce the correct result, however, it will contain more coefficients than required. Consideration of such parameter values may seem pointless. In the case of application to LP, this would artificially increase the number of variables. Still, keeping N to be an arbitrary parameter would be better from a conceptual point of view. Presenting the new form of the transform, one makes it as general as possible.

Let N0 = N stands for the boundary value, corresponding to the minimum number of coefficients necessary to reproduce the exact result. Using the simple relation for the number of Fourier coefficients 2N0 - 1 = T (there are N0 cosine coefficients an and N0 - 1 sine coefficients bn<), one finds:

Note that if T is even, the number of transform coefficients will be one more than the number of moments of time T. Clearly, one more transform coefficient is not much compared to complex DFT which, when applied to a real LP problem, doubles the number of variables. The case N = N0 is of special importance and will be called boundary''. As mentioned, if N < N0 the transform is not exact, if N > N0 it contains more sine and cosine terms then is needed to reproduce the exact result.

The case N = T/2 (assuming T is even) is also special because of the matrix $N{\delta }_{t{t}^{\prime }}+\frac{1}{2}{\sigma }_{t{t}^{\prime }}$ in eq. (22) has zero determinant. The Fourier coefficients (21) are ill-defined and one should require N ≠ T/2. However, this does not concern the boundary case (24).

B. Alternative formulation: Compared to (14), the transform (18) can be re-expressed in a more compact way, defining a single set of coefficients:

Where θ stands for a Heaviside function, defined as follows

The above formulation is closer to the one adopted in [2] and can be more convenient in applications.

##### Applications

Having found a new form of the transform, this chapter will present examples of its applications. The first will involve finding the transform of a particular signal and investigating an approximation based on incomplete transformation. In the second case, the transform will be used to construct an ansatz for a class of nonlinear differential equations in string theory.

##### Data analysis

The goal will be now to verify eqs. (18) and (21) find the Fourier transform of an example signal and then reproduce the signal from the transform. Doing this some of the Fourier coefficients will be intensionally skipped. This is to examine the nonlinear approximation provided by the transformation.

As a signal, consider an example solar capacity factor. The capacity factor is a time-dependent, dimensionless ratio of electrical energy output from a solar panel. Let t stands for hours in a year and let Et will be the corresponding energy. By definition

where P is the nominal power of the solar panel, while ItPV is the capacity factor. An example capacity factor will be used, taking into account the whole year with hourly resolution; a series containing 8760 terms.

The results of the boundary version of the transform were depicted in Figure 1. Although eqs. (21)-(22) are more complicated than in the case of the standard RDFT or DFT, the capacity factor was transformed with ease.

Two cases have been analyzed. In both of them, the Fourier transform (18) of the capacity factor was initially found. In the next step 5% and 85% of the smallest in amplitude Fourier coefficients were skipped, respectively.

Neglecting only 5% the required transform parameters leads to a fairly good result. On the other hand, skipping 85% them leads to high discrepancies. Still, some basic elements of the initial shape are still visible. The more Fourier coefficients, the better the approximation. This agrees with the expectations, providing numerical proof of the formulas (18) and (21). Keeping 100% the Fourier coefficients would lead to the perfect match of blue and orange lines.

Applications to differential equations: Another example of the use of the transform (18) will be solving a class of differential equations in string theory. More specifically, equations based on the application of the Ryu-Takayanagi formula for entanglement entropy within AdS/CFT correspondence will be discussed.

Ryu-Takayanegi formula: AdS/CFT correspondence [8,9] is a practical realization of the holohraphic principle [10], stating that a non-gravitational quantum system has a dual, gravitational description in higher dimensional spacetime. In the case of type IIB superstring theory, this leads to an effective relationship between states of strongly coupled, conformal Yang-Mills theory and classical gravity. From a practical point of view, this means that some aspects of the quantum system can be extracted from Einstein's equations in higher dimensional spacetime.

The Ruy-Takayanagi formula [11] is a holographic description of the quantum entanglement of two systems: a given quantum system and its complement, separated by some boundary. In the holographic description, the boundary can be viewed as extended to a higher dimensional space; a surface in the bulk. This surface is defined to be anchored at the boundary of the higher-dimensional space in such a way, that it coincides with the separation. It is also required for the surface to be minimal. The entanglement entropy between a spatial region V and its complement $\left(\stackrel{˜}{V}\right)$ is given by [12]:

where the extremization is over all surfaces v in the spacetime bulk, homologous to the boundary region V , and lp is a Planck constant.

Consider a spherical region of a radius and adopt Poincare coordinate system in the bulk (t, xd-1, z) which stands for the dimension of the boundary [12]. In the dual holographic description, thermal states in the region are represented by a black brane in the bulk. As shown in [12], eq. (29) leads to the following form of the surface:

where

ZH- event horizon of the brane in Poincare coordinates, Ωd-2 - an area of the unit d-2 sphere. In (30) z(r) stands for geodesics determining the minimal surface: a d+1 coordinate being a function of the boundary spherical coordinate r ∈ [0,R](see [12] for more details). The horizon ZH is related to the Hawking temperature T via:

In the case of pure anti-de-Sitter space ${z}_{H}\to \infty$ and the temperature goes to zero (in the sense, we have vacuum AdS). Eq. (31) simplifies, and the minimal surface is specified by a simple geodesic:

This is an analytical result, independent of the dimension d.

On the other hand, if the temperature is non-zero, the equations are much more complicated and cannot be solved analytically. Extremizing (30), i.e. applying Euler-Lagrange equations

one finds

$2\left(d-1\right)r{z}_{H}^{2d}\left({{z}^{\prime }}^{2}+1\right)-r{z}_{H}^{d}{z}^{d}\left(\left(d-2\right){{z}^{\prime }}^{2}+4\left(d-1\right)\right)+2{z}_{H}^{2d}z\left(\left(d-2\right){{z}^{\prime }}^{3}+$

This should be supplemented by the following boundary conditions

reflecting the meaning of the spherical separating surface.

Spectral nonlinear method: The equation (35) can be solved numerically using a variant of the spectral method [13,14] and the ansatz provided by the real transform (18). Rewrite symbolically the equation (35) as

$0z=O,$

where the operator 0 is defined compared with eq. (35). Consider the following ansatz:

Where ωN is given by eq. (23). The factor $\sqrt{{R}^{2}-{r}^{2}}$ is because in the limit T → 0 it is expected to reproduce the solution (33). The radius R was incorporated into the arguments of sine and cosine functions to make them dimensionless (r is of the dimension of length). Despite these modifications, eq. (39) can still be regarded as a Fourier series of the form (18).

The boundary condition eq. (36) is trivially satisfied by the transform (39). The condition (37) leads to the following constraint

$\sum _{n=1}^{N-1}n{b}_{n}=o.$

Eq. (38) can be now solved numerically requiring it is satisfied for a given, finite set of points rk ∈ [0,R], k = 0,…,2N -1 (the transform (39) has 2N - 1 parameters). A convenient choice for this point is Chebyshev's nodes [13,14]. Adopting this choice improves numerical precision [13,14]. The problem of finding the Fourier coefficients in the ansatz (39) can be expressed as an optimization problem, in which the following form is minimized

together with the boundary condition (40) and the additional supplementary constraints:

The last is important because otherwise z could be negativ5 The result of the procedure is the values of an and bn. The strategy resembles the standard spectral methods [13,14]. There are two crucial differences, however. First, optimization was used instead of eigenproblem. Second, both cosine and sine functions are present in the ansatz, in the combination specified by the transform (18).

Nonlinear optimization can be performed in Mathematica for various temperatures and various d. Below are presented solutions for d = 2 and d = 4, letting N = 5. The latter was intensionally made small. The boundary version of the transform was adopted in the sense that the number of Chebyshev's nodes matches the number of Fourier coefficients.

Depending on the temperature, the resulting precision given by the square root of the form (41) is about 10-4 - 10-7. With a small N, it is a very good precision. This means that the transform provides a very good ansatz. The purple line T = 0 matches perfectly the curve $z=\sqrt{1-{r}^{2}}$ , expected for the pure AdS case with zero temperature. As the temperature increases, the boundary value z(r = 0) decreases and the geodesic becomes increasingly different from the case T = 0. This is something that can be expected from a physical point of view.

For a given d and T increasing N does not affect the shape of the curve. The only change is the bigger number of Fourier coefficients an , bn. In general, both of them are non-zero and so both sine and cosine terms are present in the result6. This indirectly supports the idea of considering the combination of cosine and sine functions in the ansatz.

Having found the geodesics z(r), one may use it to calculate the corresponding entanglement entropy given by eq. (29). In particular, one can examine, how it changes with temperature and spacetime dimension. However, this will not be discussed in this paper. In fact, the Ryu-Takayanagi formula was used to provide an interesting example of the highly-nonlinear differential equation. The equation has been solved numerically in a new way, based on a modified spectral method and a new, modified real Fourier transform.

### Summary

The paper presents a new version of a real discrete Fourier transform, based on symmetric frequencies combination (14). The motivation was to make the real transformation as much similar to the complex DFT as possible. Taking a closer look at the example constraint (10), a criterion of translational invariance has been identified. It was shown, that using translationally invariant real discrete transform, a class of LP problems can be significantly simplified.

The invariant transform was constructed by postulating its form and finding the corresponding Fourier coefficients. The transform was examined numerically by calculating the Fourier transform of an example capacity factor. Having specified the coefficients in the Fourier expansion, the input capacity factor was reproduced using the transform. In the reproduction procedure, some of the Fourier terms were intensionally omitted, allowing to test of nonlinear approximation based on the transformation. A good result was obtained for five percent compression. Decreasing the number of terms (Fourier frequencies) the result starts to get worse, however, even at eighty-five percent of frequencies removed it still resembles the input curve.

The second application of the transform was solving a class of differential equations, originated by the Ryu-Takayanagi formula for holographic entanglement entropy. A modified, nonlinear spectral method has been proposed. In this method, the problem of solving differential equations is replaced by a nonlinear optimization problem with the ansatz provided by translationally invariant real Fourier transform. Applying to the thermal states separated by a spherical region, the method was used to find numerically the geodesics specifying the minimal area in the entropy form (29). In solving the corresponding differential equation, a high precision was achieved despite a relatively small number of Fourier terms. The boundary case of zero temperature (pure ani-de-Sitter space) has been successfully reproduced. Both sine and cosine terms were present in the solution. The latter shows that the modified real discrete Fourier transform provides a much better ansatz than the standard combination of cosine functions.

In summary, the main conclusion of the paper was the construction of a new form of the real discrete Fourier transform and the identification of its potential applications. The transform has been tested on simple and more complicated examples. The analysis can be generalized in several different ways. For instance, one can examine applications of the proposed spectral method to a wider class of differential equations, or calculate the entanglement entropy in the limit of high temperatures. The real transform also opens the door for the application of Fourier transform to linear programming (LP). In particular, it was shown, that a certain class of the constraints of the form (10) can be simplified using complex DFT. However, this transform doubles the number of variables. The standard real RDFT [2] makes the problem more difficult. The new version of the transform is free of these restrictions. The only limitation is that the formulas for Fourier coefficients are more complicated than in the standard DFT and RDFT, causing potential difficulties and numerical errors. However, this is not a problem for applications to linear programming or differential equations. In the case of data analysis, it was shown that a yearly series with hourly resolution can be easily transformed and the transform perfectly reproduces the input data.

1. Bailey DH, Swarztrauber PN. A Fast Method for the Numerical Evaluation of Continuous Fourier and Laplace Transforms. Scientific Computing. 1993; 15:1105-11010.
2. Ersoy OK, Hu NC. Fast algorithms for the real discrete Fourier transform, CASSP-88., International Conference on Acoustics, Speech and Signal Processing. 1988; 3:1902-1905.
3. Wilson R, Calway AD, Pearson ERS. A generalized wavelet transform for Fourier analysis: the multiresolution Fourier transform and its application to image and audio signal analysis. IEEE Transactions on Information Theory. 1992; 38.
4. Valluri SR, Dergachev V, Zhang X, Chishtie FA. Fourier transform of the continuous gravitational wave signal, Phys. Rev. D. 2021; 104:024065.
5. Weinberg S. The Quantum theory of fields. Foundations, Cambridge University Press. 2005; 1.
6. Srednicki M. Quantum field theory, Cambridge University Press. 2007.
7. Góźdź A, Piechocki W, Plewa G, Trześniewski T. Universe. 2021; 7:49. 2003.03990.
8. Maldacena JM. The Large N limit of superconformal field theories and supergravity. Int. J. Theor. Phys. 1999; 38:1113-1133; 9711200.
9. Hubeny VE. The AdS/CFT Correspondence. Class. Quant. Grav. 2009; 2015:32; 124010.
10. Susskind L. The World as a hologram. J. Math. Phys. 1995; 36:6377-6396; 1305.3182.
11. Ryu S. Tadashi Takayanagi Holographic derivation of entanglement entropy from AdS/CFT. Phys. Rev. Lett. 2006; 96:181602:0603001.
12. Blanco DD. Horacio Casini Ling-Yan Hung Robert C Myers, Relative Entropy and Holography. JHEP. 2013; 08:060;1305.3182.
13. Grandclement P, Novak J. Spectral methods for numerical relativity. Living Rev. Rel. 2009; 12:0706.2286.
14. Janik RA, Plewa G, Soltanpanahi H. Michal Spalinski Linearized nonequilibrium dynamics in nonconformal plasma, Phys. Rev. D. 2015; 91:126013; 1503.07149.