Mathematical methods and algorithms for signal processing / Todd K. Moon, Wynn C. Stirling.

Format:

Book

Author/Creator:

Moon, Todd K.

Contributor:

Stirling, Wynn C.

Sabin W. Colton, Jr., Memorial Fund.

Language:

English

Subjects (All):

Signal processing--Mathematics.

Signal processing.

Algorithms.

Physical Description:

xxxvi, 937 pages : illustrations ; 27 cm + 1 computer optical disc (4 3/4 in.)

Place of Publication:

Upper Saddle River, N.J. : Prentice Hall, [2000]

Summary:

"Mathematical Methods and Algorithms for Signal Processing tackles the challenge many students and practitioners face in the field of signal processing - how to deal with the breadth of mathematical topics employed in the subject. This text provides a solid foundation of theoretical and practical tools that will serve a broad range of signal processing applications. Linear algebra, statistical signal processing, iterative algorithms, and optimization are thoroughly treated, with signal processing examples throughout. Students, practising engineers, and researchers will find Mathematical Methods and Algorithms for Signal Processing useful as a textbook and as a reference."--BOOK JACKET.

Contents:

1.1 What is signal processing? 3

1.2 Mathematical topics embraced by signal processing 5

1.3 Mathematical models 6

1.4 Models for linear systems and signals 7

1.5 Adaptive filtering 28

1.6 Gaussian random variables and random processes 31

1.7 Markov and Hidden Markov Models 37

1.8 Some aspects of proofs 41

1.9 An application: LFSRs and Massey's algorithm 48

II Vector Spaces and Linear Algebra 69

2 Signal Spaces 71

2.1 Metric spaces 72

2.2 Vector spaces 84

2.3 Norms and normed vector spaces 93

2.4 Inner products and inner-product spaces 97

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.9 Hilbert and Banach spaces 106

2.10 Orthogonal subspaces 107

2.11 Linear transformations: Range and nullspace 108

2.12 Inner-sum and direct-sum spaces 110

2.13 Projections and orthogonal projections 113

2.14 The projection theorem 116

2.15 Orthogonalization of vectors 118

2.16 Some final technicalities for infinite dimensional spaces 121

3 Representation and Approximation in Vector Spaces 130

3.1 The Approximation problem in Hilbert space 130

3.2 The Orthogonality principle 135

3.3 Error minimization via gradients 137

3.4 Matrix Representations of least-squares problems 138

3.5 Minimum error in Hilbert-space approximations 141

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.10 Minimum mean-square estimation 156

3.11 Minimum mean-squared error (MMSE) filtering 157

3.12 Comparison of least squares and minimum mean squares 161

3.13 Frequency-domain optimal filtering 162

3.14 A dual approximation problem 179

3.15 Minimum-norm solution of underdetermined equations 182

3.16 Iterative Reweighted LS (IRLS) for L[subscript p] optimization 183

3.17 Signal transformation and generalized Fourier series 186

3.18 Sets of complete orthogonal functions 190

3.19 Signals as points: Digital communications 208

4 Linear Operators and Matrix Inverses 229

4.1 Linear operators 230

4.2 Operator norms 232

4.3 Adjoint operators and transposes 237

4.4 Geometry of linear equations 239

4.5 Four fundamental subspaces of a linear operator 242

4.6 Some properties of matrix inverses 247

4.7 Some results on matrix rank 249

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.12 Inverse of a block (partitioned) matrix 264

5 Some Important Matrix Factorizations 275

5.1 The LU factorization 275

5.2 The Cholesky factorization 283

5.3 Unitary matrices and the QR factorization 285

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.4 Geometry of invariant subspaces 316

6.5 Geometry of quadratic forms and the minimax principle 318

6.6 Extremal quadratic forms subject to linear constraints 324

6.7 The Gershgorin circle theorem 324

Application of Eigendecomposition methods

6.8 Karhunen-Loeve low-rank approximations and principal methods 327

6.9 Eigenfilters 330

6.10 Signal subspace techniques 336

6.11 Generalized eigenvalues 340

6.12 Characteristic and minimal polynomials 342

6.13 Moving the eigenvalues around: Introduction to linear control 344

6.14 Noiseless constrained channel capacity 347

6.15 Computation of eigenvalues and eigenvectors 350

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: Effective rank 377

Applications of the SVD

7.6 System identification using the SVD 378

7.7 Total least-squares problems 381

7.8 Partial total least squares 386

7.9 Rotation of subspaces 389

7.10 Computation of the SVD 390

8 Some Special Matrices and Their Applications 396

8.1 Modal matrices and parameter estimation 396

8.2 Permutation matrices 399

8.3 Toeplitz matrices and some applications 400

8.4 Vandermonde matrices 409

8.5 Circulant matrices 410

8.6 Triangular matrices 416

8.7 Properties preserved in matrix products 417

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.3 The vec operator 428

