xvi Contents
3 Pursuit Algorithms – Practice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.1 Greedy Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.1.1 The Core Idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.1.2 The Orthogonal-Matching-Pursuit . . . . . . . . . . . . . . . . . . . . . . 36
3.1.3 Other Greedy Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.1.4 Normalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.1.5 Rate of Decay of the Residual in Greedy Methods . . . . . . . . . 43
3.1.6 Thresholding Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.1.7 Numerical Demonstration of Greedy Algorithms . . . . . . . . . . 46
3.2 Convex Relaxation Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.2.1 Relaxation of the `
0
-Norm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.2.2 Numerical Algorithms for Solving (P
1
) . . . . . . . . . . . . . . . . . . 51
3.2.3 Numerical Demonstration of Relaxation Methods . . . . . . . . . 51
3.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4 Pursuit Algorithms – Guarantees .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.1 Back to the Two-Ortho Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.1.1 OMP Performance Guarantee . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.1.2 BP Performance Guarantee . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.2 The General Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.2.1 OMP Performance Guarantee . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.2.2 Thresholding Performance Guarantee . . . . . . . . . . . . . . . . . . . 67
4.2.3 BP Performance Guarantee . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.2.4 Performance of Pursuit Algorithms – Summary . . . . . . . . . . . 71
4.3 The Role of the Sign-Pattern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.4 Tropp’s Exact Recovery Condition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5 From Exact to Approximate Solutions .
. . . . . . . . . . . . . . . . . . . . . . . . . . . 79
5.1 General Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
5.2 Stability of the Sparsest Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
5.2.1 Uniqueness versus Stability – Gaining Intuition . . . . . . . . . . . 80
5.2.2 Theoretical Study of the Stability of (P
0
) . . . . . . . . . . . . . . . . 82
5.2.3 The RIP and Its Use for Stability Analysis . . . . . . . . . . . . . . . 86
5.3 Pursuit Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
5.3.1 OMP and BP Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
5.3.2 Iteratively-Reweighed-Least-Squares (IRLS) . . . . . . . . . . . . . 91
5.3.3 The LARS Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
5.3.4 Quality of Approximations Obtained . . . . . . . . . . . . . . . . . . . . 98
5.4 The Unitary Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
5.5 Performance of Pursuit Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
5.5.1 BPDN Stability Guarantee . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
5.5.2 Thresholding Stability Guarantee . . . . . . . . . . . . . . . . . . . . . . . 104