The XFT quadrature in discrete Fourier analysis (Q1728681)

The Fourier integral transform is one of the oldest and most widely used integral transforms in mathematics and applied fields, such physics and engineering. Although there are tables for the Fourier transform and its inverse, in many real applications the transform has to be computed numerically which amounts to discretizing the transform. The most common technique used for that is the Discrete Fourier Transform, known as DFT. Different algorithms have been developed to speed up the numerical computation of the DFT. Chief among them is the Fast Fourier Transform or FFT. \par In the last thirty years or so another integral transform, known as the Fractional Fourier Transform (FrFT), which is a generalization of the Fourier transform, has become the focus of many research activities because of its applications in optics and signal processing. As with the case of the Fourier transform, real applications require numerical techniques to compute the FrFT. One of those new techniques is the main subject of this book which is called eXtended Fourier transform or XFT for short. \par The XFT was developed by the author and some of his collaborators in a series of papers. This book is both a compilation of and an addition to their work. The XFT yields a quadrature for the fractional Fourier transform. By a linear quadrature, we mean a linear numerical integration formula of the form \[ \int_a^b f(t) dt \approx \sum_{k=1}^N \lambda_k f(t_k), \quad a\leq t_1 < t_2 < \cdots < t_N\leq b . \] The book comprises five chapters and two appendices: Appendices A and B describe algorithms and programming in MATHEMATICA and MATLAB to implement XFT. Chapter One, which is just two pages, is a short introduction to the book. \par Chapter Two is an introduction to the Discrete Fourier Transform (DFT) in one and two variables. An application of the DFT in digital imaging and in computing the Jacobi Elliptic Function is given. It is shown that the effect of translation in the transform causes shift in the image. \par Chapter Three is the inner core of the book and in which the author introduces the XFT, its properties, and applications. Because XFT is the central topic of the book, we will try to introduce its main idea in the next few paragraphs. \par The Hermite functions \(\left\{ h_n(t)\right\}_{n=0}^\infty ,\) which form an orthogonal basis for \(L^2(\mathbb R),\) are eigenfunctions of the Fourier transform with corresponding eigenvalues \(\left\{ e^{in\pi /2}\right\}_{n=0}^\infty.\) The fraction Fourier transform, which is a generalization of the Fourier transform, is an integral transform that depends on an angle \(\theta\) and whose eigenfunctions are the Hermite functions but with corresponding eigenvalues \(\left\{ e^{in\theta}\right\}_{n=0}^\infty,\) where \(0\leq \theta \leq 2\pi\). \par The fractional Fourier transform of a function \(f\) is defined as \[\mathcal F [f(t);x,\Theta]=\frac{e^{i(\pi/4-\Theta/2)}}{\sqrt{2\pi \sin\Theta}} \int_{\mathbb R} \exp(ixt\csc\Theta-i(x^2+t^2)\cot\Theta/2) f(t)dt .\] When \(\Theta=\pi/2\), the fractional Fourier transform reduces to the standard Fourier transform. \par The author's starting point is the construction of a discrete version of the Hermite functions. This is done by using the recurrence relation for the Hermite polynomials \(H_n(t)\), \[H_{n+1}(t)+2nH_{n-1}(t)=2tH_n(t) \] to obtain a matrix equation of the form \(\Xi \mathfrak H=t\mathfrak H\), where \(\mathfrak H^T=(H_0, H_1, \cdots)\) is a vector with the Hermite polynomials as its components. From the matrix \(\Xi\), a Jacobian matrix X is obtained and when truncated, it leads to the matrix eigenvalue equation \[Xu_k=t_ku_k,\ \ \ k=1,2,\dots,N ,\] where \(t_k\) are the zeros of the Hermite polynomial \(H_N(t)\), i.e., \[H_N(t_k)=0,\ \ k=1,2,\dots,N. \] The vectors \((u_{k1}, u_{k2},\dots,u_{kN})\) are normalized discrete version of the Hermite function and they share similar properties to them, such as orthogonality and parity. \par To construct a discrete version of the fractional Fourier transform, the author begins with an \(N\times N\) diagonal matrix whose \(k\)th nonzero element is \(\sqrt{2\pi}z^m\), where \(z\) is a complex number with \(|z|\leq 1\) and \(m=0,1,\dots,N-1\). From this matrix another matrix \(\mathcal F(z)\), whose \(n\)th eigenvector is \((u_{k1}, u_{k2},\dots,u_{kN})^T\) with eigenvalue \(z^n\), is constructed. \par In doing so, the author extends the range of the fractional Fourier transform by replacing the parameter \(\Theta\), which is on the unit circle, by an arbitrary complex number \(|z|^n \), inside the unit circle which yields the following version of the fractional Fourier transform of an appropriate function \(f\) as given by \[\mathfrak F [f(s):t,z]=\sqrt{\frac{2}{1-z^2}} \int_{\mathbb R} \exp\left(-\frac{(1+z^2)(t^2+s^2)-4zst}{2(1-z^2)} \right) f(s)ds ,\] where \(z=r^{i\Theta}\), \(0<\Theta<2\pi\), \(0\leq r\leq1\). \par The integral transform \(\mathfrak F\) is shown to have the quadrature formula \[\mathfrak F [f(s):t_j,z]\approx\sum_{k=1}^N(\mathcal F(z))_{jk}f(t_k) .\] When \(z=i\), this setup gives a discrete version of the fact that the Hermite functions are eigenfunctions of the matrix \(\mathcal F(i)\) by \(\mathcal F_{jk}\), it si shown that the following quadrature formula holds \[\int_{-\infty}^\infty e^{it_jt}f(t)dt\approx \sum_{k=1}^N \mathcal F_{jk}f(t_k) .\] The author then proceeds to derive properties of the matrix \({\mathcal F}(z),\) such as differentiation matrices associated with the XFT and fast algorithms for computing the XFT and the fractional Fourier transform. Numerical performance of the logarithms and comparison with the DFT is given. The chapter is concluded with an introduction to two-dimensional XFT. \par In Chapter Four the author surveys applications of the XFT in a variety of topics ranging from image processing to solving boundary-value problems. Because images are two-dimensional, XFT in two dimensions is the right tool to use. The first application discussed deals with a random dot autostereogram where a procedure based on XFT to retrieve a hidden figure in a random dot autostereogram, as well as, an algorithm to conceal a digital image inside another image, are given. \par After showing how the XFT is used in edge detection, the author proceeds to discuss how the XFT is used in solving linear and non-linear boundary-value problems involving differential and fractional differential equations in one and two variables. Some of the partial differential equations considered are the Kdv and Burger's equations. \par In Chapter Five, a discretization of the fractional Fourier transform and the linear canonical transform using XFT is discussed in one and two variables. Recall that the linear canonical transform, which is a generalization of the fractional Fourier transform is given by \[ {\mathcal L}^{[a,b,c,d]}[f,t]=\frac{1}{\sqrt{2\pi i b}} \int_{\mathbb R} \exp\left(\frac{i}{2b} \left[-2tx + (d t^2 +a x^2)\right] \right) f(x)dx, \] where \(ad-bc=1.\) When \(a=d=\cos \theta,\) and \(b=-c=\sin \theta ,\) we obtain the fractional Fourier transform. The chapter is concluded with an application of the linear canonical transform in digital steganography. \par The book is a good source to learn about XFT, but in my opinion it lacks two features: the first is the lack of an index. The second is that since the XFT is the main subject of the book, it should have been stated or highlighted in a definition format instead of leaving it to the reader to figure out what it is.