1 An Invitation to Compressive Sensing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 What is Compressive Sensing?. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Applications, Motivations, and Extensions . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3 Overview of the Book . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
Notes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2 Sparse Solutions of Underdetermined Systems . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.1 Sparsity and Compressibility .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.2 Minimal Number of Measurements .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.3 NP-Hardness of 0-Minimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
Notes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3 Basic Algorithms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.1 Optimization Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.2 Greedy Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.3 Thresholding-BasedMethods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
Notes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4 BasisPursuit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
4.1 Null Space Property . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.2 Stability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
4.3 Robustness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
4.4 Recovery of Individual Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
4.5 The Projected Cross-Polytope .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
4.6 Low-Rank Matrix Recovery .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
Notes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
5 Coherence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
5.1 Definitions and Basic Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
5.2 Matrices with Small Coherence .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
5.3 Analysis of OrthogonalMatching Pursuit . . . . . . . . . . . . . . . . . . . . . . . . . . 123
5.4 Analysis of Basis Pursuit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
5.5 Analysis of Thresholding Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
Notes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
6 Restricted Isometry Property . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
6.1 Definitions and Basic Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
6.2 Analysis of Basis Pursuit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
6.3 Analysis of Thresholding Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
6.4 Analysis of Greedy Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
Notes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
7 Basic Tools from Probability Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
7.1 Essentials from Probability .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
7.2 Moments and Tails . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
7.3 Cram´er’s Theorem and Hoeffding’s Inequality.. . . . . . . . . . . . . . . . . . . . 188
7.4 Subgaussian Random Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
7.5 Bernstein Inequalities .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
Notes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
8 Advanced Tools from Probability Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
8.1 Expectation of Norms of Gaussian Vectors. . . . . . . . . . . . . . . . . . . . . . . . . 202
8.2 Rademacher Sums and Symmetrization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
8.3 Khintchine Inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
8.4 Decoupling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
8.5 Noncommutative Bernstein Inequality.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
8.6 Dudley’s Inequality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
8.7 Slepian’s and Gordon’s Lemmas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
8.8 Concentration of Measure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
8.9 Bernstein Inequality for Suprema of Empirical Processes . . . . . . . . . 247
Notes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
9 Sparse Recovery with Random Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
9.1 Restricted Isometry Property for Subgaussian Matrices . . . . . . . . . . . 272
9.2 Nonuniform Recovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
9.3 Restricted Isometry Property for Gaussian Matrices . . . . . . . . . . . . . . . 291
9.4 Null Space Property for Gaussian Matrices . . . . . . . . . . . . . . . . . . . . . . . . 293
9.5 Relation to Johnson–Lindenstrauss Embeddings.. . . . . . . . . . . . . . . . . . 298
Notes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306
10 GelfandWidths of 1-Balls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311
10.1 Definitions and Relation to Compressive Sensing . . . . . . . . . . . . . . . . . 311
10.2 Estimate for the GelfandWidths of 1-Balls . . . . . . . . . . . . . . . . . . . . . . . 317
10.3 Applications to the Geometry of Banach Spaces . . . . . . . . . . . . . . . . . . . 322
Notes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328
11 Instance Optimality and Quotient Property .. . . . . . . . . . . . . . . . . . . . . . . . . . . . 331
11.1 Uniform Instance Optimality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332
11.2 Robustness and Quotient Property . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337
11.3 Quotient Property for Random Matrices. . . . . . . . . . . . . . . . . . . . . . . . . . . . 343
11.4 Nonuniform Instance Optimality. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358
Notes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363
12 Random Sampling in Bounded Orthonormal Systems . . . . . . . . . . . . . . . . . 367
12.1 Bounded Orthonormal Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 368
12.2 Uncertainty Principles and Lower Bounds . . . . . . . . . . . . . . . . . . . . . . . . . 374
12.3 Nonuniform Recovery: Random Sign Patterns . . . . . . . . . . . . . . . . . . . . . 384
12.4 Nonuniform Recovery: Deterministic Sign Patterns . . . . . . . . . . . . . . . 392
12.5 Restricted Isometry Property .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404
12.6 Discrete Bounded Orthonormal Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . 416
12.7 Relation to the Λ1-Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 418
Notes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 420
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431
13 Lossless Expanders in Compressive Sensing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 435
13.1 Definitions and Basic Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 435
13.2 Existence of Lossless Expanders .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 439
13.3 Analysis of Basis Pursuit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443
13.4 Analysis of an Iterative Thresholding Algorithm . . . . . . . . . . . . . . . . . . 447
13.5 Analysis of a Simple Sublinear-Time Algorithm.. . . . . . . . . . . . . . . . . . 452
Notes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456
14 Recovery of Random Signals using Deterministic Matrices . . . . . . . . . . . 459
14.1 Conditioning of Random Submatrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460
14.2 Sparse Recovery via 1-Minimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 469
Notes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473
15 Algorithms for 1-Minimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 475
15.1 The Homotopy Method .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 476
15.2 Chambolle and Pock’s Primal-Dual Algorithm . . . . . . . . . . . . . . . . . . . . 481
15.3 Iteratively Reweighted Least Squares. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 492
Notes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 503
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 511
Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 515
A MatrixAnalysis. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 515
A.1 Vector and Matrix Norms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 515
A.2 The Singular Value Decomposition .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 525
A.3 Least Squares Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 531
A.4 Vandermonde Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 535
A.5 Matrix Functions .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 537
B ConvexAnalysis. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 543
B.1 Convex Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 543
B.2 Convex Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 545
B.3 The Convex Conjugate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 549
B.4 The Subdifferential . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 551
B.5 Convex Optimization Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 555
B.6 Matrix Convexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 564
C Miscellanea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 573
C.1 Fourier Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 573
C.2 Covering Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 575
C.3 The Gamma Function and Stirling’s Formula . . . . . . . . . . . . . . . . . . . . . . 577
C.4 The Multinomial Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 580
C.5 Some Elementary Estimates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 580
C.6 Estimates of Some Integrals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 581
C.7 Hahn–Banach Theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 583
C.8 Smoothing Lipschitz Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 583
C.9 Weak and Distributional Derivatives .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 585
C.10 Differential Inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 587
List of Symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 589
References. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 593
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 621
· · · · · · (收起)