Discrete Fourier Analysis

Frontmatter

Chapter 1. The Finite Fourier Transform

Abstract

A good starting point is the finite Fourier transform that underpins the contents of the first thirteen chapters of the book.

M. W. Wong

Chapter 2. Translation-Invariant Linear Operators

Abstract

We give in this chapter the most basic class of linear operators from \(L^2(\mathbb{Z}_{N})\) into \(L^2(\mathbb{Z}_{N})\) in signal analysis.

M. W. Wong

Chapter 3. Circulant Matrices

Abstract

We have seen that the matrix (A)_F of a translation-invariant linear operator A :\( L^2(\mathbb{Z}_{N})\rightarrow L^2(\mathbb{Z}_{N})\) with respect to the Fourier basis F for \(L^2(\mathbb{Z}_{N})\) is a diagonal matrix. Can we say something about the structure of the matrix (A)_S with respect to the simplest basis for \(L^2(\mathbb{Z}_{N})\), namely, the standard basis S?

M. W. Wong

Chapter 4. Convolution Operators

Abstract

Translation-invariant linear operators from \(L^2(\mathbb{Z}_{N})\) into \(L^2(\mathbb{Z}_{N})\) can be given another representation that gives new insight into signal analysis. We first give a definition.

M. W. Wong

Chapter 5. Fourier Multipliers

Abstract

We now come to the last ingredient in the analysis of translation-invariant linear operators. We begin with the multiplication of two signals in \(L^2(\mathbb{Z}_{N})\).

M. W. Wong

Chapter 6. Eigenvalues and Eigenfunctions

Abstract

The results obtained in Chapters 2–5 can be used in the computation of eigenvalues of filters, which are given by translation-invariant linear operators. To recall, let A :\( L^2(\mathbb{Z}_{N})\rightarrow L^2(\mathbb{Z}_{N})\) be a filters, i.e., a translation-invariant linear operator. Then the matrix (A)_S of A with respect to the standard basis S for \(L^2(\mathbb{Z}_{N})\) is circulant. The filter A is in fact a convolution operator \( C_{b}\) with impulse response b, where b is simply the first column of the matrix A. The filter A is also a Fourier multiplier \(T_\sigma\) with symbol σ and σ = \(\hat{b}\) The matrix (A)_F of the filter A with respect to the Fourier basis F for L²(\(\mathbb{Z}_N\)) is diagonal, and is given by

$$(A)_F = \left(\begin{array}{ccccc} \lambda_0 & 0 & 0 & \ldots & 0\\ 0 & \lambda_1 & 0 & \ldots & 0\\ 0 & 0 & \lambda_2 & \ldots & 0\\ \vdots & \vdots & \vdots & \ldots & \vdots\\ 0 & 0 & 0 & \ldots & \lambda_{N-1}\\ \end{array}\right),$$

where λ_m is the eigenvalue of A corresponding to the eigenfunction F_m, m = 0, 1, …, N – 1.

M. W. Wong

Chapter 7. The Fast Fourier Transform

Abstract

The Fourier inversion formula in Theorem 1.7 states that for every signal z in \(L^2(\mathbb{Z}_{N})\), the coordinates (z)_F and (z)_S of z with respect to the Fourier basis F and the standard basis S for \(L^2(\mathbb{Z}_{N})\) respectively are related by

$$ (z)_F = \hat{z} = \Omega _{n}z = \Omega_{N}(z)s, $$

(1)

where \( \Omega_{N}\) is the Fourier matrix of order \( N \times N \). So, the change of basis from the standard basis S for L²(\(\mathbb{Z}_N\)) to the Fourier basis F for L²(\(\mathbb{Z}_N\)) is the same as multiplying an N × 1 column vector by the N × N matrix N, and it has been pointed out in Remark 1.11 that this entails N² multiplications of complex numbers. In view of the fact that in signal analysis, N is usually very big and therefore the task of carrying out N² complex multiplications is formidable even for high-speed computers. As a matter of fact, the number of additions should have been taken into account. Due to the fact that multiplication is much slower than addition on a computer, an idea of the speed of computer time required for the computation of the finite Fourier transform can be gained by just counting the number of complex multiplications.

M. W. Wong

Chapter 8. Time-Frequency Analysis

Abstract

Let z be a signal in \(L^2(\mathbb{Z}_{N})\). Then we say that z is time-localized near n₀ if all components z(n) are 0 or relatively small except for a few values of n near n₀. An orthonormal basis B for \(L^2(\mathbb{Z}_{N})\) is said to be time-localized if every signal in B is time-localized.

M. W. Wong

Chapter 9. Time-Frequency Localized Bases

Abstract

We have seen in the previous chapter that successive translations of a single signal in \(L^2(\mathbb{Z}_{N})\) can give us a time-localized orthonormal basis B for \(L^2(\mathbb{Z}_{N})\) such that the change of basis from the standard basis S for \(L^2(\mathbb{Z}_{N})\) to the basis B can be implemented by the FFT. The only thing that is missing from the basis B, though, is frequency-localization. Can we still do something with translations of signals in the construction of orthonormal bases, which are time-localized, frequencylocalized and amenable to computation by a fast algorithm? If we cannot do it with one signal, can we do it with two signals? The answer is amazingly yes. We explain how this can be done in this chapter.

