Compressed sensing and its applications: 3 MATHEON conf. 2017

ANHA Series Preface......Page 6
Preface......Page 9
Contents......Page 11
Acronyms......Page 16
An Introduction to Compressed Sensing......Page 17
 1 Introduction......Page 18
 2 Preliminaries......Page 20
  2.1 Norms and Quasinorms......Page 21
  2.2 Random Variables, Vectors, and Matrices......Page 23
 3 Signal Models......Page 26
  3.1 Sparse Vectors......Page 28
  3.2 Block- and Group-Sparse Vectors......Page 32
  3.3 Low-Rank Matrices......Page 33
  3.4 Low-Complexity Models in Bases and Frames......Page 36
  4.1 Exact Recovery......Page 37
  4.2 Connections to Conic Integral Geometry......Page 44
 5 Exact Recovery of Sparse Vectors......Page 48
 6 Characterization of Measurement Matrices......Page 50
  6.1 Null Space Property......Page 51
  6.2 Restricted Isometry Property......Page 54
  6.3 Mutual Coherence......Page 55
  6.4 Quotient Property......Page 56
  7.1 Restricted Isometries......Page 57
  7.2 Random Matrices and the Null Space Property......Page 61
 8 An Algorithmic Primer......Page 63
  8.1 Convex Programming......Page 64
  8.2 Thresholding Algorithms......Page 65
  8.3 Greedy Methods......Page 71
  8.4 Iteratively Reweighted Least-Squares......Page 74
 9 Conclusion......Page 76
 References......Page 77
 1 Introduction......Page 82
  1.1 Notation......Page 83
 2 Key Concepts......Page 84
 3 Two Fundamental Limits......Page 87
  4.1 Memoryless One-Bit Compressed Sensing: Zero Thresholds......Page 89
  4.2 Memoryless One-Bit Compressed Sensing With Dithering......Page 93
  4.4 Exponential Error Decay Via Adaptive Thresholds......Page 97
 5 Memoryless Multi-bit Compressed Sensing......Page 100
 6 Noise-Shaping Methods......Page 104
 References......Page 107
On Reconstructing Functions from Binary Measurements......Page 111
 1 Introduction......Page 112
  2.1 Definition......Page 115
  2.2 Properties......Page 118
 3 Reconstruction Space......Page 119
  4.1 PBDW Method......Page 121
  4.2 Generalized Sampling......Page 122
  4.3 The Stable Sampling Rate for the Walsh-Wavelet Case......Page 124
  5.1 Classical Compressed Sensing......Page 126
  5.3 Taking Structure and Infinite Dimensionality into Account......Page 128
  5.4 Points of Discussion Regarding Structure......Page 135
 6 Conclusion......Page 139
 References......Page 140
 1 Introduction......Page 143
  1.1 Notation and Setup......Page 144
  1.2 Related Work and Background......Page 145
 2 Simple Classification Approach......Page 146
  2.1 Analytical Justification......Page 149
  2.2 Experimental Results......Page 151
 3 Hierarchical Classification......Page 155
  3.1 Experimental Results......Page 156
  4.1 Parameter Selection......Page 158
  4.3 Efficient Representations......Page 161
 5 Conclusion......Page 162
 References......Page 163
 1 Introduction......Page 166
 2 The Learning Problem......Page 168
 3 Deep Neural Networks......Page 174
  4.1 Understanding Deep Learning Requires Rethinking Generalization......Page 178
  4.2 Exploring Generalization in Deep Learning......Page 180
  4.3 A PAC-Bayesian Approach to Spectrally Normalized Margin Bounds for Neural Networks......Page 183
  4.4 Stability and Generalization......Page 185
  4.5 Robustness and Generalization......Page 188
  4.6 Stronger Generalization Bounds for Deep Nets  via a Compression Approach......Page 191
  4.7 Train Faster, Generalize Better: Stability of Stochastic Gradient Descent......Page 192
  4.8 On Large Batch Training for Deep Learning: Generalization Gap and Sharp Minima......Page 194
  4.10 Train Longer, Generalize Better: Closing the Generalization Gap in Large Batch Training of Neural Networks......Page 196
  4.12 Generalization Error and Adversarial Attacks......Page 198
  5.1 Problem 1: Generalization and Memorization......Page 199
  5.2 Problem 2: Generalization and Robustness......Page 200
  5.4 Problem 4: Generalization Error of Generative Models......Page 201
 6 Conclusions......Page 202
 References......Page 203
 1 Motivation and Outline......Page 207
 2 Basic Example......Page 208
  2.1 Testing Error Convergence for Various Values of ε......Page 211
 3 Analysis of Trivial Neural Networks for Inverse Problems......Page 212
  3.1 Matrix Case......Page 213
 4 Further Numerical Tests......Page 219
 References......Page 221
  1.1 Model Misspecification......Page 222
  1.2 Penalized Empirical Risk Minimization......Page 223
  1.3 Conditions on the Risk......Page 225
  1.4 Norm Penalties......Page 226
  1.5 Related Literature......Page 228
 2 Sharp Oracle Inequalities......Page 229
  2.1 Convex and Nondifferentiable......Page 230
  2.3 Asymptotic Interpretation......Page 231
  3.1 Regression......Page 232
  3.2 Classification......Page 238
  3.3 Dimension Reduction......Page 239
 4 Discussion......Page 242
 5 Appendix......Page 243
 References......Page 246
Median-Truncated Gradient Descent: A Robust and Scalable Nonconvex Approach for Signal Estimation......Page 248
 1 Introduction......Page 249
 2 Median-Truncated Gradient Descent......Page 250
 3 Robust Low-Rank Matrix Recovery......Page 252
  3.1 Median-TGD for Robust Low-Rank Matrix Recovery......Page 253
  3.2 Theoretical Guarantees......Page 254
 4 Robust Phase Retrieval......Page 256
  4.1 Median-TGD for Robust Phase Retrieval......Page 257
  4.2 Performance Guarantees......Page 258
 5 Highlights of Theoretical Analysis......Page 259
  5.1 Useful Properties of Median......Page 260
  5.2 Regularity Condition......Page 261
  6.1 Median-TGD for Low-Rank Matrix Recovery......Page 262
  6.2 Median-TGD for Phase Retrieval......Page 263
 7 Related Works......Page 268
 References......Page 269
 1 Introduction......Page 273
  2.1 Compressed Sensing Techniques......Page 275
  2.2 Total Variation Regularization and Related Methods......Page 277
 3 Computational Image Reconstruction......Page 279
 4 Challenges in Practical THz Single-Pixel Imaging......Page 281
 5 Calibration Problems......Page 282
  5.1 Self-calibration and Bilinear Inverse Problems......Page 283
  5.2 Single-Pixel and Retinex Denoising......Page 284
 6 Phase Retrieval in Single-Pixel Cameras......Page 288
  6.1 Algorithms for Phase Retrieval......Page 289
  6.2 Results......Page 292
 7 Conclusion......Page 297
 References......Page 298
 (95 volumes)......Page 301