Sampling Theory: Beyond Bandlimited Systems

Eldar Y.C.Sampling theory:beyond bandlimited systems (CUP,2015)(ISBN 9781107003392)(600dpi)(835pp) ......Page 3
Copyright ......Page 4
Contents vii ......Page 6
Preface page xvii ......Page 16
List of abbreviations xxiv ......Page 23
1 Introduction 1 ......Page 25
1.1 Standard sampling 2 ......Page 26
1.2 Beyond bandlimited signals 5 ......Page 29
1.3 Outline and outlook 6 ......Page 30
2.1 Signal expansions: some examples 9 ......Page 33
2.2.1 Subspaces 13 ......Page 37
2.2.2 Properties of subspaces 14 ......Page 38
2.3 Inner product spaces 15 ......Page 39
2.3.1 The inner product 16 ......Page 40
2.3.2 Orthogonality 17 ......Page 41
2.3.3 Calculus in inner product spaces 19 ......Page 43
2.3.4 Hilbert spaces 20 ......Page 44
2.4 Linear transformations 21 ......Page 45
2.4.1 Subspaces associated with a linear transformation 22 ......Page 46
2.4.2 Invertibility 24 ......Page 48
2.4.3 Direct-sum decompositions 25 ......Page 49
2.4.4 The adjoint 29 ......Page 53
2.5 Basis expansions 32 ......Page 56
2.5.1 Set transformations 33 ......Page 57
2.5.2 Bases 35 ......Page 59
2.5.3 Riesz bases 36 ......Page 60
2.5.4 Riesz basis expansions 40 ......Page 64
2.6 Projection operators 44 ......Page 68
2.6.1 Orthogonal projection operators 46 ......Page 70
2.6.2 Oblique projection operators 48 ......Page 72
2.7 Pseudoinverse of a transformation 51 ......Page 75
2.7.1 Definition and properties 52 ......Page 76
2.7.2 Matrices 54 ......Page 78
2.8 Frames 55 ......Page 79
2.8.1 Definition of frames 56 ......Page 80
2.8.2 Frame expansions 58 ......Page 62
2.8.3 The canonical dual 59 ......Page 83
2.9 Exercises 63 ......Page 87
3 Fourier analysis 67 ......Page 91
3.1.1 Linearity and time-invariance 68 ......Page 92
3.1.2 The impulse response 71 ......Page 95
3.1.3 Causality and stability 73 ......Page 97
3.2.1 Definition of the CTFT 75 ......Page 99
3.2.2 Properties of the CTFT 76 ......Page 100
3.2.3 Examples of the CTFT 77 ......Page 101
3.2.4 Fubini’s theorem 79 ......Page 103
3.3.1 Discrete-time impulse response 80 ......Page 104
3.3.2 Discrete-time Fourier transform 81 ......Page 105
3.3.3 Properties of the DTFT 82 ......Page 106
3.4 Continuous-discrete representations 85 ......Page 109
3.4.1 Poisson-sum formula 87 ......Page 111
3.4.2 Sampled correlation sequences 88 ......Page 112
3.5 Exercises 90 ......Page 114
4.1.1 Sampling and reconstruction spaces 95 ......Page 119
4.1.2 Practical sampling theorems 96 ......Page 120
4.2.1 The Shannon-Nyquist theorem 98 ......Page 122
4.2.2 Sampling by modulation 100 ......Page 124
4.2.3 Aliasing 102 ......Page 126
4.2.4 Orthonormal basis interpretation 105 ......Page 129
4.2.5 Towards more general sampling spaces 109 ......Page 133
4.3.1 Shift-invariant spaces 110 ......Page 134
4.3.2 Spline functions 112 ......Page 136
4.3.3 Digital communication signals 114 ......Page 138
4.3.4 Multiple generators 117 ......Page 141
4.3.5 Refinable functions 121 ......Page 145
4.4.1 Gabor spaces 122 ......Page 146
4.4.2 Wavelet expansions 126 ......Page 150
4.5 Union of subspaces 132 ......Page 156
4.5.1 Signal model 133 ......Page 157
4.5.2 Union classes 136 ......Page 160
4.6 Stochastic and smoothness priors 138 ......Page 162
4.7 Exercises 142 ......Page 166
5.1 Riesz basis in SI spaces 146 ......Page 170
5.1.1 Riesz basis condition 147 ......Page 171
5.1.2 Examples 149 ......Page 173
5.2.1 Biorthogonal basis 152 ......Page 176
5.2.2 Expansion coefficients 155 ......Page 179
5.2.3 Alternative basis expansions 156 ......Page 180
5.3 Partition of unity 161 ......Page 185
5.4 Redundant sampling in SI spaces 163 ......Page 187
5.4.1 Redundant bandlimited sampling 165 ......Page 189
5.4.2 Missing samples 168 ......Page 192
5.5 Multiple generators 169 ......Page 193
5.5.1 Riesz condition 170 ......Page 194
5.5.2 Biorthogonal basis 171 ......Page 195
5.6 Exercises 175 ......Page 199
6.1.1 Sampling setups 178 ......Page 202
6.1.2 Sampling process 179 ......Page 203
6.1.3 Unconstrained recovery 181 ......Page 205
6.1.4 Predefined recovery kernel 182 ......Page 206
6.1.5 Design objectives 183 ......Page 207
6.2.1 Geometric interpretation 186 ......Page 210
6.2.2 Equal sampling and prior spaces 188 ......Page 212
6.3 Sampling in general spaces 191 ......Page 215
6.3.1 The direct-sum condition 192 ......Page 216
6.3.2 Unique recovery 194 ......Page 218
6.3.3 Computing the oblique projection operator 198 ......Page 222
6.3.4 Oblique biorthogonal basis 202 ......Page 226
6.4.1 Consistent recovery 205 ......Page 229
6.4.2 Recovery error 208 ......Page 232
6.5.1 Least squares recovery 211 ......Page 235
6.5.2 Minimax recovery 213 ......Page 237
6.6 Constrained recovery 215 ......Page 239
6.6.1 Minimal-error recovery 216 ......Page 240
6.6.2 Least squares recovery 219 ......Page 243
6.6.3 Minimax recovery 222 ......Page 246
6.7 Unified formulation of recovery techniques 224 ......Page 248
6.8.1 Recovery methods 226 ......Page 250
6.8.2 Papoulis’ generalized sampling 227 ......Page 251
6.9 Exercises 235 ......Page 259
7.1.1 Smoothness prior 238 ......Page 262
7.1.2 Least squares solution 239 ......Page 263
7.1.3 Minimax solution 242 ......Page 266
7.1.4 Examples 243 ......Page 267
7.1.5 Multichannel sampling 247 ......Page 271
7.2.1 Least squares solution 249 ......Page 273
7.2.2 Minimax-regret solution 251 ......Page 275
7.2.3 Comparison between least squares and minimax 256 ......Page 280
7.3 Stochastic priors 259 ......Page 283
7.3.1 The hybrid Wiener filter 261 ......Page 285
7.3.2 Constrained reconstruction 263 ......Page 287
7.4.1 Summary of methods 265 ......Page 289
7.4.2 Unified view 268 ......Page 292
7.5 Sampling with noise 269 ......Page 293
7.5.1 Constrained reconstruction problem 270 ......Page 294
7.5.2 Least squares solution 272 ......Page 296
7.5.4 Minimax MSE filters 273 ......Page 297
7.5.6 Summary of the different filters 275 ......Page 299
7.5.7 Bandlimited interpolation 277 ......Page 301
7.5.8 Unconstrained recovery 279 ......Page 303
7.6 Exercises 281 ......Page 305
8 Nonlinear sampling 284 ......Page 308
8.1.1 Nonlinear model 285 ......Page 309
8.1.2 Wiener-Hammerstein systems 286 ......Page 310
8.2.1 Bandlimited signals 288 ......Page 312
8.2.2 Reproducing kernel Hilbert spaces 290 ......Page 314
8.3 Subspace-preserving nonlinearities 294 ......Page 318
8.4 Equal prior and sampling spaces 295 ......Page 319
8.4.1 Iterative recovery 297 ......Page 321
8.4.2 Linearization approach 302 ......Page 326
8.4.3 Conditions for invertibility 305 ......Page 329
8.4.4 Newton algorithm 306 ......Page 330
8.4.5 Comparison between algorithms 310 ......Page 334
8.5.1 Recovery algorithms 312 ......Page 336
8.5.2 Uniqueness conditions 314 ......Page 338
8.5.3 Algorithm convergence 317 ......Page 341
8.5.4 Examples 319 ......Page 343
8.6 Exercises 322 ......Page 346
9 Resampling 325 ......Page 349
9.1 Bandlimited sampling rate conversion 326 ......Page 350
9.1.1 Interpolation by an integer factor I 327 ......Page 351
9.1.2 Decimation by an integer factor D 329 ......Page 353
9.1.3 Rate conversion by a rational factor I/D 332 ......Page 356
9.1.4 Rate conversion by arbitrary factors 334 ......Page 358
9.2.1 Interpolation formula 337 ......Page 361
9.2.2 Comparison with bandlimited interpolation 340 ......Page 364
9.3 Dense-grid interpolation 341 ......Page 365
9.3.1 Subspace prior 342 ......Page 366
9.3.2 Smoothness prior 348 ......Page 372
9.3.3 Stochastic prior 349 ......Page 373
9.4 Projection-based resampling 350 ......Page 374
9.4.1 Orthogonal projection resampling 351 ......Page 375
9.4.2 Oblique projection resampling 357 ......Page 381
9.5.1 Computational aspects 365 ......Page 389
9.6 Exercises 366 ......Page 390
10 Union of subspaces 370 ......Page 394
10.1.1 Multiband sampling 371 ......Page 395
10.1.2 Time-delay estimation 373 ......Page 397
10.2.1 Definition and properties 375 ......Page 399
10.2.2 Classes of unions 378 ......Page 402
10.3.1 Unique and stable sampling 382 ......Page 406
10.3.2 Rate requirements 386 ......Page 410
10.3.3 Xampling: compressed sampling methods 387 ......Page 411
10.4 Exercises 389 ......Page 413
11.1 Motivation for compressed sensing 392 ......Page 416
11.2 Sparsity models 394 ......Page 418
11.2.1 Normed vector spaces 395 ......Page 419
11.2.2 Sparse signal models 397 ......Page 421
11.3 Sensing matrices 403 ......Page 427
11.3.1 Null space conditions 404 ......Page 428
11.3.2 The restricted isometry property 410 ......Page 434
11.3.3 Coherence 417 ......Page 441
11.3.4 Uncertainty relations 422 ......Page 446
11.3.5 Sensing matrix constructions 428 ......Page 452
11.4 Recovery algorithms 431 ......Page 455
11.4.1 ^recovery 432 ......Page 456
11.4.2 Greedy algorithms 436 ......Page 460
11.4.3 Combinatorial algorithms 440 ......Page 464
11.4.4 Analysis versus synthesis methods 441 ......Page 465
11.5 Recovery guarantees 442 ......Page 466
11.5.1 t\ recovery: RIP-based results 443 ......Page 467
11.5.2 i\ recovery: coherence-based results 450 ......Page 474
11.5.3 Instance-optimal guarantees 451 ......Page 475
11.5.4 The cross-polytope and phase transitions 453 ......Page 477
11.5.5 Guarantees on greedy methods 455 ......Page 479
11.6.1 Signal model 457 ......Page 481
11.6.2 Recovery algorithms 459 ......Page 483
11.6.3 Performance guarantees 465 ......Page 489
11.6.4 Infinite measurement vectors 466 ......Page 490
11.7 Summary and extensions 470 ......Page 494
11.8 Exercises 471 ......Page 495
12.1.1 Signal model 475 ......Page 499
12.1.2 Problem formulation 478 ......Page 502
12.1.3 Connection with block sparsity 479 ......Page 503
12.2 Uniqueness and stability 482 ......Page 506
12.2.1 Block RIP 483 ......Page 507
12.2.2 Block coherence and subcoherence 485 ......Page 509
12.3.1 Exponential recovery algorithm 488 ......Page 512
12.3.2 Convex recovery algorithm 489 ......Page 513
12.3.3 Greedy algorithms 490 ......Page 514
12.4.1 Block basis pursuit recovery 493 ......Page 517
12.4.2 Random matrices and block RIP 499 ......Page 523
12.5.1 Recovery conditions 500 ......Page 524
12.5.2 Extensions 504 ......Page 528
12.5.3 Proofs of theorems 507 ......Page 531
12.6 Dictionary and subspace learning 513 ......Page 537
12.6.1 Dictionary learning 514 ......Page 538
12.6.2 Subspace learning 517 ......Page 541
12.7.1 BCS problem formulation 522 ......Page 546
12.7.2 BCS with a constrained dictionary 523 ......Page 547
12.7.3 BCS with multiple measurement matrices 531 ......Page 555
12.8 Exercises 534 ......Page 558
13.1.1 Sparse union of SI subspaces 539 ......Page 563
13.1.2 Sub-Nyquist sampling 541 ......Page 565
13.2.1 Union of discrete sequences 543 ......Page 567
13.2.2 Reduced-rate sampling 545 ......Page 369
13.3 Application to detection 553 ......Page 577
13.3.1 Matched-filter receiver 554 ......Page 578
13.3.2 Maximum-likelihood detector 556 ......Page 580
13.3.3 Compressed-sensing receiver 557 ......Page 581
13.4 Multiuser detection 563 ......Page 587
13.4.1 Conventional multiuser detectors 564 ......Page 588
13.4.2 Reduced-dimension MUD (RD-MUD) 565 ......Page 589
13.4.3 Performance of RD-MUD 568 ......Page 592
13.5 Exercises 571 ......Page 595
14.1 Sampling of multiband signals 574 ......Page 598
14.2.1 I/Q demodulation 577 ......Page 601
14.2.2 Landau rate 579 ......Page 603
14.2.3 Direct undersampling of bandpass signals 582 ......Page 606
14.3.1 Bandpass sampling 587 ......Page 611
14.3.2 Multiband sampling 592 ......Page 616
14.3.3 Universal sampling patterns 602 ......Page 626
14.3.4 Hardware considerations 606 ......Page 630
14.4 Modulated wideband converter 608 ......Page 632
14.4.1 MWC operation 610 ......Page 634
14.4.2 MWC signal recovery 611 ......Page 635
14.4.3 Collapsing channels 614 ......Page 638
14.4.4 Sign-alternating sequences 620 ......Page 644
14.5 Blind sampling of multiband signals 624 ......Page 648
14.5.1 Minimal sampling rate 625 ......Page 649
14.5.2 Blind recovery 627 ......Page 651
14.5.3 Multicoset sampling and the sparse SI framework 629 ......Page 653
14.5.4 Sub-Nyquist baseband processing 631 ......Page 655
14.5.5 Noise folding 632 ......Page 656
14.6 Hardware prototype of sub-Nyquist multiband sensing 633 ......Page 657
14.7.1 MWC designs 636 ......Page 660
14.7.2 Sign-alternating sequences 638 ......Page 662
14.7.3 Effect of CTF length 639 ......Page 663
14.7.4 Parameter limits 640 ......Page 664
14.8 Exercises 644 ......Page 668
15.1 Finite rate of innovation signals 649 ......Page 673
15.1.1 Shift-invariant spaces 650 ......Page 674
15.1.2 Channel sounding 651 ......Page 675
15.1.3 Other examples 654 ......Page 678
15.2 Periodic pulse streams 656 ......Page 680
15.2.1 Time-domain formulation 657 ......Page 681
15.2.2 Frequency-domain formulation 660 ......Page 684
15.2.3 Prony’s method 664 ......Page 688
15.2.4 Noisy samples 667 ......Page 691
15.2.5 Matrix pencil 672 ......Page 696
15.2.6 Subspace methods 677 ......Page 701
15.2.7 Covariance-based methods 682 ......Page 706
15.2.8 Compressed sensing formulation 686 ......Page 710
15.2.9 Sub-Nyquist sampling 688 ......Page 712
15.3.1 Coset sampling 692 ......Page 716
15.3.2 Sum-of-sincs filter 695 ......Page 719
15.3.3 Noise effects 698 ......Page 722
15.3.4 Finite and infinite pulse streams 701 ......Page 725
15.4 Multichannel sampling 705 ......Page 729
15.4.1 Modulation-based multichannel systems 706 ......Page 730
15.4.2 Filterbank sampling 714 ......Page 738
15.5 Noisy FRI recovery 717 ......Page 741
15.5.1 MSE bounds 718 ......Page 742
15.5.2 Periodic versus semiperiodic FRI signals 721 ......Page 745
15.6 General FRI sampling 723 ......Page 747
15.6.1 Sampling method 724 ......Page 748
15.6.2 Minimal sampling rate 725 ......Page 749
15.6.3 Least squares recovery 727 ......Page 751
15.6.4 Iterative recovery 728 ......Page 752
15.7.1 Sub-Nyquist radar 733 ......Page 757
15.7.2 Time-varying system identification 743 ......Page 767
15.7.3 Ultrasound imaging 744 ......Page 768
15.8 Exercises 750 ......Page 774
A. 1.1 Matrix operations 755 ......Page 779
A. 1.2 Matrix properties 756 ......Page 780
A. 1.3 Special classes of matrices 758 ......Page 782
A.2.1 Eigenvalues and eigenvectors 760 ......Page 784
A.2.2 Singular value decomposition 763 ......Page 787
A.3 Linear equations 764 ......Page 788
A.4 Matrix norms 765 ......Page 789
A.4.1 Induced norms 766 ......Page 790
A.4.3 Schatten norms 767 ......Page 791
B. 1.1 Probability density function 768 ......Page 792
B. 1.2 Jointly random variables 769 ......Page 793
B.3.1 Continuous-time random processes 770 ......Page 794
B.3.2 Discrete-time random processes 772 ......Page 796
B.4 Sampling of bandlimited processes 773 ......Page 797
References 775 ......Page 799
Index 799 ......Page 823
cover ......Page 1