III Detection, Estimation, and Optimal Filtering 435

10 Introduction to Detection and Estimation, and Mathematical Notation 437

10.1 Detection and estimation theory 437

10.2 Some notational conventions 442

10.3 Conditional expectation 444

10.4 Transformations of random variables 445

10.5 Sufficient statistics 446

10.6 Exponential families 453

11 Detection Theory 460

11.1 Introduction to hypothesis testing 460

11.2 Neyman-Pearson theory 462

11.3 Neyman-Pearson testing with composite binary hypotheses 483

11.4 Bayes decision theory 485

11.5 Some M-ary problems 499

11.6 Maximum-likelihood detection 503

11.7 Approximations to detection performance: The union bound 503

11.8 Invariant Tests 504

11.9 Detection in continuous time 512

11.10 Minimax Bayes decisions 520

12 Estimation Theory 542

12.1 The maximum-likelihood principle 542

12.2 ML estimates and sufficiency 547

12.3 Estimation quality 548

12.4 Applications of ML estimation 561

12.5 Bayes estimation theory 568

12.6 Bayes risk 569

12.7 Recursive estimation 580

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 II: The innovations approach 595

13.4 Numerical considerations: Square-root filters 604

13.5 Application in continuous-time systems 606

13.6 Extensions of Kalman filtering to nonlinear systems 607

13.7 Smoothing 613

13.8 Another approach: H[subscript [infinity]] smoothing 616

IV Iterative and Recursive Methods in Signal Processing 621

14 Basic Concepts and Methods of Iterative Algorithms 623

14.1 Definitions and qualitative properties of iterated functions 624

14.2 Contraction mappings 629

14.3 Rates of convergence for iterative algorithms 631

14.4 Newton's method 632

14.5 Steepest descent 637

Some Applications of Basic Iterative Methods

14.6 LMS adaptive Filtering 643

14.7 Neural networks 648

14.8 Blind source separation 660

15 Iteration by Composition of Mappings 670

15.2 Alternating projections 671

15.3 Composite mappings 676

15.4 Closed mappings and the global convergence theorem 677

15.5 The composite mapping algorithm 680

15.6 Projection on convex sets 689

16 Other Iterative Algorithms 695

16.1 Clustering 695

16.2 Iterative methods for computing inverses of matrices 701

16.3 Algebraic reconstruction techniques (ART) 706

16.4 Conjugate-direction methods 708

16.5 Conjugate-gradient method 710

16.6 Nonquadratic problems 713

17 The EM Algorithm in Signal Processing 717

17.2 General statement of the EM algorithm 721

17.3 Convergence of the EM algorithm 723

Example applications of the EM algorithm

17.4 Introductory example, revisited 725

17.5 Emission computed tomography (ECT) image reconstruction 725

17.6 Active noise cancellation (ANC) 729

17.7 Hidden Markov models 732

17.8 Spread-spectrum, multiuser communication 740

V Methods of Optimization 749

18 Theory of Constrained Optimization 751

18.2 Generalization of the chain rule to composite functions 755

18.3 Definitions for constrained optimization 757

18.4 Equality constraints: Lagrange multipliers 758

18.5 Second-order conditions 767

18.6 Interpretation of the Lagrange multipliers 770

18.7 Complex constraints 773

18.8 Duality in optimization 773

18.9 Inequality constraints: Kuhn-Tucker conditions 777

19 Shortest-Path Algorithms and Dynamic Programming 787

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.5 Maximum-likelihood sequence estimation 800

19.6 HMM likelihood analysis and HMM training 808

19.7 Alternatives to shortest-path algorithms 813

20 Linear Programming 818

20.1 Introduction to linear programming 818

20.2 Putting a problem into standard form 819

20.3 Simple examples of linear programming 823

20.4 Computation of the linear programming solution 824

20.5 Dual problems 836

20.6 Karmarker's algorithm for LP 838

Examples and applications of linear programming

20.7 Linear-phase FIR filter design 846

20.8 Linear optimal control 849

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.7 Basic constrained optimization 869

A.8 The Holder and Minkowski inequalities 870

B Completing the Square 877

B.1 The scalar case 877

B.2 The matrix case 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

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

E Derivatives and Gradients 896

E.1 Derivatives of vectors and scalars with respect to a real vector 896

E.2 Derivatives of real-valued functions of real matrices 899

E.3 Derivatives of matrices with respect to scalars, and vice versa 901

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 complex vectors and matrices 908

F Conditional Expectations of Multinomial and Poisson r.v.s 913

F.1 Multinomial distributions 913

F.2 Poisson random variables 914.

Notes:

Includes bibliographical references (pages [915]-928) and index.

Local Notes:

Acquired for the Penn Libraries with assistance from the Sabin W. Colton, Jr., Memorial Fund.

ISBN:

0201361868

OCLC:

41320162