book

Mathematical Foundations for Signal Processing, Communications, and Networking

by Erchin Serpedin, Thomas Chen, Dinesh Rajan

December 2017

Intermediate to advanced

858 pages

21h 17m

English

CRC Press

Read now

Unlock full access

Cover
Half Title
Title Page
Copyright Page
Table of Contents
List of Figures
List of Tables
Preface
Editors
List of Contributors

List of Acronyms
Notations and Symbols
1 Introduction
2 Signal Processing Transforms
2.1 Introduction2.2 Basic Transformations2.3 Fourier Series and Transform2.3.1 Basic Definitions2.3.2 Fourier Series2.3.3 Fourier Transform2.4 Sampling2.4.1 Impulse-Train Sampling2.4.2 Aliasing2.5 Cosine and Sine Transforms2.5.1 Cosine Transform2.5.2 Sine Transform2.6 Laplace Transform2.6.1 Properties of Laplace Transform2.7 Hartley Transform2.7.1 Properties of Hartley Transform2.8 Hilbert Transform2.8.1 Properties of Hilbert Transform2.9 Discrete-Time Fourier Transform2.10 The Z-Transform2.10.1 Properties of Z-Transform2.11 Conclusion and Further Reading2.12 ExercisesReferences
3 Linear Algebra
3.1 Vector Spaces3.1.1 Subspaces and Direct Sums3.1.2 Spanning and Linear Independency3.1.3 Bases3.1.4 Dimension3.1.5 Ordered Basis3.1.6 Norms3.1.7 Inner-Products3.1.8 Induced Norms3.1.9 Orthogonality3.1.10 Gram-Schmidt Orthogonalization3.2 Linear Transformations3.2.1 Range and Nullspace of a Linear Transformation3.2.2 Composition and Invertibility3.2.3 Matrix Representation of Linear Transformations3.2.4 Projection Operators3.2.5 Linear Functionals and Dual Spaces3.2.6 Adjoint of a Linear Transformation3.2.7 Four Fundamental Subspaces3.3 Operator Norms and Matrix Norms3.4 Systems of Linear Equations3.5 Determinant, Adjoint, and Inverse of a Matrix3.6 Cramer’s Rule3.7 Unitary and Orthogonal Operators and Matrices3.8 LU Decomposition3.9 LDL and Cholesky Decomposition3.10 QR Decomposition3.11 Householder and Givens Transformations3.11.1 Orthogonal Reduction
3.12 Best Approximations and Orthogonal Projections
3.13 Least Squares Approximations3.14 Angles Between Subspaces3.14.1 Principal Angles Between Subspaces3.15 Eigenvalues and Eigenvectors3.15.1 Diagonalization3.16 Schur Factorization and Spectral Theorem3.17 Singular Value Decomposition (SVD)3.18 Rayleigh Quotient3.19 Application of SVD and Rayleigh Quotient: Principal Component Analysis3.20 Special Matrices3.20.1 Block Matrices3.20.2 Circulant Matrices3.20.3 Toeplitz Matrices3.20.4 Hankel Matrices3.20.5 Vandermonde Matrices3.20.6 Normal Matrices3.20.7 Stochastic Matrices3.20.8 Positive and Negative Definite Matrices3.20.9 Matrix Condition Number3.20.10 Sherman-Morrison-Woodbury Identity3.20.11 Schur Complement3.20.12 Generalized Inverses3.21 Matrix Operations3.21.1 Kronecker Product3.21.2 Hadamard Product3.21.3 Dot Product3.21.4 Direct Sum3.21.5 Differentiation of Matrix and Vector Functions3.22 References and Further Studies3.23 ExercisesReferences
4 Elements of Galois Fields
4.1 Groups, Rings, and Fields4.1.1 Groups4.1.2 Rings4.1.3 Fields4.2 Galois Fields4.3 Polynomials with Coefficients in GF(2)4.4 Construction of GF(2m)4.4.1 Conjugate Elements4.4.2 Factorization of the Polynomial Xn + 14.5 Some Notes on Applications of Finite Fields4.6 ExercisesReferences
5 Numerical Analysis
5.1 Numerical Approximation5.2 Sensitivity and Conditioning5.3 Computer Arithmetic5.4 Interpolation5.4.1 Polynomial Interpolation5.4.2 Piecewise Polynomial Interpolation5.5 Nonlinear Equations5.5.1 Interval Bisection5.5.2 Newton’s Method5.5.3 Secant Method5.5.4 Muller’s Method5.5.5 Linear Fractional Interpolation5.5.6 Zeros of Polynomials5.6 Eigenvalues and Singular Values5.6.1 Power Iterations5.6.2 QR Algorithm5.6.3 Computing Singular Values5.7 Further Reading5.8 Exercises
References
6 Combinatorics
6.1 Two Principles of Enumeration6.2 Permutations and Combinations6.3 The Principle of Inclusion and Exclusion6.4 Generating Functions6.5 Recurrence Relations6.6 Graphs6.7 Paths and Cycles in Graphs6.8 Trees6.9 Encoding and Decoding6.10 Latin Squares6.11 Balanced Incomplete Block Designs6.12 Conclusion6.13 ExercisesReferences
7 Probability, Random Variables, and Stochastic Processes
7.1 Introduction to Probability7.2 Random Variables7.2.1 Discrete Random Variables7.2.2 Continuous Random Variables7.3 Joint Random Variables7.3.1 Expected Values, Characteristic Functions
7.3.2 Inequalities
7.3.3 Functions of Multiple Random Variables7.3.4 Convergence of Random Variables7.3.5 Law of Large Numbers (LLN) and Central Limit Theorem (CLT)7.4 Random Processes7.4.1 Stationary Process7.4.2 Random Process as the Input to a Linear System7.5 Markov Process7.5.1 Markov Chains7.5.2 Continuous Time Markov Chains7.5.3 Hidden Markov Model7.6 Summary and Further Reading7.7 ExercisesReferences
8 Random Matrix Theory
8.1 Probability Notations8.2 Spectral Distribution of Random Matrices8.2.1 Wishart Matrices8.2.2 Limiting Spectral Distribution8.3 Spectral Analysis8.3.1 Exact Eigenvalue Separation8.3.2 Support of l.s.d.8.4 Statistical Inference8.5 Applications8.5.1 Binary Hypothesis Testing
8.5.2 Parameter Estimation
8.6 Conclusion8.7 ExercisesReferences
9 Large Deviations
9.1 Introduction9.2 Concentration Inequalities9.3 Rate Function9.4 Cramér’s Theorem9.5 Method of Types9.6 Sanov’s Theorem9.7 Hypothesis Testing9.8 Further Readings9.9 ExercisesReferences
10 Fundamentals of Estimation Theory
10.1 Introduction10.2 Bound on Minimum Variance – Cramér-Rao Lower Bound10.2.1 Computation of CRLB10.2.2 Finding MVUE Attaining the CRLB10.3 MVUE Using RBLS Theorem10.3.1 Sufficient Statistics10.3.2 Finding MVUE from Sufficient Statistics10.4 Maximum Likelihood Estimation10.4.1 ML Estimation Principle10.4.2 Properties of the ML Estimator
10.5 Least Squares Estimation
10.5.1 Geometrical Interpretation10.5.2 Recursive LS Estimation10.5.3 Weighted LS and Iterative Reweighted LS10.5.4 Constrained LS Estimation10.6 Regularized LS Estimation10.6.1 ℓ2 Regularization10.6.2 LS Estimation with Quadratic Constraint10.6.3 ℓ1 Regularization10.7 Bayesian Estimation10.7.1 Minimum Mean Square Error Estimation10.7.2 General Bayesian Estimator10.7.3 Handling Nuisance Parameters10.8 References and Further Reading10.9 ExercisesReferences
11 Fundamentals of Detection Theory
11.1 Introduction11.1.1 Statistical Decision Theory Framework11.1.2 Probabilistic Structure for Observation Space11.1.3 Conditional Density and Conditional Risk11.1.4 Bayesian Approach11.1.5 Minimax Approach11.1.6 Randomized Decision Rules11.1.7 General Method for Finding Bayes Rules11.2 Bayesian Binary Detection11.2.1 Likelihood Ratio Test11.2.2 Uniform Costs11.2.3 Examples11.3 Binary Minimax Detection11.3.1 Bayes Risk Line and Minimum Risk Curve11.3.2 Equalizer Rule11.3.3 Examples11.4 Binary Neyman-Pearson Detection11.4.1 Solution to the N-P Optimization Problem11.4.2 N-P Rule and Receiver Operating Characteristic11.4.3 Examples11.5 Bayesian Composite Detection11.6 Neyman-Pearson Composite Detection11.6.1 UMP Detection with One Composite Hypothesis
11.6.2 UMP Detection with Both Composite Hypotheses
11.6.3 Generalized Likelihood Ratio (GLR) Detection11.6.4 Locally Most Powerful (LMP) Detection11.7 Binary Detection with Vector Observations11.7.1 Conditionally Independent Observations11.7.2 Deterministic Signals in Correlated Gaussian Noise11.7.3 Gaussian Signals in Gaussian Noise11.8 Summary and Further Reading11.9 ExercisesReferences
12 Monte Carlo Methods for Statistical Signal Processing
12.1 Introduction12.1.1 Model-Based Signal Processing12.1.2 Examples12.2 Monte Carlo Methods12.3 Markov Chain Monte Carlo (MCMC) Methods12.3.1 General MCMC Algorithms12.3.2 Applications of MCMC in Digital Communications12.4 Sequential Monte Carlo (SMC) Methods12.4.1 General SMC Algorithms12.4.2 Resampling Procedures12.4.3 Applications of SMC in Bioinformatics12.5 Conclusions and Further Readings12.6 ExercisesReferences
13 Factor Graphs and Message Passing Algorithms
13.1 Introduction13.1.1 Why Factor Graphs?13.1.2 Literature Survey13.1.3 Organization of the Chapter13.2 Factor Graphs13.3 Modeling Systems Using Factor Graphs13.3.1 Behavioral Modeling13.3.2 Probabilistic Modeling13.4 Relationship with Other Probabilistic Graphical Models13.4.1 Markov Random Fields13.4.2 Bayesian Networks13.5 Message Passing in Factor Graphs13.5.1 Sum-Product Algorithm13.5.2 Max-Product Algorithm13.6 Factor Graphs with Cycles13.6.1 Message Passing Schedules13.6.2 Iterative Message Passing13.7 Some General Remarks on Factor Graphs13.7.1 Mappers13.7.2 Hybrid Equality Constraint13.7.3 Quantizers13.7.4 Continuous Variables13.8 Some Important Message Passing Algorithms13.8.1 Forward/Backward Algorithm13.8.2 The Viterbi Algorithm13.8.3 Kalman Filter13.8.4 Expectation Maximization (EM) Algorithm13.9 Applications of Message Passing in Factor Graphs13.9.1 Detection of OFDM Signals in the Presence of Carrier Frequency Offset and Phase Noise13.10 ExercisesReferences
14 Unconstrained and Constrained Optimization Problems
14.1 Basics of Convex Analysis14.2 Unconstrained vs. Constrained Optimization14.2.1 Optimality Conditions for Unconstrained Optimization14.2.2 Optimality Conditions for Constrained Optimization14.2.3 Lagrangian Duality14.3 Application Examples14.4 ExercisesReferences
15 Linear Programming and Mixed Integer Programming
15.1 Linear Programming15.1.1 General Presentation15.1.2 Transformations of the Standard Problem15.1.3 Optimality Characterization15.1.4 Duality Aspects15.1.5 The Simplex Method15.1.6 Interior-Point Methods15.2 Modeling Problems via Linear Programming15.2.1 Optimization with 1-norm and ∞-norm15.2.2 Chebyshev Center of a Polytope15.2.3 Classification with Separating Hyperplanes15.2.4 Linear Fractional Programming15.2.5 Continuous Constraints and Discretization15.3 Mixed Integer Programming15.3.1 Problem Statement and LP Relaxation15.3.2 Branch and Bound15.3.3 Examples of Mixed Integer Problems15.4 Historical Notes and Further Reading15.5 ExercisesReferences
16 Majorization Theory and Applications
16.1 Majorization Theory16.1.1 Basic Concepts16.1.2 Schur-Convex/Concave Functions16.1.3 Relation to Matrix Theory16.1.4 Multiplicative Majorization16.1.5 Stochastic Majorization16.2 Applications of Majorization Theory16.2.1 CDMA Sequence Design16.2.2 Linear MIMO Transceiver Design16.2.3 Nonlinear MIMO Transceiver Design16.2.4 Impact of Correlation16.2.5 Robust Design16.3 Conclusions and Further Readings16.4 ExercisesReferences
17 Queueing Theory
17.1 Introduction17.2 Markov Chains17.2.1 Discrete-Time Markov Chains17.2.2 Continuous-Time Markov Chains17.3 Queueing Models17.4 M/M/1 Queue17.4.1 Steady-State Probabilities for Number in System17.4.2 Little’s Formula17.4.3 Probability Distribution of Delay Through System17.5 M/M/1/N Queue17.5.1 Example: Queueing Model of a Packet Switch17.6 M/M/N/N Queue17.7 M/M/1 Queues in Tandem17.7.1 Product Form17.7.2 Jackson Networks17.8 M/G/1 Queue17.8.1 Embedded Markov Chain17.8.2 Mean Number in System17.8.3 Distribution of Number in System17.8.4 Mean Delay Through System17.8.5 Distribution of Delay Through System17.8.6 Example: Mixed Packets17.8.7 Example: Data Frame Retransmissions17.9 Conclusions17.10 ExercisesReferences
18 Network Optimization Techniques
18.1 Introduction18.2 Basic Multicommodity Flow Networks Optimization Models18.2.1 Notions and Notations18.2.2 Link-Path vs. Node-Link Formulation Applied to Allocation Problems18.2.3 Dimensioning Problems18.3 Optimization Methods for Multicommodity Flow Networks18.3.1 Decomposition Methods18.3.2 Solving MIP Problems
18.3.3 Heuristic Approaches
18.4 Optimization Models for Multistate Networks18.4.1 Protection Models18.4.2 Restoration Models18.4.3 Multihour and Multiperiod Design18.5 Concluding Remarks18.6 ExercisesReferences
19 Game Theory
19.1 Introduction19.2 Utility Theory19.3 Games on the Normal Form19.3.1 Zero-Sum Games19.3.2 Non-Zero-Sum Games19.4 Noncooperative Games and the Nash Equilibrium19.5 Cooperative Games19.5.1 Bargaining without Transferable Utilities19.5.2 Bargaining with Transferable Utilities19.6 Games with Incomplete Information19.7 Extensive Form Games19.7.1 Nash Equilibrium in Extensive Form Games19.7.2 Subgame-Perfect Equilibrium19.7.3 Incomplete Information in Extensive Form Games19.8 Repeated Games and Evolutionary Stability19.8.1 Repeated Games19.8.2 Evolutionary Game Theory19.9 Coalitional Form/Characteristic Function Form19.9.1 The Core19.9.2 The Kernel19.9.3 The Nucleolus19.9.4 The Shapley Value19.10 Mechanism Design and Implementation Theory19.10.1 Social Choice19.10.2 Auctions19.10.3 Direct Revelation Principle19.10.4 Clarke-Groves and AGV-Arrow Mechanism19.11 Applications to Signal Processing and Communications19.12 Acknowledgments19.13 ExercisesReferences
20 A Short Course on Frame Theory
20.1 Examples of Signal Expansions20.2 Signal Expansions in Finite-Dimensional Spaces20.2.1 Orthonormal Bases20.2.2 General Bases20.2.3 Redundant Signal Expansions20.3 Frames for General Hilbert Spaces20.3.1 The Frame Operator20.3.2 The Canonical Dual Frame20.3.3 Signal Expansions
20.3.4 Tight Frames
20.3.5 Exact Frames and Biorthonormality20.4 The Sampling Theorem20.4.1 Sampling Theorem as a Frame Expansion20.4.2 Design Freedom in Oversampled A/D Conversion20.4.3 Noise Reduction in Oversampled A/D Conversion20.5 Important Classes of Frames20.5.1 Weyl-Heisenberg Frames20.5.2 Wavelets20.6 ExercisesReferences
Index

Content preview from Mathematical Foundations for Signal Processing, Communications, and Networking

Chapter 15 Linear Programming and Mixed Integer Programming

Bogdan Dumitrescu^‡

‡ Tampere University of Technology, Finland

Linear programming (LP) is the class of optimization problems whose criterion and constraints are linear. Such problems appeared first in economy, for example in activity planning or resource allocation, but are now ubiquitous also in engineering. Although being apparently the simplest type of optimization problem that has no analytic solution, LP has interesting properties and its study has led to significant developments and generalizations for the whole optimization field, both in terms of theory and algorithms.

Mixed integer programming (MIP) problems also have linear criterion and constraints, but some of their variables ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

The Physics and Mathematics of Electromagnetic Wave Propagation in Cellular Wireless Communication

Publisher Resources

ISBN: 9781439855140

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

Mathematical Foundations for Signal Processing, Communications, and Networking

by Erchin Serpedin, Thomas Chen, Dinesh Rajan

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.