Sparse and Redundant Representations

by Elad, Michael; Bruckstein, Alfred M.

• ISBN13: 9781441970107
• ISBN10: 144197010X
• Format: Hardcover
• Copyright: 2010-10-02
• Publisher: Springer Nature

Summary

This textbook introduces sparse and redundant representations with a focus on applications in signal and image processing. The theoretical and numerical foundations are tackled before the applications are discussed. Mathematical modeling for signal sources is discussed along with how to use the proper model for tasks such as denoising, restoration, separation, interpolation and extrapolation, compression, sampling, analysis and synthesis, detection, recognition, and more. The presentation is elegant and engaging.Sparse and Redundant Representations is intended for graduate students in applied mathematics and electrical engineering, as well as applied mathematicians, engineers, and researchers who are active in the fields of signal and image processing.

Table of Contents

Sparse and Redundant Representations - Theoretical and Numerical Foundations
Prologue	p. 3
Underdetermined Linear Systems	p. 3
Regularization	p. 4
The Temptation of Convexity	p. 5
A Closer Look at l1 Minimization	p. 6
Conversion of (P1) to Linear Programming	p. 8
Promoting Sparse Solutions	p. 8
The l0-Norm and Implications	p. 12
The (P0) Problem - Our Main Interest	p. 13
The Signal Processing Perspective	p. 14
Further Reading	p. 14
Uniqueness and Uncertainty	p. 17
Treating the Two-Ortho Case	p. 17
An Uncertainty Principle	p. 18
Uncertainty of Redundant Solutions	p. 21
From Uncertainty to Uniqueness	p. 23
Uniqueness Analysis for the General Case	p. 23
Uniqueness via the Spark	p. 23
Uniqueness via the Mutual-Coherence	p. 25
Uniqueness via the Babel Function	p. 27
Upper-Bounding the Spark	p. 28
Constructing Grassmannian Matrices	p. 29
Summary	p. 30
Further Reading	p. 31
Pursuit Algorithms - Practice	p. 35
Greedy Algorithms	p. 35
The Core Idea	p. 35
The Orthogonal-Matching-Pursuit	p. 36
Other Greedy Methods	p. 39
Normalization	p. 41
Rate of Decay of the Residual in Greedy Methods	p. 43
Thresholding Algorithm	p. 45
Numerical Demonstration of Greedy Algorithms	p. 46
Convex Relaxation Techniques	p. 48
Relaxation of the l0-Norm	p. 48
Numerical Algorithms for Solving (P1)	p. 51
Numerical Demonstration of Relaxation Methods	p. 51
Summary	p. 52
Further Reading	p. 53
Pursuit Algorithms - Guarantees	p. 55
Back to the Two-Ortho Case	p. 55
OMP Performance Guarantee	p. 55
BP Performance Guarantee	p. 58
The General Case	p. 64
OMP Performance Guarantee	p. 65
Thresholding Performance Guarantee	p. 67
BP Performance Guarantee	p. 68
Performance of Pursuit Algorithms - Summary	p. 71
The Role of the Sign-Pattern	p. 71
Tropp's Exact Recovery Condition	p. 73
Summary	p. 76
Further Reading	p. 76
From Exact to Approximate Solutions	p. 79
General Motivation	p. 79
Stability of the Sparsest Solution	p. 80
Uniqueness versus Stability - Gaining Intuition	p. 80
Theoretical Study of the Stability of (P0¿)	p. 82
The RIP and Its Use for Stability Analysis	p. 86
Pursuit Algorithms	p. 89
OMP and BP Extensions	p. 89
Iteratively-Reweighed-Least-Squares (IRLS)	p. 91
The LARS Algorithm	p. 95
Quality of Approximations Obtained	p. 98
The Unitary Case	p. 101
Performance of Pursuit Algorithms	p. 103
BPDN Stability Guarantee	p. 103
Thresholding Stability Guarantee	p. 104
Summary	p. 107
Further Reading	p. 108
Iterative-Shrinkage Algorithms	p. 111
Background	p. 111
The Unitary Case - A Source of Inspiration	p. 112
Shrinkage For the Unitary case	p. 112
The BCR Algorithm and Variations	p. 113
Developing Iterative-Shrinkage Algorithms	p. 115
Surrogate Functions and the Prox Method	p. 115
EM and Bound-Optimization Approaches	p. 117
An IRLS-Based Shrinkage Algorithm	p. 119
The Parallel-Coordinate-Descent (PCD) Algorithm	p. 120
StOMP: A Variation on Greedy Methods	p. 123
Bottom Line - Iterative-Shrinkage Algorithms	p. 125
Acceleration Using Line-Search and SESOP	p. 127
Iterative-Shrinkage Algorithms: Tests	p. 127
Summary	p. 132
Further Reading	p. 134
Towards Average Performance Analysis	p. 137
Empirical Evidence Revisited	p. 137
A Glimpse into Probabilistic Analysis	p. 140
The Analysis Goals	p. 140
Two-Ortho Analysis by Candes & Romberg	p. 141
Probabilistic Uniqueness	p. 143
Donoho's Analysis	p. 143
Summary	p. 144
Average Performance of Thresholding	p. 144
Preliminaries	p. 144
The Analysis	p. 145
Discussion	p. 148
Summary	p. 150
Further Reading	p. 150
The Dantzig-Selector Algorithm	p. 153
Dantzig-Selector versus Basis-Pursuit	p. 153
The Unitary Case	p. 155
Revisiting the Restricted Isometry Machinery	p. 156
Dantzig-Selector Performance Guaranty	p. 157
Dantzig-Selector in Practice	p. 163
Summary	p. 164
Further Reading	p. 165
From Theory to Practice - Signal and Image Processing Applications
Sparsity-Seeking Methods in Signal Processing	p. 169
Priors and Transforms for Signals	p. 169
The Sparse-Land Model	p. 172
Geometric Interpretation of Sparse-Land	p. 173
Processing of Sparsely-Generated Signals	p. 176
Analysis Versus Synthesis Signal Modeling	p. 178
Summary	p. 180
Further Reading	p. 181
Image Deblurring - A Case Study	p. 185
Problem Formulation	p. 185
The Dictionary	p. 186
Numerical Considerations	p. 188
Experiment Details and Results	p. 191
Summary	p. 198
Further Reading	p. 199
MAP versus MMSE Estimation	p. 201
A Stochastic Model and Estimation Goals	p. 201
Background on MAP and MMSE	p. 202
The Oracle Estimation	p. 204
Developing the Oracle Estimator	p. 204
The Oracle Error	p. 206
The MAP Estimation	p. 208
Developing the MAP Estimator	p. 208
Approximating the MAP Estimator	p. 211
The MMSE Estimation	p. 212
Developing the MMSE Estimator	p. 212
Approximating the MMSE Estimator	p. 215
MMSE and MAP Errors	p. 218
More Experimental Results	p. 220
Summary	p. 224
Further Reading	p. 224
The Quest for a Dictionary	p. 227
Choosing versus Learning	p. 227
Dictionary-Learning Algorithms	p. 228
Core Questions in Dictionary-Learning	p. 229
The MOD Algorithm	p. 230
The K-SVD Algorithm	p. 231
Training Structured Dictionaries	p. 237
The Double-Sparsity Model	p. 239
Union of Unitary Bases	p. 241
The Signature Dictionary	p. 242
Summary	p. 244
Further Reading	p. 244
Image Compression - Facial Images	p. 247
Compression of Facial Images	p. 247
Previous Work	p. 249
Sparse-Representation-Based Coding Scheme	p. 250
The General Scheme	p. 251
VQ Versus Sparse Representations	p. 253
More Details and Results	p. 254
K-SVD Dictionaries	p. 255
Reconstructed Images	p. 255
Run-Time and Memory Usage	p. 260
Comparing to Other Techniques	p. 261
Dictionary Redundancy	p. 262
Post-Processing for Deblocking	p. 263
The Blockiness Artifacts	p. 263
Possible Approaches For Deblocking	p. 265
Learning-Based Deblocking Approach	p. 266
Deblocking Results	p. 267
Summary	p. 268
Further Reading	p. 269
Image Denoising	p. 273
General Introduction - Image Denoising	p. 273
The Beginning: Global Modeling	p. 274
The Core Image-Denoising Algorithm	p. 274
Various Improvements	p. 276
From Global to Local Modeling	p. 278
The General Methodology	p. 278
Learning the Shrinkage Curves	p. 279
Learned Dictionary and Globalizing the Prior	p. 286
The Non-Local-Means Algorithm	p. 292
3D-DCT Shrinkage: BM3D Denoising	p. 296
SURE for Automatic Parameter Setting	p. 297
Development of the SURE	p. 298
Demonstrating SURE to Global-Threhsolding	p. 300
Summary	p. 303
Further Reading	p. 303
Other Applications	p. 309
General	p. 309
Image Separation via MCA	p. 310
Image = Cartoon + Texture	p. 310
Global MCA for Image Separation	p. 312
Local MCA for Image Separation	p. 316
Image Inpainting and Impulsive Noise Removal	p. 324
Inpainting Sparse-Land Signals - Core Principles	p. 324
Inpainting Images - Local K-SVD	p. 327
Inpainting Images - The Global MCA	p. 335
Impulse-Noise Filtering	p. 338
Image Scale-Up	p. 341
Modeling the Problem	p. 343
The Super-Resolution Algorithm	p. 346
Scaling-Up Results	p. 349
Image Scale-Up: Summary	p. 351
Summary	p. 353
Further Reading	p. 354
Epilogue	p. 359
What is it All About?	p. 359
What is Still Missing?	p. 359
Bottom Line	p. 360
Notation	p. 363
Acronyms	p. 369
Index	p. 371
Table of Contents provided by Ingram. All Rights Reserved.