A Wavelet Tour of Signal Processing

The Sparse Way


  • Stephane Mallat, École Polytechique, Centre de Mathématiques Appliquées, Paris, France

Mallat's book is the undisputed reference in this field - it is the only one that covers the essential material in such breadth and depth. - Laurent Demanet, Stanford UniversityThe new edition of this classic book gives all the major concepts, techniques and applications of sparse representation, reflecting the key role the subject plays in today's signal processing. The book clearly presents the standard representations with Fourier, wavelet and time-frequency transforms, and the construction of orthogonal bases with fast algorithms. The central concept of sparsity is explained and applied to signal compression, noise reduction, and inverse problems, while coverage is given to sparse representations in redundant dictionaries, super-resolution and compressive sensing applications.Features:* Balances presentation of the mathematics with applications to signal processing* Algorithms and numerical examples are implemented in WaveLab, a MATLAB toolbox* Companion website for instructors and selected solutions and code available for studentsNew in this edition* Sparse signal representations in dictionaries* Compressive sensing, super-resolution and source separation* Geometric image processing with curvelets and bandlets* Wavelets for computer graphics with lifting on surfaces* Time-frequency audio processing and denoising* Image compression with JPEG-2000* New and updated exercisesA Wavelet Tour of Signal Processing: The Sparse Way, third edition, is an invaluable resource for researchers and R&D engineers wishing to apply the theory in fields such as image processing, video processing and compression, bio-sensing, medical imaging, machine vision and communications engineering.Stephane Mallat is Professor in Applied Mathematics at École Polytechnique, Paris, France. From 1986 to 1996 he was a Professor at the Courant Institute of Mathematical Sciences at New York University, and between 2001 and 2007, he co-founded and became CEO of an image processing semiconductor company.Companion website: A Numerical Tour of Signal Processing
View full description


R&D engineers and university researchers in image and signal processing; Signal processing and applied mathematics graduates


Book information

  • Published: December 2008
  • ISBN: 978-0-12-374370-1


"There is no question that this revision should be published. Mallat’s book is the undisputed reference in this field - it is the only one that covers the essential material in such breadth and depth." - Laurent Demanet, Stanford University

Table of Contents

