Table of Contents#### Download Safari Books Online apps: Apple iOS | Android | BlackBerry

Entire Site

Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.

2 CHAPTER 1 Sparse Representations illustrate the strong connection between well-structured mathematical tools and fast algorithms. 1.1.1 The Fourier Kingdom The Fourier transform is everywhere in physics and mathematics because it diago- nalizes time-invariant convolution operators. It rules over linear time-invariant signal processing, the building blocks of which are frequency filtering operators. Fourier analysis represents any finite energy function f (t) as a sum of sinusoidal waves e i t : 1 ^ f ( ) e i t d . f (t) (1.1) 2 ^ The amplitude f ( ) of each sinusoidal wave e i also called Fourier transform: ^ f ( ) f (t) e t is equal to its correlation with f , dt. (1.2) i t ^ The more regular f (t), the faster the decay of the sinusoidal wave amplitude | f ( )| when frequency increases. When f (t) is defined only on an interval, say [0, 1], then the Fourier transform becomes a decomposition in a Fourier orthonormal basis {e i2 mt } m Z of L 2 [0, 1]. If f (t) is uniformly regular, then its Fourier transform coefficients also have a fast decay when the frequency 2 m increases, so it can be easily approximated with few low-frequency Fourier coefficients. The Fourier transform therefore defines a sparse representation of uniformly regular functions. Over discrete signals, the Fourier transform is a decomposition in a discrete orthogonal Fourier basis {e i2 kn/N } 0 k N of C N , which has properties similar to a Fourier transform on functions. Its embedded structure leads to fast Fourier trans- form (FFT) algorithms,which compute discrete Fourier coefficients with O(N log N ) instead of N 2 . This FFT algorithm is a cornerstone of discrete signal processing. As long as we are satisfied with linear time-invariant operators or uniformly regular signals, the Fourier transform provides simple answers to most questions. Its richness makes it suitable for a wide range of applications such as signal transmissions or stationary signal processing. However, to represent a transient phenomenon--a word pronounced at a particular time, an apple located in the left corner of an image--the Fourier transform becomes a cumbersome tool that requires many coefficients to represent a localized event. Indeed, the support of ^ e i t covers the whole real line, so f ( ) depends on the values f (t) for all times t R. This global "mix" of information makes it difficult to analyze or represent any ^ local property of f (t) from f ( ). 1.1.2 Wavelet Bases Wavelet bases, like Fourier bases, reveal the signal regularity through the ampli- tude of coefficients, and their structure leads to a fast computational algorithm.