CHAPTER 1 Sparse Representations 1
1.1 Computational Harmonic Analysis 1
1.1.1 The Fourier Kingdom 2
1.1.2 Wavelet Bases 2
1.2 Approximation and Processing in Bases 5
1.2.1 Sampling with Linear Approximations 7
1.2.2 Sparse Nonlinear Approximations 8
1.2.3 Compression 11
1.2.4 Denoising 11
1.3 Time-Frequency Dictionaries 14
1.3.1 Heisenberg Uncertainty 15
1.3.2 Windowed Fourier Transform 16
1.3.3 Continuous Wavelet Transform 17
1.3.4 Time-Frequency Orthonormal Bases 19
1.4 Sparsity in Redundant Dictionaries 21
1.4.1 Frame Analysis and Synthesis 21
1.4.2 Ideal Dictionary Approximations 23
1.4.3 Pursuit in Dictionaries 24
1.5 Inverse Problems 26
1.5.1 Diagonal Inverse Estimation 27
1.5.2 Super-resolution and Compressive Sensing 28
1.6 Travel Guide 30
1.6.1 Reproducible Computational Science 30
1.6.2 Book Road Map 30
CHAPTER 2 The Fourier Kingdom 33
2.1 Linear Time-Invariant Filtering 33
2.1.1 Impulse Response 33
2.1.2 Transfer Functions 35
2.2 Fourier Integrals 35
2.2.1 Fourier Transform in L1(R) 35
2.2.2 Fourier Transform in L2(R) 38
2.2.3 Examples 40
2.3 Properties 42
2.3.1 Regularity and Decay 42
2.3.2 Uncertainty Principle 43
2.3.3 Total Variation 46
2.4 Two-Dimensional Fourier Transform 51
2.5 Exercises 55
CHAPTER 3 Discrete Revolution 59
3.1 Sampling Analog Signals 59
3.1.1 Shannon-Whittaker SamplingTheorem 59
3.1.2 Aliasing 61
3.1.3 General Sampling and Linear Analog Conversions 65
3.2 Discrete Time-Invariant Filters 70
3.2.1 Impulse Response and Transfer Function 70
3.2.2 Fourier Series 72
3.3 Finite Signals 75
3.3.1 Circular Convolutions 76
3.3.2 Discrete Fourier Transform 76
3.3.3 Fast Fourier Transform 78
3.3.4 Fast Convolutions 79
3.4 Discrete Image Processing 80
3.4.1 Two-Dimensional Sampling Theorems 80
3.4.2 Discrete Image Filtering 82
3.4.3 Circular Convolutions and Fourier Basis 83
3.5 Exercises 85
CHAPTER 4 Time Meets Frequency 89
4.1 Time-Frequency Atoms 89
4.2 Windowed Fourier Transform 92
4.2.1 Completeness and Stability 94
4.2.2 Choice of Window 98
4.2.3 Discrete Windowed Fourier Transform 101
4.3 Wavelet Transforms 102
4.3.1 Real Wavelets 103
4.3.2 Analytic Wavelets 107
4.3.3 Discrete Wavelets 112
4.4 Time-Frequency Geometry of Instantaneous Frequencies 115
4.4.1 Analytic Instantaneous Frequency 115
4.4.2 Windowed Fourier Ridges 118
4.4.3 Wavelet Ridges 129
4.5 Quadratic Time-Frequency Energy 134
4.5.1 Wigner-Ville Distribution 136
4.5.2 Interferences and Positivity 140
4.5.3 Cohen's Class 145
4.5.4 Discrete Wigner-Ville Computations 149
4.6 Exercises 151
CHAPTER 5 Frames 155
5.1 Frames and Riesz Bases 155
5.1.1 Stable Analysis and Synthesis Operators 155
5.1.2 Dual Frame and Pseudo Inverse 159
5.1.3 Dual-Frame Analysis and Synthesis Computations 161
5.1.4 Frame Projector and Reproducing Kernel 166
5.1.5 Translation-Invariant Frames 168
5.2 Translation-Invariant Dyadic Wavelet Transform 170
5.2.1 Dyadic Wavelet Design 172
5.2.2 Algorithme à Trous 175
5.3 Subsampled Wavelet Frames 178
5.4 Windowed Fourier Frames 181
5.4.1 Tight Frames 183
5.4.2 General Frames 184
5.5 Multiscale Directional Frames for Images 188
5.5.1 Directional Wavelet Frames 189
5.5.2 Curvelet Frames 194
5.6 Exercises 201
CHAPTER 6 Wavelet Zoom 205
6.1 Lipschitz Regularity 205
6.1.1 Lipschitz Definition and Fourier Analysis 205
6.1.2 Wavelet Vanishing Moments 208
6.1.3 Regularity Measurements with Wavelets 211
6.2 Wavelet Transform Modulus Maxima 218
6.2.1 Detection of Singularities 218
6.2.2 Dyadic Maxima Representation 224
6.3 Multiscale Edge Detection 230
6.3.1 Wavelet Maxima for Images 230
6.3.2 Fast Multiscale Edge Computations 239
6.4 Multifractals 242
6.4.1 Fractal Sets and Self-Similar Functions 242
6.4.2 Singularity Spectrum 246
6.4.3 Fractal Noises 254
6.5 Exercises 259
CHAPTER 7 Wavelet Bases 263
7.1 Orthogonal Wavelet Bases 263
7.1.1 Multiresolution Approximations 264
7.1.2 Scaling Function 267
7.1.3 Conjugate Mirror Filters 270
7.1.4 In Which Orthogonal Wavelets Finally Arrive 278
7.2 Classes of Wavelet Bases 284
7.2.1 Choosing a Wavelet 284
7.2.2 Shannon,Meyer,Haar,and Battle-Lemarié Wavelets 289
7.2.3 Daubechies Compactly Supported Wavelets 292
7.3 Wavelets and Filter Banks 298
7.3.1 Fast Orthogonal Wavelet Transform 298
7.3.2 Perfect Reconstruction Filter Banks 302
7.3.3 Biorthogonal Bases of l2(Z) 306
7.4 Biorthogonal Wavelet Bases 308
7.4.1 Construction of Biorthogonal Wavelet Bases 308
7.4.2 Biorthogonal Wavelet Design 311
7.4.3 Compactly Supported Biorthogonal Wavelets 313
7.5 Wavelet Bases on an Interval 317
7.5.1 Periodic Wavelets 318
7.5.2 Folded Wavelets 320
7.5.3 Boundary Wavelets 322
7.6 Multiscale Interpolations 328
7.6.1 Interpolation and Sampling Theorems 328
7.6.2 Interpolation Wavelet Basis 333
7.7 Separable Wavelet Bases 338
7.7.1 Separable Multiresolutions 338
7.7.2 Two-Dimensional Wavelet Bases 340
7.7.3 Fast Two-Dimensional Wavelet Transform 346
7.7.4 Wavelet Bases in Higher Dimensions 348
7.8 Lifting Wavelets 350
7.8.1 Biorthogonal Bases over Nonstationary Grids 350
7.8.2 Lifting Scheme 352
7.8.3 Quincunx WaveletBases 359
7.8.4 Wavelets on Bounded Domains and Surfaces 361
7.8.5 Faster Wavelet Transform with Lifting 367
7.9 Exercises 370
CHAPTER 8 Wavelet Packet and Local Cosine Bases 377
8.1 Wavelet Packets 377
8.1.1 Wavelet Packet Tree 377
8.1.2 Time-Frequency Localization 383
8.1.3 Particular Wavelet Packet Bases 388
8.1.4 Wavelet Packet Filter Banks 393
8.2 Image Wavelet Packets 395
8.2.1 Wavelet Packet Quad-Tree 395
8.2.2 Separable Filter Banks 399
8 3 Block Transforms 400
8.3.1 Block Bases 401
8.3.2 Cosine Bases 403
8.3.3 Discrete Cosine Bases 406
8.3.4 Fast Discrete Cosine Transforms 407
8.4 Lapped Orthogonal Transforms 410
8.4.1 LappedProjectors 410
8.4.2 Lapped Orthogonal Bases 416
8.4.3 Local Cosine Bases 419
8.4.4 Discrete Lapped Transforms 422
8.5 Local Cosine Trees 426
8.5.1 Binary Tree of Cosine Bases 426
8.5.2 Tree of Discrete Bases 429
8.5.3 Image Cosine Quad-Tree 429
8.6 Exercises 432
CHAPTER 9 Approximations in Bases 435
9.1 Linear Approximations 435
9.1.1 Sampling and Approximation Error 435
9.1.2 Linear Fourier Approximations 438
9.1.3 Multiresolution Approximation Errors with Wavelets 442
9.1.4 Karhunen-Loève Approximations 446
9.2 Nonlinear Approximations 450
9.2.1 Nonlinear Approximation Error 451
9.2.2 Wavelet Adaptive Grids 455
9.2.3 Approximations in Besov and Bounded Variation Spaces 459
9.3 Sparse Image Representations 463
9.3.1 Wavelet Image Approximations 464
9.3.2 Geometric Image Models and Adaptive Triangulations 471
9.3.3 Curvelet Approximations 476
9.4 Exercises 478
CHAPTER 10 Compression 481
10.1 Transform Coding 481
10.1.1 Compression State of the Art 482
10.1.2 Compression in Orthonormal Bases 483
10.2 Distortion Rate of Quantization 485
10.2.1 Entropy Coding 485
10.2.2 Scalar Quantization 493
10.3 High Bit Rate Compression 496
10.3.1 Bit Allocation 496
10.3.2 Optimal Basis and Karhunen-Loève 498
10.3.3 Transparent Audio Code 501
10.4 Sparse Signal Compression 506
10.4.1 Distortion Rate and Wavelet Image Coding 506
10.4.2 Embedded Transform Coding 516
10.5 Image-Compression Standards 519
10.5.1 JPEG Block Cosine Coding 519
10.5.2 JPEG-2000 Wavelet Coding 523
10.6 Exercises 531
CHAPTER 11 Denoising 535
11.1 Estimation with Additive Noise 535
11.1.1 Bayes Estimation 536
11.1.2 Minimax Estimation 544
11.2 Diagonal Estimationin a Basis 548
11.2.1 Diagonal Estimation with Ofacles 548
11.2.2 Thresholding Estimation 552
11.2.3 Thresholding Improvements 558
11.3 Thresholding Sparse Representations 562
11.3.1 Wavelet Thresholding 563
11.3.2 Wavelet and Curvelet Image Denoising 568
11.3.3 Audio Denoising by Time-Frequency Thresholding 571
11.4 Nondiagonal Block Thresholding 575
11.4.1 Block Thresholding in Bases and Frames 575
11.4.2 Wavelet Block Thresholding 581
11.4.3 Time-Frequency Audio Block Thresholding 582
11.5 Denoising Minimax Optimality 585
11.5.1 Linear Diagonal Minimax Estimation 587
11.5.2 Thresholding Optimality over Orthosymmetric Sets 590
11.5.3 Nearly Minimax with Wavelet Estimation 595
11.6 Exercises 606
CHAPTER 12 Sparsity in Redundant Dictionaries 611
12.1 Ideal Sparse Processing in Dictionaries 611
12.1.1 Best M-Term Approximations 612
12.1.2 Compression by Support Coding 614
12.1.3 Denoising by Support Selection in a Dictionary 616
12.2 Dictionaries of Orthonormal Bases 621
12.2.1 Approximation,Compression,and Denoising in a Best Basis 622
12.2.2 Fast Best-Basis Search in Tree Dictionaries 623
12.2.3 Wavelet Packet and Local Cosine Best Bases 626
12.2.4 Bandlets for Geometric Image Regularity 631
12.3 Greedy Matching Pursuits 642
12.3.1 Matching Pursuit 642
12.3.2 Orthogonal Matching Pursuit 648
12.3.3 Gabor Dictionaries 650
12.3.4 Coherent Matching Pursuit Denoising 655
12.4 11 Pursuits 659
12.4.1 Basis Pursuit 659
12.4.2 11 Lagrangian Pursuit 664
12.4.3 Computations of 11 Minimizations 668
12.4.4 Sparse Synthesis versus Analysis and Total Variation Regularization 673
12.5 Pursuit Recovery 677
12.5.1 Stability and Incoherence 677
12.5.2 Support Recovery with Matching Pursuit 679
12.5.3 Support Recovery with 11 Pursuits 684
12.6 Multichannel Signals 688
12.6.1 Approximation and Denoising by Thresholding in Bases 689
12.6.2 Multichannel Pursuits 690
12.7 Learning Dictionaries 693
12.8 Exercises 696
CHAPTER 13 Inverse Problems 699
13.1 Linear Inverse Estimation 700
13.1.1 Quadratic and Tikhonov Regularizations 700
13.1.2 Singular Value Decompositions 702
13.2 Thresholding Estimators for Inverse Problems 703
13.2.1 Thresholding in Bases of Almost Singular Vectors 703
13.2.2 Thresholding Deconvolutions 709
13.3 Super-resolution 713
13.3.1 Sparse Super-resolution Estimation 713
13.3.2 Sparse Spike Deconvolution 719
13.3.3 Recovery of Missing Data 722
13.4 Compressive Sensing 728
13.4.1 Incoherence with Random Measurements 729
13.4.2 Approximations with Compressive Sensing 735
13.4.3 Compressive Sensing Applications 742
13.5 Blind Source Separation 744
13.5.1 Blind Mixing Matrix Estimation 745
13.5.2 Source Separation 751
13.6 Exercises 752
APPENDIX Mathematical Complements 753
Bibliography 765
Index 795