Preface to the Sparse EditionNotations1. Sparse Representations1.1 Computational Harmonic Analysis 1.1.1 Fourier Kingdom 1.1.2 Wavelet Bases 1.2 Approximation and Processing in Bases 1.2.1 Sampling with Linear Approximations1.2.2 Sparse Non-linear Approximations 1.2.3 Compression 1.2.4 Denoising 1.3 Time-Frequency Dictionaries 1.3.1 Heisenberg Uncertainty 1.3.2 Windowed Fourier Transform 1.3.3 Continuous Wavelet Transform 1.3.4 Time-Frequency Orthonormal Bases 1.4 Sparsity in Redundant Dictionaries 1.4.1 Frame Analysis and Synthesis 1.4.2 Ideal Dictionary Approximations1.4.3 Pursuit in Dictionaries 1.5 Inverse Problems 1.5.1 Diagonal Inverse Estimation 1.5.2 Super-Resolution and Compressive Sensing 1.6 Travel Guide 2. Fourier Kingdom2.1 Linear Time-Invariant Filtering2.1.1 Impulse Response 2.1.2 Transfer Functions 2.2 Fourier Integrals 2.2.1 Fourier Transform in L1(R) 2.2.2 Fourier Transform in L2(R) 2.2.3 Examples 2.3 Properties 2.3.1 Regularity and Decay 2.3.2 Uncertainty Principle 2.3.3 Total Variation 2.4 Two-Dimensional Fourier Transform 2.5 Exercises 3. Discrete Revolution3.1 Sampling Analog Signals 3.1.1 Shannon-Whittaker Sampling Theorem 3.1.2 Aliasing 3.1.3 General Sampling and Linear Analog Conversions 3.2 Discrete Time-Invariant Filters 3.2.1 Impulse Response and Transfer Function 3.2.2 Fourier Series 3.3 Finite Signals 3.3.1 Circular Convolutions 3.3.2 Discrete Fourier Transform 3.3.3 Fast Fourier Transform 3.3.4 Fast Convolutions 3.4 Discrete Image Processing 3.4.1 Two-Dimensional Sampling Theorems 3.4.2 Discrete Image Filtering 3.4.3 Circular Convolutions and Fourier Basis 3.5 Exercises 4 Time Meets Frequency4.1 Time-Frequency Atoms 4.2 Windowed Fourier Transform 4.2.1 Completeness and Stability 4.2.2 Choice of Window 4.2.3 Discrete Windowed Fourier Transform 4.3 Wavelet Transforms 4.3.1 Real Wavelets 4.3.2 Analytic Wavelets4.3.3 Discrete Wavelets 4.4 Time-Frequency Geometry of Instantaneous Frequencies4.4.1 Windowed Fourier Ridges 4.4.2 Wavelet Ridges 4.5 Quadratic Time-Frequency Energy4.5.1 Wigner-Ville Distribution 4.5.2 Interferences and Positivity 4.5.3 Cohen¡¯s Class4.5.4 Discrete Wigner-Ville Computations 4.6 Exercises 5. Frames 5.1 Frames and Riesz Bases5.1.1 Stable Analysis and Synthesis Operators 5.1.2 Dual Frame and Pseudo Inverse 5.1.3 Dual Frame Analysis and Synthesis Computations 5.1.4 Frame Projector and Reproducing Kernel 5.1.5 Translation Invariant Frames 5.2 Translation Invariant Dyadic Wavelet Transform 5.2.1 Dyadic Wavelet Design 5.2.2 ¡°Algorithme `a Trous¡± 5.3 Subsampled Wavelet Frames 5.4 Windowed Fourier Frames 5.5 Multiscale Directional Frames for Images 5.5.1 Directional Wavelet Frames 5.5.2 Curvelet Frames 5.6 Exercises6. Wavelet Zoom6.1 Lipschitz Regularity 6.1.1 Lipschitz Definition and Fourier Analysis 6.1.2 Wavelet Vanishing Moments 6.1.3 Regularity Measurements with Wavelets 6.2 Wavelet Transform Modulus Maxima 6.2.1 Detection of Singularities 6.2.2 Dyadic Maxima Representation 6.3 Multiscale Edge Detection 6.3.1 Wavelet Maxima for Images 6.3.2 Fast Multiscale Edge Computations 6.4 Multifractals 6.4.1 Fractal Sets and Self-Similar Functions 6.4.2 Singularity Spectrum 6.4.3 Fractal Noises 6.5 Exercises 7. Wavelet Bases 7.1 Orthogonal Wavelet Bases7.1.1 Multiresolution Approximations 7.1.2 Scaling Function 7.1.3 Conjugate Mirror Filters 7.1.4 In Which Orthogonal Wavelets Finally Arrive 7.2 Classes of Wavelet Bases 7.2.1 Choosing a Wavelet 7.2.2 Shannon, Meyer and Battle-Lemari¢¥e Wavelets 7.2.3 Daubechies Compactly Supported Wavelets7.3 Wavelets and Filter Banks 7.3.1 Fast Orthogonal Wavelet Transform 7.3.2 Perfect Reconstruction Filter Banks 7.3.3 Biorthogonal Bases of §¤2(Z) 7.4 Biorthogonal Wavelet Bases 7.4.1 Construction of Biorthogonal Wavelet Bases 7.4.2 Biorthogonal Wavelet Design 7.4.3 Compactly Supported Biorthogonal Wavelets 7.5 Wavelet Bases on an Interval 7.5.1 Periodic Wavelets 7.5.2 Folded Wavelets 7.5.3 Boundary Wavelets 7.6 Multiscale Interpolations7.6.1 Interpolation and Sampling Theorems7.6.2 Interpolation Wavelet Basis 7.7 Separable Wavelet Bases 7.7.1 Separable Multiresolutions 7.7.2 Two-Dimensional Wavelet Bases7.7.3 Fast Two-Dimensional Wavelet Transform 7.7.4 Wavelet Bases in Higher Dimensions 7.8 Lifting Wavelets 7.8.1 Biorthogonal Bases over Non-stationary Grids 7.8.2 The Lifting Scheme 7.8.3 Quincunx Wavelet Bases 7.8.4 Wavelets on Bounded Domains and Surfaces 7.8.5 Faster Wavelet Transform with Lifting 7.9 Exercises 8. Wavelet Packet and Local Cosine Bases8.1 Wavelet Packets8.1.1 Wavelet Packet Tree 8.1.2 Time-Frequency Localization8.1.3 Particular Wavelet Packet Bases 8.1.4 Wavelet Packet Filter Banks 8.2 Image Wavelet Packets8.2.1 Wavelet Packet Quad-Tree 8.2.2 Separable Filter Banks 8.3 Block Transforms 8.3.1 Block Bases 8.3.2 Cosine Bases 8.3.3 Discrete Cosine Bases 8.3.4 Fast Discrete Cosine Transforms 8.4 Lapped Orthogonal Transforms 8.4.1 Lapped Projectors 8.4.2 Lapped Orthogonal Bases 8.4.3 Local Cosine Bases8.4.4 Discrete Lapped Transforms 8.5 Local Cosine Trees 8.5.1 Binary Tree of Cosine Bases8.5.2 Tree of Discrete Bases 8.5.3 Image Cosine Quad-Tree 8.6 Exercises9. Approximations in Bases 9.1 Linear Approximations 9.1.1 Sampling and Approximation Error 9.1.2 Linear Fourier Approximations . 9.1.3 Multiresolution Approximation Errors with Wavelets9.1.4 Karhunen-Lo`eve Approximations 9.2 Non-Linear Approximations 9.2.1 Non-Linear Approximation Error 9.2.2 Wavelet Adaptive Grids 9.2.3 Approximations in Besov and Bounded Variation Spaces 9.3 Sparse Image Representations 9.3.1 Wavelet Image Approximations 9.3.2 Geometric Image Models and Adaptive Triangulations 9.3.3 Curvelet Approximations 9.4 Exercises 10. Compression10.1 Transform Coding 10.1.1 Compression State of the Art 10.1.2 Compression in Orthonormal Bases 10.2 Distortion Rate of Quantization 10.2.1 Entropy Coding 10.2.2 Scalar Quantization 10.3 High Bit Rate Compression 10.3.1 Bit Allocation 10.3.2 Optimal Basis and Karhunen-Lo`eve 10.3.3 Transparent Audio Code 10.4 Sparse Signal Compression 10.4.1 Distortion Rate and Wavelet Image Coding 10.4.2 Embedded Transform Coding 10.5 Image Compression Standards 10.5.1 JPEG Block Cosine Coding 10.5.2 JPEG-2000 Wavelet Coding 10.6 Exercises11. Denoising11.1 Estimation with Additive Noise 11.1.1 Bayes Estimation 11.1.2 Minimax Estimation 11.2 Diagonal Estimation in a Basis 11.2.1 Diagonal Estimation with Oracles11.2.2 Thresholding Estimation11.2.3 Thresholding Refinements 11.2.4 Wavelet Thresholding 11.2.5 Wavelet and Curvelet Image Denoising 11.2.6 Audio Denoising by Time-Frequency Thresholding 11.3 Non-Diagonal Block Thresholding 11.3.1 Block Thresholding in Bases and Frames 11.3.2 Wavelet Block Thresholding 11.3.3 Time-Frequency Audio Block Thresholding 11.4 Denoising Minimax Optimality 11.4.1 Linear Diagonal Minimax Estimation 11.4.2 Orthosymmetric Sets 11.4.3 Nearly Minimax with Wavelet Thresholding 11.5 Exercises12. Sparse in Redundant Dictionaries12.1 Ideal Sparse Processing in Dictionaries 12.1.1 Best Approximation 12.1.2 Compression by Support Coding in a Dictionary 12.1.3 Denoising in a Dictionary 12.2 Dictionaries of Orthonormal Bases 12.2.1 Approximation, Compression and Denoising in a Best Basis 12.2.2 Fast Best Basis Search in Tree Dictionaries 12.2.3 Wavelet Packet and Local Cosine Best Bases 12.2.4 Bandlet Dictionaries for Geometric Processing 12.3 Greedy Pursuits 12.3.1 Matching Pursuit 12.3.2 Orthogonal Matching Pursuit . 12.3.3 Gabor Dictionaries 12.3.4 Learning Dictionaries 12.3.5 Coherent Matching Pursuit Denoising12.4 l1 Pursuits 12.4.1 Basis Pursuit 12.4.2 l1 Lagrangian Pursuit 12.5 Approximation Performance of Pursuits 12.5.1 Support Identification and Stability 12.5.2 Support Dependent Success of Pursuits 12.5.3 Sparsity Dependent Criterions and Mutual-Coherence 12.6 Inverse Problems 12.6.1 Linear Estimation and Singular Value Decompositions 12.6.2 Thresholding Inverse Problem Estimators 12.6.3 Super-Resolution 12.6.4 Compressive Sensing 12.6.5 Source Separation 12.7 ExercisesA. Mathematical ComplementsA.1 Functions and IntegrationA.2 Banach and Hilbert SpacesA.3 Bases of Hilbert Spaces A.4 Linear Operators A.5 Separable Spaces and BasesA.6 Random Vectors and Covariance Operators A.7 Diracs