| |
| |
| |
| Sparse and Redundant Representations - Theoretical and Numerical Foundations | |
| |
| |
| |
| Prologue | |
| |
| |
| |
| Underdetermined Linear Systems | |
| |
| |
| |
| Regularization | |
| |
| |
| |
| The Temptation of Convexity | |
| |
| |
| |
| A Closer Look at l<sub>1</sub> Minimization | |
| |
| |
| |
| Conversion of (P<sub>1</sub>) to Linear Programming | |
| |
| |
| |
| Promoting Sparse Solutions | |
| |
| |
| |
| The l<sub>0</sub>-Norm and Implications | |
| |
| |
| |
| The (P<sub>0</sub>) Problem - Our Main Interest | |
| |
| |
| |
| The Signal Processing Perspective | |
| |
| |
| Further Reading | |
| |
| |
| |
| Uniqueness and Uncertainty | |
| |
| |
| |
| Treating the Two-Ortho Case | |
| |
| |
| |
| An Uncertainty Principle | |
| |
| |
| |
| Uncertainty of Redundant Solutions | |
| |
| |
| |
| From Uncertainty to Uniqueness | |
| |
| |
| |
| Uniqueness Analysis for the General Case | |
| |
| |
| |
| Uniqueness via the Spark | |
| |
| |
| |
| Uniqueness via the Mutual-Coherence | |
| |
| |
| |
| Uniqueness via the Babel Function | |
| |
| |
| |
| Upper-Bounding the Spark | |
| |
| |
| |
| Constructing Grassmannian Matrices | |
| |
| |
| |
| Summary | |
| |
| |
| Further Reading | |
| |
| |
| |
| Pursuit Algorithms - Practice | |
| |
| |
| |
| Greedy Algorithms | |
| |
| |
| |
| The Core Idea | |
| |
| |
| |
| The Orthogonal-Matching-Pursuit | |
| |
| |
| |
| Other Greedy Methods | |
| |
| |
| |
| Normalization | |
| |
| |
| |
| Rate of Decay of the Residual in Greedy Methods | |
| |
| |
| |
| Thresholding Algorithm | |
| |
| |
| |
| Numerical Demonstration of Greedy Algorithms | |
| |
| |
| |
| Convex Relaxation Techniques | |
| |
| |
| |
| Relaxation of the l<sub>0</sub>-Norm | |
| |
| |
| |
| Numerical Algorithms for Solving (P<sub>1</sub>) | |
| |
| |
| |
| Numerical Demonstration of Relaxation Methods | |
| |
| |
| |
| Summary | |
| |
| |
| Further Reading | |
| |
| |
| |
| Pursuit Algorithms - Guarantees | |
| |
| |
| |
| Back to the Two-Ortho Case | |
| |
| |
| |
| OMP Performance Guarantee | |
| |
| |
| |
| BP Performance Guarantee | |
| |
| |
| |
| The General Case | |
| |
| |
| |
| OMP Performance Guarantee | |
| |
| |
| |
| Thresholding Performance Guarantee | |
| |
| |
| |
| BP Performance Guarantee | |
| |
| |
| |
| Performance of Pursuit Algorithms - Summary | |
| |
| |
| |
| The Role of the Sign-Pattern | |
| |
| |
| |
| Tropp's Exact Recovery Condition | |
| |
| |
| |
| Summary | |
| |
| |
| Further Reading | |
| |
| |
| |
| From Exact to Approximate Solutions | |
| |
| |
| |
| General Motivation | |
| |
| |
| |
| Stability of the Sparsest Solution | |
| |
| |
| |
| Uniqueness versus Stability - Gaining Intuition | |
| |
| |
| |
| Theoretical Study of the Stability of (P<sub>0</sub><sup>�</sup>) | |
| |
| |
| |
| The RIP and Its Use for Stability Analysis | |
| |
| |
| |
| Pursuit Algorithms | |
| |
| |
| |
| OMP and BP Extensions | |
| |
| |
| |
| Iteratively-Reweighed-Least-Squares (IRLS) | |
| |
| |
| |
| The LARS Algorithm | |
| |
| |
| |
| Quality of Approximations Obtained | |
| |
| |
| |
| The Unitary Case | |
| |
| |
| |
| Performance of Pursuit Algorithms | |
| |
| |
| |
| BPDN Stability Guarantee | |
| |
| |
| |
| Thresholding Stability Guarantee | |
| |
| |
| |
| Summary | |
| |
| |
| Further Reading | |
| |
| |
| |
| Iterative-Shrinkage Algorithms | |
| |
| |
| |
| Background | |
| |
| |
| |
| The Unitary Case - A Source of Inspiration | |
| |
| |
| |
| Shrinkage For the Unitary case | |
| |
| |
| |
| The BCR Algorithm and Variations | |
| |
| |
| |
| Developing Iterative-Shrinkage Algorithms | |
| |
| |
| |
| Surrogate Functions and the Prox Method | |
| |
| |
| |
| EM and Bound-Optimization Approaches | |
| |
| |
| |
| An IRLS-Based Shrinkage Algorithm | |
| |
| |
| |
| The Parallel-Coordinate-Descent (PCD) Algorithm | |
| |
| |
| |
| StOMP: A Variation on Greedy Methods | |
| |
| |
| |
| Bottom Line - Iterative-Shrinkage Algorithms | |
| |
| |
| |
| Acceleration Using Line-Search and SESOP | |
| |
| |
| |
| Iterative-Shrinkage Algorithms: Tests | |
| |
| |
| |
| Summary | |
| |
| |
| Further Reading | |
| |
| |
| |
| Towards Average Performance Analysis | |
| |
| |
| |
| Empirical Evidence Revisited | |
| |
| |
| |
| A Glimpse into Probabilistic Analysis | |
| |
| |
| |
| The Analysis Goals | |
| |
| |
| |
| Two-Ortho Analysis by Candes & Romberg | |
| |
| |
| |
| Probabilistic Uniqueness | |
| |
| |
| |
| Donoho's Analysis | |
| |
| |
| |
| Summary | |
| |
| |
| |
| Average Performance of Thresholding | |
| |
| |
| |
| Preliminaries | |
| |
| |
| |
| The Analysis | |
| |
| |
| |
| Discussion | |
| |
| |
| |
| Summary | |
| |
| |
| Further Reading | |
| |
| |
| |
| The Dantzig-Selector Algorithm | |
| |
| |
| |
| Dantzig-Selector versus Basis-Pursuit | |
| |
| |
| |
| The Unitary Case | |
| |
| |
| |
| Revisiting the Restricted Isometry Machinery | |
| |
| |
| |
| Dantzig-Selector Performance Guaranty | |
| |
| |
| |
| Dantzig-Selector in Practice | |
| |
| |
| |
| Summary | |
| |
| |
| Further Reading | |
| |
| |
| |
| From Theory to Practice - Signal and Image Processing Applications | |
| |
| |
| |
| Sparsity-Seeking Methods in Signal Processing | |
| |
| |
| |
| Priors and Transforms for Signals | |
| |
| |
| |
| The Sparse-Land Model | |
| |
| |
| |
| Geometric Interpretation of Sparse-Land | |
| |
| |
| |
| Processing of Sparsely-Generated Signals | |
| |
| |
| |
| Analysis Versus Synthesis Signal Modeling | |
| |
| |
| |
| Summary | |
| |
| |
| Further Reading | |
| |
| |
| |
| Image Deblurring - A Case Study | |
| |
| |
| |
| Problem Formulation | |
| |
| |
| |
| The Dictionary | |
| |
| |
| |
| Numerical Considerations | |
| |
| |
| |
| Experiment Details and Results | |
| |
| |
| |
| Summary | |
| |
| |
| Further Reading | |
| |
| |
| |
| MAP versus MMSE Estimation | |
| |
| |
| |
| A Stochastic Model and Estimation Goals | |
| |
| |
| |
| Background on MAP and MMSE | |
| |
| |
| |
| The Oracle Estimation | |
| |
| |
| |
| Developing the Oracle Estimator | |
| |
| |
| |
| The Oracle Error | |
| |
| |
| |
| The MAP Estimation | |
| |
| |
| |
| Developing the MAP Estimator | |
| |
| |
| |
| Approximating the MAP Estimator | |
| |
| |
| |
| The MMSE Estimation | |
| |
| |
| |
| Developing the MMSE Estimator | |
| |
| |
| |
| Approximating the MMSE Estimator | |
| |
| |
| |
| MMSE and MAP Errors | |
| |
| |
| |
| More Experimental Results | |
| |
| |
| |
| Summary | |
| |
| |
| Further Reading | |
| |
| |
| |
| The Quest for a Dictionary | |
| |
| |
| |
| Choosing versus Learning | |
| |
| |
| |
| Dictionary-Learning Algorithms | |
| |
| |
| |
| Core Questions in Dictionary-Learning | |
| |
| |
| |
| The MOD Algorithm | |
| |
| |
| |
| The K-SVD Algorithm | |
| |
| |
| |
| Training Structured Dictionaries | |
| |
| |
| |
| The Double-Sparsity Model | |
| |
| |
| |
| Union of Unitary Bases | |
| |
| |
| |
| The Signature Dictionary | |
| |
| |
| |
| Summary | |
| |
| |
| Further Reading | |
| |
| |
| |
| Image Compression - Facial Images | |
| |
| |
| |
| Compression of Facial Images | |
| |
| |
| |
| Previous Work | |
| |
| |
| |
| Sparse-Representation-Based Coding Scheme | |
| |
| |
| |
| The General Scheme | |
| |
| |
| |
| VQ Versus Sparse Representations | |
| |
| |
| |
| More Details and Results | |
| |
| |
| |
| K-SVD Dictionaries | |
| |
| |
| |
| Reconstructed Images | |
| |
| |
| |
| Run-Time and Memory Usage | |
| |
| |
| |
| Comparing to Other Techniques | |
| |
| |
| |
| Dictionary Redundancy | |
| |
| |
| |
| Post-Processing for Deblocking | |
| |
| |
| |
| The Blockiness Artifacts | |
| |
| |
| |
| Possible Approaches For Deblocking | |
| |
| |
| |
| Learning-Based Deblocking Approach | |
| |
| |
| |
| Deblocking Results | |
| |
| |
| |
| Summary | |
| |
| |
| Further Reading | |
| |
| |
| |
| Image Denoising | |
| |
| |
| |
| General Introduction - Image Denoising | |
| |
| |
| |
| The Beginning: Global Modeling | |
| |
| |
| |
| The Core Image-Denoising Algorithm | |
| |
| |
| |
| Various Improvements | |
| |
| |
| |
| From Global to Local Modeling | |
| |
| |
| |
| The General Methodology | |
| |
| |
| |
| Learning the Shrinkage Curves | |
| |
| |
| |
| Learned Dictionary and Globalizing the Prior | |
| |
| |
| |
| The Non-Local-Means Algorithm | |
| |
| |
| |
| 3D-DCT Shrinkage: BM3D Denoising | |
| |
| |
| |
| SURE for Automatic Parameter Setting | |
| |
| |
| |
| Development of the SURE | |
| |
| |
| |
| Demonstrating SURE to Global-Threhsolding | |
| |
| |
| |
| Summary | |
| |
| |
| Further Reading | |
| |
| |
| |
| Other Applications | |
| |
| |
| |
| General | |
| |
| |
| |
| Image Separation via MCA | |
| |
| |
| |
| Image = Cartoon + Texture | |
| |
| |
| |
| Global MCA for Image Separation | |
| |
| |
| |
| Local MCA for Image Separation | |
| |
| |
| |
| Image Inpainting and Impulsive Noise Removal | |
| |
| |
| |
| Inpainting Sparse-Land Signals - Core Principles | |
| |
| |
| |
| Inpainting Images - Local K-SVD | |
| |
| |
| |
| Inpainting Images - The Global MCA | |
| |
| |
| |
| Impulse-Noise Filtering | |
| |
| |
| |
| Image Scale-Up | |
| |
| |
| |
| Modeling the Problem | |
| |
| |
| |
| The Super-Resolution Algorithm | |
| |
| |
| |
| Scaling-Up Results | |
| |
| |
| |
| Image Scale-Up: Summary | |
| |
| |
| |
| Summary | |
| |
| |
| Further Reading | |
| |
| |
| |
| Epilogue | |
| |
| |
| |
| What is it All About? | |
| |
| |
| |
| What is Still Missing? | |
| |
| |
| |
| Bottom Line | |
| |
| |
| Notation | |
| |
| |
| Acronyms | |
| |
| |
| Index | |