Sparse optimization theory and methods

Cover......Page 1
Title Page......Page 2
Copyright Page......Page 3
Table of Contents......Page 8
Dedication......Page 4
Preface......Page 6
 1.1 Introduction......Page 14
 1.2 Spark......Page 15
 1.3 Uniqueness via Mutual Coherence......Page 18
  1.4.1 Sub-Mutual Coherence and Coherence Rank......Page 23
  1.4.2 Improved Lower Bounds of Spark(A)......Page 25
  1.4.3 Improved Coherence Conditions......Page 30
 1.5 Babel Function and Sub-Babel Function......Page 31
 1.6 Notes......Page 36
2: Uniqueness of Solutions to l1-Minimization Problems......Page 38
 2.1 Strict Complementary Slackness Property (SCSP)......Page 39
  2.2.1 Preliminary......Page 41
  2.2.2 Necessary Condition (I): Range Space Property of AT......Page 44
  2.2.3 Necessary Condition (II): Full-Column-Rank Property......Page 47
  2.2.4 Sufficient Condition......Page 49
  2.2.5 Uniqueness Characterization......Page 53
 2.3 Least I1-Norm Non-negative Solution......Page 54
 2.4 Least l1-Norm Points in Polyhedra......Page 59
  2.4.1 Restricted Range Space Property of AT......Page 60
  2.4.2 Proof of Necessity......Page 61
  2.4.3 Proof of Sufficiency......Page 67
 2.5 Notes......Page 70
 3.1 Equivalence and Strong Equivalence......Page 72
 3.2 Standard l0- and l1-Minimization Problems......Page 74
 3.3 Problems with Non-negative Constraints......Page 77
 3.4 Application to Linear Programming......Page 81
 3.5 Equivalence of l0-Problem and Weighted l1-Problem......Page 82
 3.6 Sparse Vector Recovery......Page 88
  3.6.1 Uniform Recovery: RSP-Based Analysis......Page 92
  3.6.2 Beyond Uniform Recovery......Page 96
  3.7.1 Uniform Recovery: RSP+-Based Analysis......Page 98
  3.7.2 Non-uniform Recovery of Non-negative Vectors......Page 101
 3.8 Notes......Page 104
 4.1 Introduction......Page 106
 4.2 Sign Measurements and Recovery Criteria......Page 108
 4.3 Relaxation Models......Page 110
 4.4 Consistency Condition......Page 111
  4.4.1 Nonstandard Sign Function......Page 112
  4.4.2 Standard Sign Function......Page 114
 4.5 Reformulation of 1-Bit Compressed Sensing......Page 116
 4.6 Non-uniform Sign Recovery......Page 118
 4.7 Uniform Sign Recovery......Page 128
 4.8 Notes......Page 132
5: Stability of Linear Sparse Optimization Methods......Page 134
 5.1 Introduction......Page 135
 5.2 Hoffman’s Error Bound for Linear Systems......Page 137
 5.3 Weak RSP of Order k of AT......Page 140
 5.4 Stability of Standard l1-Minimization......Page 141
 5.5 Linear Dantzig Selector......Page 147
  5.6.1 Standard Dantzig Selector......Page 153
  5.6.2 Weighted Dantzig Selector......Page 154
  5.6.3 l1-Minimization with l∞-Norm Constraints......Page 155
  5.6.4 l1-Minimization with l1-Norm Constraints......Page 157
 5.7 Notes......Page 159
6: Stability of Nonlinear Sparse Optimization Methods......Page 162
 6.1 Introduction......Page 163
 6.2 Orthogonal Projection Operator......Page 165
  6.3.1 l2-Ball......Page 168
  6.3.2 General Unit Ball......Page 170
 6.4 A Necessary Condition for Stability......Page 172
 6.5 l1-Minimization with l2-Norm Constraints......Page 175
 6.6 Nonlinear Dantzig Selector......Page 184
 6.7 The LASSO Problem......Page 192
 6.9 Notes......Page 202
7: Reweighted l1-Algorithms......Page 206
 7.1 Merit Function for Sparsity......Page 207
  7.1.1 M(1)-Class Merit Functions......Page 209
  7.1.2 M(2)-Class Merit Functions......Page 213
 7.2 Reweighted l1-Methods......Page 217
  7.2.1 Examples of Weights......Page 220
 7.3 Numerical Experiments......Page 222
 7.4 Theoretical Analysis......Page 225
  7.4.1 Well-Definedness of Algorithms......Page 226
  7.4.2 Convergence to Sparse Points......Page 229
 7.6 Notes......Page 239
 8.1 Introduction......Page 242
 8.2 l0-Minimization with Non-negative Constraints......Page 243
  8.2.1 Optimal Weight via Dual Density......Page 244
  8.2.2 Dual-Density-Based Reweighted l1-Algorithm......Page 248
  8.2.3 Numerical Experiments......Page 251
  8.2.4 Theoretical Performance......Page 254
 8.3 DDRW for Standard l0-Minimization......Page 262
 8.4 Sparsity Enhancement for Weighted l1-Minimizers......Page 269
 8.5 Notes......Page 272
References......Page 274
Index......Page 294