A Mathematical Introduction to Compressive Sensing pdf epub mobi txt 電子書 下載2025

想要找書就要到 小美書屋

立刻按 ctrl+D收藏本頁

你會得到大驚喜!!

The first textbook completely devoted to the topic of compressive sensing

Comprehensive treatment of the subject, including background material from probability theory, detailed proofs of the main theorems, and an outline of possible applications

Numerous exercises designed to help students understand the material

An extensive bibliography with over 500 references that guide researchers through the literature

At the intersection of mathematics, engineering, and computer science sits the thriving field of compressive sensing. Based on the premise that data acquisition and compression can be performed simultaneously, compressive sensing finds applications in imaging, signal processing, and many other domains. In the areas of applied mathematics, electrical engineering, and theoretical computer science, an explosion of research activity has already followed the theoretical results that highlighted the efficiency of the basic principles. The elegant ideas behind these principles are also of independent interest to pure mathematicians.

A Mathematical Introduction to Compressive Sensing gives a detailed account of the core theory upon which the field is build. Key features include:

· The first textbook completely devoted to the topic of compressive sensing

· Comprehensive treatment of the subject, including background material from probability theory, detailed proofs of the main theorems, and an outline of possible applications

· Numerous exercises designed to help students understand the material

· An extensive bibliography with over 500 references that guide researchers through the literature

With only moderate prerequisites, A Mathematical Introduction to Compressive Sensing is an excellent textbook for graduate courses in mathematics, engineering, and computer science. It also serves as a reliable resource for practitioners and researchers in these disciplines who want to acquire a careful understanding of the subject.

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
· · · · · · (收起)