Discrete Fourier and Wavelet Transforms

An Introduction through Linear Algebra with Applications to Signal Processing

Roe W Goodman

• Publisher: WSPC
• Year: 2016
• eBook ISBN: 9789814725798
• Topic: Technology & Engineering
• Subtopic: Discrete Mathematics
• Index: Technology & Engineering

This textbook for undergraduate mathematics, science, and engineering students introduces the theory and applications of discrete Fourier and wavelet transforms using elementary linear algebra, without assuming prior knowledge of signal processing or advanced analysis.

It explains how to use the Fourier matrix to extract frequency information from a digital signal and how to use circulant matrices to emphasize selected frequency ranges. It introduces discrete wavelet transforms for digital signals through the lifting method and illustrates through examples and computer explorations how these transforms are used in signal and image processing. Then the general theory of discrete wavelet transforms is developed via the matrix algebra of two-channel filter banks. Finally, wavelet transforms for analog signals are constructed based on filter bank results already presented, and the mathematical framework of multiresolution analysis is examined.

Request Inspection Copy

This textbook for undergraduate mathematics, science, and engineering students introduces the theory and applications of discrete Fourier and wavelet transforms using elementary linear algebra, without assuming prior knowledge of signal processing or advanced analysis.

It explains how to use the Fourier matrix to extract frequency information from a digital signal and how to use circulant matrices to emphasize selected frequency ranges. It introduces discrete wavelet transforms for digital signals through the lifting method and illustrates through examples and computer explorations how these transforms are used in signal and image processing. Then the general theory of discrete wavelet transforms is developed via the matrix algebra of two-channel filter banks. Finally, wavelet transforms for analog signals are constructed based on filter bank results already presented, and the mathematical framework of multiresolution analysis is examined.

Request Inspection Copy

Readership: Undergraduate mathematics, science and engineering students interested in the theory and applications of discrete Fourier and wavelet transforms.
Key Features:

• Accessible account of the theory and applications of discrete Fourier and wavelet transforms based on ten years of classroom use
• Introduction of discrete wavelet transforms for digital signals via elementary lifting steps and filter banks
• Interweaving of mathematical theory with examples and applications to digital signal processing and image compression
• Computer explorations of signal and image processing in each chapter
• Mathematical concepts clarified by more than 90 figures and 75 exercises with detailed solutions

Chapter 1

Linear Algebra and Signal Processing

1.1Overview

In signal processing we sample an analog signal of a continuous variable (time or space) to obtain a digital signal of a discrete variable. This analog-to-digital conversion lets us manipulate signals using linear algebra: finite-dimensional vector spaces and their bases and dual bases, linear transformations and their matrices, and direct sums of vector spaces and the associated partitioned matrices. We begin with a brief review of these concepts, which will be used throughout the later chapters for signal processing by Fourier and wavelet transforms. As an illustration of the power of the linear algebra approach, we present the vector graphics method for efficient encoding of a two-dimensional image. Then we show how to use parametric families of affine transformations to animate the image. This application combines geometry and linear algebra in a vivid way.

We next recall the concepts of inner products, norms, orthogonal projections, and unitary matrices from linear algebra. These mathematical tools are important for signal processing because analog to digital conversion creates loss of information (aliasing and quantization error). Further signal processing, such as compression (for rapid transmission and compact storage), noise removal, and emphasizing selected features of a signal (such as the high frequencies in a sound or the edges in an image), also cause more loss of information. The distortion in the original signal caused by these processing steps can be quantified using the energy in a signal, which is the square of the norm of the vector representing the signal. When a digital signal is transformed by a unitary matrix, the energy is unchanged.

The vector space of periodic functions of a continuous variable plays an important role in signal processing. The basic idea of Fourier analysis is that the Fourier coefficients of a periodic function give the components of the function relative to the Fourier basis of oscillating waves. Thus the function can be viewed as a column vector with infinitely many components. The function can be well approximated (in the energy norm) by trigonometric polynomials, which correspond to column vectors with only finitely many nonzero components.

1.2Sampling and Quantization

An analog signal,¹ such as the continuously-varying voltage in an electric current or the gray scale levels in a black-and-white photograph on film, must be converted to digital form in order to be stored as a computer-readable file. This analog-to-digital conversion process is carried out in several steps. The first step is to sample the signal. Next the signal is quantized. Finally, the quantized signal is encoded for efficient storage and transmission.

Example 1.1 (Sampling an Analog Signal). Suppose the sound intensity levels in an audio signal are given by a function f(t) for a ≤ t ≤ b, where t represents time and f(t) is a real number. Choose N equall...

Table of contents

• Cover
• Halftitle
• Title
• Copyright
• Preface
• Contents
• 1. Linear Algebra and Signal Processing
• 2. Discrete Fourier Transform
• 3. Discrete Wavelet Transforms
• 4. Wavelet Transforms from Filter Banks
• 5. Wavelet Transforms for Analog Signals
• Appendix A Some Mathematical and Software Tools
• Appendix B Solutions to Exercises
• Bibliography
• Index