M. W. Wong

Chapter 10. Wavelet Transforms and Filter Banks

Abstract

Let \(B=\{R_{2{k{\varphi}}}\}\begin{array}{ll}{M-1}\\{K=0}\end{array}\cup\{R_{2{k{\psi}}}\}\begin{array}{ll}{M-1}\\{K=0}\end{array} \) be a time-frequency localized basis for \(L^2(\mathbb{Z}_{N})\), where \(\varphi\) is the mother wavelet and \(\psi \) is the father wavelet. For every signal z in L²(\(\mathbb{Z}_N\)), we get, by the fact that B is an orthonormal basis for L²(\(\mathbb{Z}_N\)) and (8.3)

$$z = \sum\limits^{M-1}_{k=0} (z, R_{2k}\varphi)R_{2k}\varphi + \sum\limits^{M-1}_{k=0} (z, R_{2k}\psi)R_{2k}\psi.$$

(10.1)

M. W. Wong

Chapter 11. Haar Wavelets

Abstract

Let z be a signal in \(L^2(\mathbb{Z}_{N})\), where we now assume that \( N = 2^{l}\) for some positive integer \( l \). We let N = 2M, where M is a positive integer. As usual, we write

$$z = \left( \begin{array}{c}z(0)\\z(1)\\ \vdots \\ z(N-1) \end{array}\right).$$

M. W. Wong

Chapter 12. Daubechies Wavelets

Abstract

We first give a more detailed discussion of the small fluctuation property for the first-level Haar wavelets. Once this is understood, we can ask whether or not the same property can be upheld for other wavelets. It is in this context that we introduce the Daubechies wavelets in this chapter.

M. W. Wong

Chapter 13. The Trace

Abstract

We give in this chapter a class of linear operators A from \(L^2(\mathbb{Z}_{N})\) into \(L^2(\mathbb{Z}_{N})\) for which the trace tr(A) of A can be computed.

M. W. Wong

Chapter 14. Hilbert Spaces

Abstract

Our starting point is an infinite-dimensional complex vector space X. An inner product (,) in X is a mapping from \( X \times X \) into \( \mathbb{C}\) such that \( (\alpha{x}+ \beta{y},Z) = \alpha(x,y)+ \beta(y,z), \) \( (x,\alpha{y}+\beta{z})= \bar{\alpha}(x,y)+\bar{\beta}(x,z), \) \( (x,x)\geq 0, \) \((x,x)=0\Leftrightarrow x=0 \) for all x, y and z in X and all complex numbers \( \alpha\) and \(\beta \) Given an inner product (,) in X, the induced norm ║ ║ in X is given by

$$||x||^2 = (x,x),\quad x\epsilon X.$$

M. W. Wong

Chapter 15. Bounded Linear Operators

Abstract

A linear operator A on a Hilbert space X is said to be a bounded linear operator on X if there exists a positive constant C such that

$$||A_x|| \geq C||x||,\quad x \in X.$$

M. W. Wong

Chapter 16. Self-Adjoint Operators

Abstract

Of particular importance in operator theory are self-adjoint operators. To this end, we first recall the notion of the adjoint of a bounded linear operator A on a Hilbert space X. A linear operator B on X is said to be an adjoint of A if

$$(Ax,y) = (x, By), \quad x,y \epsilon X.$$

M. W. Wong

Chapter 17. Compact Operators

Abstract

A sequence \(\{x_j\}^{\infty}_{j=1}\) in a Hilbert space X is said to be bounded if there exists a positive constant C such that

$$||x_j|| \leq C, \quad j =1,2,\ldots.$$

M. W. Wong

Chapter 18. The Spectral Theorem

Abstract

We are now in a good position to state and prove the spectral theorem for selfadjoint and compact operators on Hilbert spaces.

M. W. Wong

Chapter 19. Schatten–von Neumann Classes

Abstract

We consider special classes of compact operators in this chapter known as Schatten–von Neumann classes \(S_p, 1 \leq p < \infty\). The most distinguished class is S ₂, which is made up of Hilbert–Schmidt operators.

M. W. Wong

Chapter 20. Fourier Series

Abstract

In this chapter we give a succinct and sufficiently self-contained treatment of Fourier series that we need for the rest of this book. A proper treatment of Fourier series entails the use of measure theory and the corresponding theory of integration, which we assume as prerequisites.

M. W. Wong

Chapter 21. Fourier Multipliers on $$\mathbb{S}^{1}$$

Abstract

The Plancherel theorem and the Fourier inversion formula for Fourier series are the basic ingredients for the study of filters on the unit circle \(\mathbb{S}^{1}\) with center at the origin.

M. W. Wong

Chapter 22. Pseudo-Differential Operators on $$\mathbb{S}^{1}$$

Abstract

We present in this chapter time-varying FM-filters that extend the FM-filters in the preceding chapter. These time-varying FM-filters are pseudo-differential operators on the unit circle \(\mathbb{S}^{1}\) with center at the origin.

M. W. Wong

Chapter 23. Pseudo-Differential Operators on $$\mathbb{Z}$$

Abstract

This chapter is a “dual” of the preceding chapter. Presenting this duality can contribute to a better understanding of pseudo-differential operators.

M. W. Wong

Backmatter