Wavelet Tour of Signal Processing (eBook)

Front Cover 1
A Wavelet Tour of Signal Processing 4
Copyright Page 5
Dedication Page 6
Table of Contents 8
Preface to the Sparse Edition 16
Notations 20
Chapter 1. Sparse Representations 24
1.1 Computational Harmonic Analysis 24
1.1.1 The Fourier Kingdom 25
1.1.2 Wavelet Bases 25
1.2 Approximation and Processing in Bases 28
1.2.1 Sampling with Linear Approximations 30
1.2.2 Sparse Nonlinear Approximations 31
1.2.3 Compression 34
1.2.4 Denoising 34
1.3 Time-Frequency Dictionaries 37
1.3.1 Heisenberg Uncertainty 38
1.3.2 Windowed Fourier Transform 39
1.3.3 Continuous Wavelet Transform 40
1.3.4 Time-Frequency Orthonormal Bases 42
1.4 Sparsity in Redundant Dictionaries 44
1.4.1 Frame Analysis and Synthesis 44
1.4.2 Ideal Dictionary Approximations 46
1.4.3 Pursuit in Dictionaries 47
1.5 Inverse Problems 49
1.5.1 Diagonal Inverse Estimation 50
1.5.2 Super-resolution and Compressive Sensing 51
1.6 Travel Guide 53
1.6.1 Reproducible Computational Science 53
1.6.2 Book Road Map 53
Chapter 2. The Fourier Kingdom 56
2.1 Linear Time-Invariant Filtering 56
2.1.1 Impulse Response 56
2.1.2 Transfer Functions 58
2.2 Fourier Integrals 58
2.2.1 Fourier Transform in L1(R) 58
2.2.2 Fourier Transform in L2(R) 61
2.2.3 Examples 63
2.3 Properties 65
2.3.1 Regularity and Decay 65
2.3.2 Uncertainty Principle 66
2.3.3 Total Variation 69
2.4 Two-Dimensional Fourier Transform 74
2.5 Exercises 78
Chapter 3. Discrete Revolution 82
3.1 Sampling Analog Signals 82
3.1.1 Shannon-Whittaker Sampling Theorem 82
3.1.2 Aliasing 84
3.1.3 General Sampling and Linear Analog Conversions 88
3.2 Discrete Time-Invariant Filters 93
3.2.1 Impulse Response and Transfer Function 93
3.2.2 Fourier Series 95
3.3 Finite Signals 98
3.3.1 Circular Convolutions 99
3.3.2 Discrete Fourier Transform 99
3.3.3 Fast Fourier Transform 101
3.3.4 Fast Convolutions 102
3.4 Discrete Image Processing 103
3.4.1 Two-Dimensional Sampling Theorems 103
3.4.2 Discrete Image Filtering 105
3.4.3 Circular Convolutions and Fourier Basis 106
3.5 Exercises 108
Chapter 4. Time Meets Frequency 112
4.1 Time-Frequency Atoms 112
4.2 Windowed Fourier Transform 115
4.2.1 Completeness and Stability 117
4.2.2 Choice of Window 121
4.2.3 Discrete Windowed Fourier Transform 124
4.3 Wavelet Transforms 125
4.3.1 Real Wavelets 126
4.3.2 Analytic Wavelets 130
4.3.3 Discrete Wavelets 135
4.4 Time-Frequency Geometry of Instantaneous Frequencies 138
4.4.1 Analytic Instantaneous Frequency 138
4.4.2 Windowed Fourier Ridges 141
4.4.3 Wavelet Ridges 152
4.5 Quadratic Time-Frequency Energy 157
4.5.1 Wigner-Ville Distribution 159
4.5.2 Interferences and Positivity 163
4.5.3 Cohen’s Class 168
4.5.4 Discrete Wigner-Ville Computations 172
4.6 Exercises 174
Chapter 5. Frames 178
5.1 Frames and Riesz Bases 178
5.1.1 Stable Analysis and Synthesis Operators 178
5.1.2 Dual Frame and Pseudo Inverse 182
5.1.3 Dual-Frame Analysis and Synthesis Computations 184
5.1.4 Frame Projector and Reproducing Kernel 189
5.1.5 Translation-Invariant Frames 191
5.2 Translation-Invariant Dyadic Wavelet Transform 193
5.2.1 Dyadic Wavelet Design 195
5.2.2 Algorithme à Trous 198
5.3 Subsampled Wavelet Frames 201
5.4 Windowed Fourier Frames 204
5.4.1 Tight Frames 206
5.4.2 General Frames 207
5.5 Multiscale Directional Frames For Images 211
5.5.1 Directional Wavelet Frames 212
5.5.2 Curvelet Frames 217
5.6 Exercises 224
Chapter 6. Wavelet Zoom 228
6.1 Lipschitz Regularity 228
6.1.1 Lipschitz Definition and Fourier Analysis 228
6.1.2 Wavelet Vanishing Moments 231
6.1.3 Regularity Measurements with Wavelets 234
6.2 Wavelet Transform Modulus Maxima 241
6.2.1 Detection of Singularities 241
6.2.2 Dyadic Maxima Representation 247
6.3 Multiscale Edge Detection 253
6.3.1 Wavelet Maxima for Images 253
6.3.2 Fast Multiscale Edge Computations 262
6.4 Multifractals 265
6.4.1 Fractal Sets and Self-Similar Functions 265
6.4.2 Singularity Spectrum 269
6.4.3 Fractal Noises 277
6.5 Exercises 282
Chapter 7. Wavelet Bases 286
7.1 Orthogonal Wavelet Bases 286
7.1.1 Multiresolution Approximations 287
7.1.2 Scaling Function 290
7.1.3 Conjugate Mirror Filters 293
7.1.4 In Which Orthogonal Wavelets Finally Arrive 301
7.2 Classes of Wavelet Bases 307
7.2.1 Choosing a Wavelet 307
7.2.2 Shannon, Meyer, Haar, and Battle-Lemarié Wavelets 312
7.2.3 Daubechies Compactly Supported Wavelets 315
7.3 Wavelets and Filter Banks 321
7.3.1 Fast Orthogonal Wavelet Transform 321
7.3.2 Perfect Reconstruction Filter Banks 325
7.3.3 Biorthogonal Bases of l2(Z) 329
7.4 Biorthogonal Wavelet Bases 331
7.4.1 Construction of Biorthogonal Wavelet Bases 331
7.4.2 Biorthogonal Wavelet Design 334
7.4.3 Compactly Supported Biorthogonal Wavelets 336
7.5 Wavelet Bases on an Interval 340
7.5.1 Periodic Wavelets 341
7.5.2 Folded Wavelets 343
7.5.3 Boundary Wavelets 345
7.6 Multiscale Interpolations 351
7.6.1 Interpolation and Sampling Theorems 351
7.6.2 Interpolation Wavelet Basis 356
7.7 Separable Wavelet Bases 361
7.7.1 Separable Multiresolutions 361
7.7.2 Two-Dimensional Wavelet Bases 363
7.7.3 Fast Two-Dimensional Wavelet Transform 369
7.7.4 Wavelet Bases in Higher Dimensions 371
7.8 Lifting Wavelets 373
7.8.1 Biorthogonal Bases over Nonstationary Grids 373
7.8.2 Lifting Scheme 375
7.8.3 Quincunx Wavelet Bases 382
7.8.4 Wavelets on Bounded Domains and Surfaces 384
7.8.5 Faster Wavelet Transform with Lifting 390
7.9 Exercises 393
Chapter 8. Wavelet Packet and Local Cosine Bases 400
8.1 Wavelet Packets 400
8.1.1 Wavelet Packet Tree 400
8.1.2 Time-Frequency Localization 406
8.1.3 Particular Wavelet Packet Bases 411
8.1.4 Wavelet Packet Filter Banks 416
8.2 Image Wavelet Packets 418
8.2.1 Wavelet Packet Quad-Tree 418
8.2.2 Separable Filter Banks 422
8.3 Block Transforms 423
8.3.1 Block Bases 424
8.3.2 Cosine Bases 426
8.3.3 Discrete Cosine Bases 429
8.3.4 Fast Discrete Cosine Transforms 430
8.4 Lapped Orthogonal Transforms 433
8.4.1 Lapped Projectors 433
8.4.2 Lapped Orthogonal Bases 439
8.4.3 Local Cosine Bases 442
8.4.4 Discrete Lapped Transforms 445
8.5 Local Cosine Trees 449
8.5.1 Binary Tree of Cosine Bases 449
8.5.2 Tree of Discrete Bases 452
8.5.3 Image Cosine Quad-Tree 452
8.6 Exercises 455
Chapter 9. Approximations in Bases 458
9.1 Linear Approximations 458
9.1.1 Sampling and Approximation Error 458
9.1.2 Linear Fourier Approximations 461
9.1.3 Multiresolution Approximation Errors with Wavelets 465
9.1.4 Karhunen-Loève Approximations 469
9.2 Nonlinear Approximations 473
9.2.1 Nonlinear Approximation Error 474
9.2.2 Wavelet Adaptive Grids 478
9.2.3 Approximations in Besov and Bounded Variation Spaces 482
9.3 Sparse Image Representations 486
9.3.1 Wavelet Image Approximations 487
9.3.2 Geometric Image Models and Adaptive Triangulations 494
9.3.3 Curvelet Approximations 499
9.4 Exercises 501
Chapter 10. Compression 504
10.1 Transform Coding 504
10.1.1 Compression State of the Art 505
10.1.2 Compression in Orthonormal Bases 506
10.2 Distortion Rate of Quantization 508
10.2.1 Entropy Coding 508
10.2.2 Scalar Quantization 516
10.3 High Bit Rate Compression 519
10.3.1 Bit Allocation 519
10.3.2 Optimal Basis and Karhunen-Loève 521
10.3.3 Transparent Audio Code 524
10.4 Sparse Signal Compression 529
10.4.1 Distortion Rate and Wavelet Image Coding 529
10.4.2 Embedded Transform Coding 539
10.5 Image-Compression Standards 542
10.5.1 JPEG Block Cosine Coding 542
10.5.2 JPEG-2000 Wavelet Coding 546
10.6 Exercises 554
Chapter 11. Denoising 558
11.1 Estimation with Additive Noise 558
11.1.1 Bayes Estimation 559
11.1.2 Minimax Estimation 567
11.2 Diagonal Estimation in a Basis 571
11.2.1 Diagonal Estimation with Oracles 571
11.2.2 Thresholding Estimation 575
11.2.3 Thresholding Improvements 581
11.3 Thresholding Sparse Representations 585
11.3.1 Wavelet Thresholding 586
11.3.2 Wavelet and Curvelet Image Denoising 591
11.3.3 Audio Denoising by Time-Frequency Thresholding 594
11.4 Nondiagonal Block Thresholding 598
11.4.1 Block Thresholding in Bases and Frames 598
11.4.2 Wavelet Block Thresholding 604
11.4.3 Time-Frequency Audio Block Thresholding 605
11.5 Denoising Minimax Optimality 608
11.5.1 Linear Diagonal Minimax Estimation 610
11.5.2 Thresholding Optimality over Orthosymmetric Sets 613
11.5.3 Nearly Minimax with Wavelet Estimation 618
11.6 Exercises 629
Chapter 12. Sparsity in Redundant Dictionaries 634
12.1 Ideal Sparse Processing in Dictionaries 634
12.1.1 Best M-Term Approximations 635
12.1.2 Compression by Support Coding 637
12.1.3 Denoising by Support Selection in a Dictionary 639
12.2 Dictionaries of Orthonormal Bases 644
12.2.1 Approximation, Compression, and Denoising in a Best Basis 645
12.2.2 Fast Best-Basis Search in Tree Dictionaries 646
12.2.3 Wavelet Packet and Local Cosine Best Bases 649
12.2.4 Bandlets for Geometric Image Regularity 654
12.3 Greedy Matching Pursuits 665
12.3.1 Matching Pursuit 665
12.3.2 Orthogonal Matching Pursuit 671
12.3.3 Gabor Dictionaries 673
12.3.4 Coherent Matching Pursuit Denoising 678
12.4 l1 Pursuits 682
12.4.1 Basis Pursuit 682
12.4.2 l1 Lagrangian Pursuit 687
12.4.3 Computations of l1 Minimizations 691
12.4.4 Sparse Synthesis versus Analysis and Total Variation Regularization 696
12.5 Pursuit Recovery 700
12.5.1 Stability and Incoherence 700
12.5.2 Support Recovery with Matching Pursuit 702
12.5.3 Support Recovery with l1 Pursuits 707
12.6 Multichannel Signals 711
12.6.1 Approximation and Denoising by Thresholding in Bases 712
12.6.2 Multichannel Pursuits 713
12.7 Learning Dictionaries 716
12.8 Exercises 719
Chapter 13. Inverse Problems 722
13.1 Linear Inverse Estimation 723
13.1.1 Quadratic and Tikhonov Regularizations 723
13.1.2 Singular Value Decompositions 725
13.2 Thresholding Estimators for Inverse Problems 726
13.2.1 Thresholding in Bases of Almost Singular Vectors 726
13.2.2 Thresholding Deconvolutions 732
13.3 Super-Resolution 736
13.3.1 Sparse Super-resolution Estimation 736
13.3.2 Sparse Spike Deconvolution 742
13.3.3 Recovery of Missing Data 745
13.4 Compressive Sensing 751
13.4.1 Incoherence with Random Measurements 752
13.4.2 Approximations with Compressive Sensing 758
13.4.3 Compressive Sensing Applications 765
13.5 Blind Source Separation 767
13.5.1 Blind Mixing Matrix Estimation 768
13.5.2 Source Separation 774
13.6 Exercises 775
Appendix Mathematical Complements 776
Bibliography 788
Index 818