Mathematical Methods and Algorithms for Signal Processing
Todd K. Moon, Wynn C. Stirling
Résumé
- .
- Presents mathematics with applications drawn from signal processing literature and practice to motivate learning in a wide variety of areas
- .
- Application topics include both traditional areas? such as spectral estimation, adaptive filtering, detection, and estimation? and also more recent topics such as blind source separation and the EM algorithm
- .
- A foundation in vector spaces is presented as a unifying framework for a variety of signal processing concepts, including least-squares, minimum mean-squares, wavelet transforms, digital communications, subspace methods, and more
- .
- Many exercises are provided to reinforce understanding, extend the material, and apply the concepts
- .
1 Introduction and Foundations 3
1.1 What is signal processing? 3
1.2 Mathematical topics embraced by signal 5
processing
1.3 Mathematical models 6
1.4 Models for linear systems and signals 7
1.4.1 Linear discrete-time models 7
1.4.2 Stochastic MA and AR models 12
1.4.3 Continuous-time notation 20
1.4.4 Issues and applications 21
1.4.5 Identification of the modes 26
1.4.6 Control of the modes 28
1.5 Adaptive filtering 28
1.5.1 System identification 29
1.5.2 Inverse system identification 29
1.5.3 Adaptive predictors 29
1.5.4 Interference cancellation 30
1.6 Gaussian random variables and random 31
processes
1.6.1 Conditional Gaussian densities 36
1.7 Markov and Hidden Markov Models 37
1.7.1 Markov models 37
1.7.2 Hidden Markov models 39
1.8 Some aspects of proofs 41
1.8.1 Proof by computation: direct proof 43
1.8.2 Proof by contradiction 45
1.8.3 Proof by induction 46
1.9 An application: LFSRs and Massey's 48
algorithm
1.9.1 Issues and applications of LFSRs 50
1.9.2 Massey's algorithm 52
1.9.3 Characterization of LFSR length in 53
Massey's algorithm
1.10 Exercises 58
1.11 References 67
II Vector Spaces and Linear Algebra 69
2 Signal Spaces 71
2.1 Metric spaces 72
2.1.1 Some topological terms 76
2.1.2 Sequences, Cauchy sequences, and 78
completeness
2.1.3 Technicalities associated with the 82
L(p) and L(Infinity) spaces
2.2 Vector spaces 84
2.2.1 Linear combinations of vectors 87
2.2.2 Linear independence 88
2.2.3 Basis and dimension 90
2.2.4 Finite-dimensional vector spaces 93
and matrix notation
2.3 Norms and normed vector spaces 93
2.3.1 Finite-dimensional normed linear 97
spaces
2.4 Inner products and inner-product spaces 97
2.4.1 Weak convergence 99
2.5 Induced norms 99
2.6 The Cauchy-Schwarz inequality 100
2.7 Direction of vectors: Orthogonality 101
2.8 Weighted inner products 103
2.8.1 Expectation as an inner product 105
2.9 Hilbert and Banach spaces 106
2.10 Orthogonal subspaces 107
2.11 Linear transformations: Range and 108
nullspace
2.12 Inner-sum and direct-sum spaces 110
2.13 Projections and orthogonal projections 113
2.13.1 Projection matrices 115
2.14 The projection theorem 116
2.15 Orthogonalization of vectors 118
2.16 Some final technicalities for 121
infinite dimensional spaces
2.17 Exercises 121
2.18 References 129
3 Representation and Approximation in Vector 130
Spaces
3.1 The Approximation problem in Hilbert 130
space
3.1.1 The Grammian matrix 133
3.2 The Orthogonality principle 135
3.2.1 Representations in 136
infinite-dimensional space
3.3 Error minimization via gradients 137
3.4 Matrix Representations of 138
least-squares problems
3.4.1 Weighted least-squares 140
3.4.2 Statistical properties of the 140
least-squares estimate
3.5 Minimum error in Hilbert-space 141
approximations
Applications of the orthogonality theorem
3.6 Approximation by continuous polynomials 143
3.7 Approximation by discrete polynomials 145
3.8 Linear regression 147
3.9 Least-squares filtering 149
3.9.1 Least-squares prediction and AR 154
spectrum estimation
3.10 Minimum mean-square estimation 156
3.11 Minimum mean-squared error (MMSE) 157
filtering
3.12 Comparison of least squares and 161
minimum mean squares
3.13 Frequency-domain optimal filtering 162
3.13.1 Brief review of stochastic 162
processes and Laplace transforms
3.13.2 Two-sided Laplace transforms and 165
their decompositions
3.13.3 The Wiener-Hopf equation 169
3.13.4 Solution to the Wiener-Hopf 171
equation
3.13.5 Examples of Wiener filtering 174
3.13.6 Mean-square error 176
3.13.7 Discrete-time Wiener filters 176
3.14 A dual approximation problem 179
3.l5 Minimum-norm solution of 182
underdetermined equations
3.16 Iterative Reweighted LS (IRLS) for 183
L(p) optimization
3.17 Signal transformation and generalized 186
Fourier series
3.18 Sets of complete orthogonal functions 190
3.18.1 Trigonometric functions 190
3.18.2 Orthogonal polynomials 190
3.18.3 Sinc functions 193
3.18.4 Orthogonal wavelets 194
3.19 Signals as points: Digital 208
communications
3.19.1 The detection problem 210
3.19.2 Examples of basis functions used 212
in digital communications
3.19.3 Detection in nonwhite noise 213
3.20 Exercises 215
3.21 References 228
4 Linear Operators and Matrix Inverses 229
4.1 Linear operators 230
4.1.1 Linear functionals 231
4.2 Operator norms 232
4.2.1 Bounded operators 233
4.2.2 The Neumann expansion 235
4.2.3 Matrix norms 235
4.3 Adjoint operators and transposes 237
4.3.1 A dual optimization problem 239
4.4 Geometry of linear equations 239
4.5 Four fundamental subspaces of a linear 242
operator
4.5.1 The four fundamental subspaces 246
with non-closed range
4.6 Some properties of matrix inverses 247
4.6.1 Tests for invertibility of matrices 248
4.7 Some results on matrix rank 249
4.7.1 Numeric rank 250
4.8 Another look at least squares 251
4.9 Pseudoinverses 251
4.10 Matrix condition number 253
4.11 Inverse of a small-rank adjustment 258
4.11.1 An application: the RLS filter 259
4.11.2 Two RLS applications 261
4.12 Inverse of a block (partitioned) 264
matrix
4.12.1 Application: Linear models 267
4.13 Exercises 268
4.14 References 274
5 Some Important Matrix Factorizations 275
5.1 The LU factorization 275
5.1.1 Computing the determinant using the 277
LU factorization
5.1.2 Computing the LU factorization 278
5.2 The Cholesky factorization 283
5.2.1 Algorithms for computing the 284
Cholesky factorization
5.3 Unitary matrices and the QR 285
factorization
5.3.1 Unitary matrices 285
5.3.2 The QR factorization 286
5.3.3 QR factorization and least-squares 286
filters
5.3.4 Computing the QR factorization 287
5.3.5 Householder transformations 287
5.3.6 Algorithms for Householder 291
transformations
5.3.7 QR factorization using Givens 293
rotations
5.3.8 Algorithms for QR factorization 295
using Givens rotations
5.3.9 Solving least-squares problems 296
using Givens rotations
5.3.10 Givens rotations via CORDIC 297
rotations
5.3.11 Recursive updates to the QR 299
factorization
5.4 Exercises 300
5.5 References 304
6 Eigenvalues and Eigenvectors 305
6.1 Eigenvalues and linear systems 305
6.2 Linear dependence of eigenvectors 308
6.3 Diagonalization of a matrix 309
6.3.1 The Jordan form 311
6.3.2 Diagonalization of self-adjoint 312
matrices
6.4 Geometry of invariant subspaces 316
6.5 Geometry of quadratic forms and the 318
minimax principle
6.6 Extremal quadratic forms subject to 324
linear constraints
6.7 The Gershgorin circle theorem 324
Application of Eigendecomposition methods
6.8 Karhunen-Loeve low-rank approximations 327
and principal methods
6.8.1 Principal component methods 329
6.9 Eigenfilters 330
6.9.1 Eigenfilters for random signals 330
6.9.2 Eigenfilter for designed spectral 332
response
6.9.3 Constrained eigenfilters 334
6.10 Signal subspace techniques 336
6.10.1 The signal model 336
6.10.2 The noise model 337
6.10.3 Pisarenko harmonic decomposition 338
6.10.4 MUSIC 339
6.11 Generalized eigenvalues 340
6.11.1 An application: ESPRIT 341
6.12 Characteristic and minimal polynomials 342
6.12.1 Matrix polynomials 342
6.12.2 Minimal polynomials 344
6.13 Moving the eigenvalues around: 344
Introduction to linear control
6.14 Noiseless constrained channel capacity 347
6.15 Computation of eigenvalues and 350
eigenvectors
6.15.1 Computing the largest and 350
smallest eigenvalues
6.15.2 Computing the eigenvalues of a 351
symmetric matrix
6.15.3 The QR iteration 352
6.16 Exercises 355
6.17 References 368
7 The Singular Value Decomposition 369
7.1 Theory of the SVD 369
7.2 Matrix structure from the SVD 372
7.3 Pseudoinverses and the SVD 373
7.4 Numerically sensitive problems 375
7.5 Rank-reducing approximations: 377
Effective rank
Applications of the SVD
7.6 System identification using the SVD 378
7.7 Total least-squares problems 381
7.7.1 Geometric interpretation of the 385
TLS solution
7.8 Partial total least squares 386
7.9 Rotation of subspaces 389
7.10 Computation of the SVD 390
7.11 Exercises 392
7.12 References 395
8 Some Special Matrices and Their 396
Applications
8.1 Modal matrices and parameter estimation 396
8.2 Permutation matrices 399
8.3 Toeplitz matrices and some applications 400
8.3.1 Durbin's algorithm 402
8.3.2 Predictors and lattice filters 403
8.3.3 Optimal predictors and Toeplitz 407
inverses
8.3.4 Toeplitz equations with a general 408
right-hand side
8.4 Vandermonde matrices 409
8.5 Circulant matrices 410
8.5.1 Relations among Vandermonde, 412
circulant, and companion matrices
8.5.2 Asymptotic equivalence of the 413
eigenvalues of Toeplitz and circulant
matrices
8.6 Triangular matrices 416
8.7 Properties preserved in matrix products 417
8.8 Exercises 418
8.9 References 421
9 Kronecker Products and the Vec Operator 422
9.1 The Kronecker product and Kronecker sum 422
9.2 Some applications of Kronecker products 425
9.2.1 Fast Hadamard transforms 425
9.2.2 DFT computation using Kronecker 426
products
9.3 The vec operator 428
9.4 Exercises 431
9.5 References 433
III Detection, Estimation, and Optimal 435
Filtering
10 Introduction to Detection and Estimation, 437
and Mathematical Notation
10.1 Detection and estimation theory 437
10.1.1 Game theory and decision theory 438
10.1.2 Randomization 440
10.1.3 Special cases 441
10.2 Some notational conventions 442
10.2.1 Populations and statistics 443
10.3 Conditional expectation 444
10.4 Transformations of random variables 445
10.5 Sufficient statistics 446
10.5.1 Examples of sufficient statistics 450
10.5.2 Complete sufficient statistics 451
10.6 Exponential families 453
10.7 Exercises 456
10.8 References 459
11 Detection Theory 460
11.1 Introduction to hypothesis testing 460
11.2 Neyman-Pearson theory 462
11.2.1 Simple binary hypothesis testing 462
11.2.2 The Neyman-Pearson lemma 463
11.2.3 Application of the Neyman-Pearson 466
lemma
11.2.4 The likelihood ratio and the 467
receiver operating characteristic
11.2.5 A Poisson example 468
11.2.6 Some Gaussian examples 469
11.2.7 Properties of the ROC 480
11.3 Neyman-Pearson testing with composite 483
binary hypotheses
11.4 Bayes decision theory 485
11.4.1 The Bayes principle 486
11.4.2 The risk function 487
11.4.3 Bayes risk 489
11.4.4 Bayes tests of simple binary 490
hypotheses
11.4.5 Posterior distributions 494
11.4.6 Detection and sufficiency 498
11.4.7 Summary of binary decision 498
problems
11.5 Some M-ary problems 499
11.6 Maximum-likelihood detection 503
11.7 Approximations to detection 503
performance: The union bound
11.8 Invariant Tests 504
11.8.1 Detection with random (nuisance) 507
parameters
11.9 Detection in continuous time 512
11.9.1 Some extensions and precautions 516
11.10 Minimax Bayes decisions 520
11.10.1 Bayes envelope function 520
11.10.2 Minimax rules 523
11.10.3 Minimax Bayes in 524
multiple-decision problems
11.10.4 Determining the least favorable 528
prior
11.10.5 A minimax example and the 529
minimax theorem
11.11 Exercises 532
11.12 References 541
12 Estimation Theory 542
12.1 The maximum-likelihood principle 542
12.2 ML estimates and sufficiency 547
12.3 Estimation quality 548
12.3.1 The score function 548
12.3.2 The Cramer-Rao lower bound 550
12.3.3 Efficiency 552
12.3.4 Asymptotic properties of 553
maximum-likelihood estimators
12.3.5 The multivariate normal case 556
12.3.6 Minimum-variance unbiased 559
estimators
12.3.7 The linear statistical model 561
12.4 Applications of ML estimation 561
12.4.1 ARMA parameter estimation 561
12.4.2 Signal subspace identification 565
12.4.3 Phase estimation 566
12.5 Bayes estimation theory 568
12.6 Bayes risk 569
12.6.1 MAP estimates 573
12.6.2 Summary 574
12.6.3 Conjugate prior distributions 574
12.6.4 Connections with minimum 577
mean-squared estimation
12.6.5 Bayes estimation with the 578
Gaussian distribution
12.7 Recursive estimation 580
12.7.1 An example of non-Gaussian 582
recursive Bayes
12.8 Exercises 584
12.9 References 590
13 The Kalman Filter 591
13.1 The state-space signal model 591
13.2 Kalman filter I: The Bayes approach 592
13.3 Kalman filter I: The innovations 595
approach
13.3.1 Innovations for processes with 596
linear observation models
13.3.2 Estimation using the innovations 597
process
13.3.3 Innovations for processes with 598
state-space models
13.3.4 A recursion for P(t|t-1) 599
13.3.5 The discrete-time Kalman filter 601
13.3.6 Perspective 602
13.3.7 Comparison with the RLS adaptive 603
filter algorithm
13.4 Numerical considerations: Square-root 604
filters
13.5 Application in continuous-time systems 606
13.5.1 Conversion from continuous time 606
to discrete time
13.5.2 A simple kinematic example 606
13.6 Extensions of Kalman filtering to 607
nonlinear systems
13.7 Smoothing 613
13.7.1 The Rauch-Tung-Streibel 613
fixed-interval smoother
13.8 Another approach: H(Infinity) 616
smoothing
13.9 Exercises 617
13.10 References 620
IV Iterative and Recursive Methods in Signal 621
Processing
14 Basic Concepts and Methods of Iterative 623
Algorithms
14.1 Definitions and qualitative 624
properties of iterated functions
14.1.1 Basic theorems of iterated 626
functions
14.1.2 Illustration of the basic theorems 627
14.2 Contraction mappings 629
14.3 Rates of convergence for iterative 631
algorithms
14.4 Newton's method 632
14.5 Steepest descent 637
14.5.1 Comparison and discussion: Other 642
techniques
Some Applications of Basic Iterative Methods
14.6 LMS adaptive Filtering 643
14.6.1 An example LMS application 645
14.6.2 Convergence of the LMS algorithm 646
14.7 Neural networks 648
14.7.1 The backpropagation training 650
algorithm
14.7.2 The nonlinearity function 653
14.7.3 The forward-backward training 654
algorithm
14.7.4 Adding a momentum term 654
14.7.5 Neural network code 655
14.7.6 How many neurons? 658
14.7.7 Pattern recognition: ML or NN? 659
14.8 Blind source separation 660
14.8.1 A bit of information theory 660
14.8.2 Applications to source separation 662
14.8.3 Implementation aspects 664
14.9 Exercises 665
14.10 References 668
15 Iteration by Composition of Mappings 670
15.1 Introduction 670
15.2 Alternating projections 671
15.2.1 An applications: bandlimited 675
reconstruction
15.3 Composite mappings 676
15.4 Closed mappings and the global 677
convergence theorem
15.5 The composite mapping algorithm 680
15.5.1 Bandlimited reconstruction, 681
revisited
15.5.2 An example: Positive sequence 681
determination
15.5.3 Matrix property mappings 683
15.6 Projection on convex sets 689
15.7 Exercises 693
15.8 References 694
16 Other Iterative Algorithms 695
16.1 Clustering 695
16.1.1 An example application: Vector 695
quantization
16.1.2 An example application: Pattern 697
recognition
16.1.3 k -means Clustering 698
16.1.4 Clustering using fuzzy k-means 700
16.2 Iterative methods for computing 701
inverses of matrices
16.2.1 The Jacobi method 702
16.2.2 Gauss-Seidel iteration 703
16.2.3 Successive over-relaxation (SOR) 705
16.3 Algebraic reconstruction techniques 706
16.4 Conjugate-direction methods 708
16.5 Conjugate-gradient method 710
16.6 Nonquadratic problems 713
16.7 Exercises 713
16.8 References 715
17 The EM Algorithm in Signal Processing 717
17.1 An introductory example 718
17.2 General statement of the EM algorithm 721
17.3 Convergence of the EM algorithm 723
17.3.1 Convergence rate: Some 724
generalizations
Example applications of the EM algorithm
17.4 Introductory example, revisited 725
17.5 Emission computed tomography (ECT) 725
image reconstruction
17.6 Active noise cancellation (ANC) 729
17.7 Hidden Markov models 732
17.7.1 The E- and M-steps 734
17.7.2 The forward and backward 735
probabilities
17.7.3 Discrete output densities 736
17.7.4 Gaussian output densities 736
17.7.5 Normalization 737
17.7.6 Algorithms for HMMs 738
17.8 Spread-spectrum, multiuser 740
communication
17.9 Summary 743
17.10 Exercises 744
17.11 References 747
V Methods of Optimization 749
18 Theory of Constrained Optimization 751
18.1 Basic definitions 751
18.2 Generalization of the chain rule to 755
composite functions
18.3 Definitions for constrained 757
optimization
18.4 Equality constraints: Lagrange 758
multipliers
18.4.1 Examples of equality-constrained 764
optimization
18.5 Second-order conditions 767
18.6 Interpretation of the Lagrange 770
multipliers
18.7 Complex constraints 773
18.8 Duality in optimization 773
18.9 Inequality constraints: Kuhn-Tucker 777
conditions
18.9.1 Second-order conditions for 783
inequality constraints
18.9.2 An extension: Fritz John 783
conditions
18.10 Exercises 784
18.11 References 786
19 Shortest-Path Algorithms and Dynamic 787
Programming
19.1 Definitions for graphs 787
19.2 Dynamic programming 789
19.3 The Viterbi algorithm 791
19.4 Code for the Viterbi algorithm 795
19.4.1 Related algorithms: Dijkstra's 798
and Warshall's
19.4.2 Complexity comparisons of Viterbi 799
and Dijkstra
Applications of path search algorithms
19.5 Maximum-likelihood sequence estimation 800
19.5.1 The intersymbol interference 800
(ISI) channel
19.5.2 Code-division multiple access 804
19.5.3 Convolutional decoding 806
19.6 HMM likelihood analysis and HMM 808
training
19.6.1 Dynamic warping 811
19.7 Alternatives to shortest-path 813
algorithms
19.8 Exercises 815
19.9 References 817
20 Linear Programming 818
20.1 Introduction to linear programming 818
20.2 Putting a problem into standard form 819
20.2.1 Inequality constraints and slack 819
variables
20.2.2 Free variables 820
20.2.3 Variable-bound constraints 822
20.2.4 Absolute value in the objective 823
20.3 Simple examples of linear programming 823
20.4 Computation of the linear programming 824
solution
20.4.1 Basic variables 824
20.4.2 Pivoting 826
20.4.3 Selecting variables on which to 828
pivot
20.4.4 The effect of pivoting on the 829
value of the problem
20.4.5 Summary of the simplex algorithm 830
20.4.6 Finding the initial basic 831
feasible solution
20.4.7 MATLAB(R) code for linear 834
programming
20.4.8 Matrix notation for the simplex 835
algorithm
20.5 Dual problems 836
20.6 Karmarker's algorithm for LP 838
20.6.1 Conversion to Karmarker standard 842
form
20.6.2 Convergence of the algorithm 844
20.6.3 Summary and extensions 846
Examples and applications of linear programming
20.7 Linear-phase FIR filter design 846
20.7.1 Least-absolute-error approximation 847
20.8 Linear optimal control 849
20.9 Exercises 850
20.10 References 853
A Basic Concepts and Definitions 855
A.1 Set theory and notation 855
A.2 Mappings and functions 859
A.3 Convex functions 860
A.4 O and o Notation 861
A.5 Continuity 862
A.6 Differentiation 864
A.6.1 Differentiation with a single real 864
variable
A.6.2 Partial derivatives and gradients 865
on R^
A.6.3 Linear approximation using the 867
gradient
A.6.4 Taylor series 868
A.7 Basic constrained optimization 869
A.8 The Holder and Minkowski inequalities 870
A.9 Exercises 871
A.10 References 876
B Completing the Square 877
B.1 The scalar case 877
B.2 The matrix case 879
B.3 Exercises 879
C Basic Matrix Concepts 880
C.1 Notational conventions 880
C.2 Matrix Identity and Inverse 882
C.3 Transpose and trace 883
C.4 Block (partitioned) matrices 885
C.5 Determinants 885
C.5.1 Basic properties of determinants 885
C.5.2 Formulas for the determinant 887
C.5.3 Determinants and matrix inverses 889
C.6 Exercises 889
C.7 References 890
D Random Processes 891
D.1 Definitions of means and correlations 891
D.2 Stationarity 892
D.3 Power spectral-density functions 893
D.4 Linear systems with stochastic inputs 894
D.4.1 Continuous-time signals and systems 894
D.4.2 Discrete-time signals and systems 895
D.5 References 895
E Derivatives and Gradients 896
E.1 Derivatives of vectors and scalars 896
with respect to a real vector
E.1.1 Some important gradients 897
E.2 Derivatives of real-valued functions 899
of real matrices
E.3 Derivatives of matrices with respect 901
to scalars, and vice versa
E.4 The transformation principle 903
E.5 Derivatives of products of matrices 903
E.6 Derivatives of powers of a matrix 904
E.7 Derivatives involving the trace 906
E.8 Modifications for derivatives of 908
complex vectors and matrices
E.9 Exercises 910
E.10 References 912
F Conditional Expectations of Multinomial 913
and Poisson r.v.s
F.1 Multinomial distributions 913
F.2 Poisson random variables 914
F.3 Exercises 914
Bibliography 915
Index 929</body>
</html>
Caractéristiques techniques
| PAPIER | |
| Éditeur(s) | Prentice Hall |
| Auteur(s) | Todd K. Moon, Wynn C. Stirling |
| Parution | 01/07/1999 |
| Nb. de pages | 937 |
| Format | 20,5 x 26 |
| Couverture | Relié |
| Poids | 1953g |
| Intérieur | Noir et Blanc |
| EAN13 | 9780201361865 |
Avantages Eyrolles.com
Nos clients ont également acheté
Consultez aussi
- Les meilleures ventes en Graphisme & Photo
- Les meilleures ventes en Informatique
- Les meilleures ventes en Construction
- Les meilleures ventes en Entreprise & Droit
- Les meilleures ventes en Sciences
- Les meilleures ventes en Littérature
- Les meilleures ventes en Arts & Loisirs
- Les meilleures ventes en Vie pratique
- Les meilleures ventes en Voyage et Tourisme
- Les meilleures ventes en BD et Jeunesse