The present textbook describes mathematical concepts and results that are of importance in the design, analysis, and optimization of signal processing algorithms, modern communication systems, and networks. This textbook is intended to offer a comprehensive overview of all the necessary concepts and results from linear algebra, numerical analysis, statistics, probability, stochastic processes, and optimization in order to give students and specialists easy access to the state-of-the-art literature and mastering of the key techniques and results in the above-mentioned areas.
This textbook consists of 20 chapters ordered in such a manner that all the necessary background and prerequisite information is presented before more advanced topics are addressed. At the same time, all the efforts have been taken to make each chapter self-contained and as much as possible independent with respect to the other chapters. Each chapter is accompanied by a set of homework exercises and presents pointers to further readings for additional topics and applications.
Chapter 2 of this textbook presents a brief overview of the fundamental transforms used for processing analog and discrete-time signals such as Fourier, Laplace, Z-transform, Hilbert, Hartley, discrete sine and cosine transforms, and sampling. The Sampling Theorem and aliasing errors introduced by sampling analog signals are also described.
Chapter 3 of the book provides a compressed summary of the broad field of linear algebra and matrix theory. Concepts such as vector space, vector norm, normed vector space, linear transformation, orthogonal projection, and Gramm-Schmidt orthogonalization are first described. This chapter also presents an overview of the most important concepts and factorizations from the field of matrix theory. Concepts such as condition number, eigenvalue, eigenvector, determinant, pseudoinverse, special types of matrices (circulant, Toeplitz, Hankel, Vandermonde, stochastic, positive and negative definite), condition number, and matrix factorizations (LU, singular value decomposition (SVD), QR, Cholesky) are described. This chapter ends by presenting various matrix operations such as Kronecker product, Hadamard product, dot (inner) product, direct sum and rules for differentiation of matrix and vector valued functions.
Chapter 4 of this textbook presents a compact description of the Galois field of numbers from the viewpoint of coding and cryptography theory. The chapter introduces first the concepts of group, ring and fields, and then focuses on construction of finite (Galois) fields and potential applications of Galois fields.
Chapter 5 introduces basic concepts in numerical analysis: fixed and floating point representation of numbers, condition number, error propagation, interpolation, determining the roots of polynomials, and numerical procedures for finding roots of nonlinear equations, eigenvalues, and singular values of matrices.
Chapter 6 presents an incursion into the three main branches of combinatorics: enumeration, graph theory, and design theory. Basic enumeration principles such as permutations, combinations, the principle of inclusion and exclusion, generating functions and recurrence relations are presented and their usage is illustrated by numerous examples and applications. Fundamental concepts and results from the field of graph theory such as path, cycle, tree, Eulerian path, and Hamiltonian cycle are presented too. Finally, combinatorial designs are studied for designing and analyzing experiments.
Chapter 7 covers the main concepts and results from the fields of probabilities, random variables, and stochastic processes. The major types of probability distributions and convergence laws for sequences of random variables are reviewed. The law of large numbers (LLN) and central limit theorem (CLT), and their applications in signal processing, telecommunications, and networking are briefly presented. In the realm of stationary stochastic processes, special emphasis is put on concepts such as power spectral density, correlation, Markov chain, and hidden Markov model (HMM).
Chapter 8 is devoted to the study of matrix-valued random variables, and especially to the study and applications of the asymptotic distribution of the eigenvalues of matrices whose entries as normally distributed and whose dimensions grow without limit. Applications in spectral analysis, statistical inference, hypotheses testing, and parameter estimation in large dimensional systems are presented.
Chapter 9 is dedicated to the large deviation theory, i.e., the study of occurrence of rare events. This chapter represents a short introduction to the basic large deviation concepts and techniques including concentration inequalities, rate function, Cramer’s theorem, type analysis, and Sanov’s theorem. Determination of the error exponents of several standard hypothesis testing methods is presented as an application of large deviation theory.
Chapter 10 and Chapter 11 cover the fundamentals of estimation and detection theories, respectively. Chapter 10 presents first the concept of Cramer-Rao bound and several approaches for finding minimum variance unbiased estimators such as the method based on Rao-Blackwell-Lehmann-Scheffe theorem and the estimation technique that exploits the concept of sufficient statistics. Properties of maximum likelihood estimator are then reviewed. Various forms of least squares estimation techniques such as recursive least squares (RLS), weighted least squares, constrained least squares and regularized least squares are also presented. Chapter 10 ends with the description of Bayesian estimation techniques. Chapter 11 starts with a general formulation of a detection problem as a statistical decision problem. Three fundamental approaches for binary detection applications are considered: Bayesian, minimax, and Neyman-Pearson. The likelihood ratio test (LRT), uniformly most powerful (UMP), generalized likelihood ratio (GLR), and locally most powerful (LMP) detection scheme are also discussed.
Chapter 12 discusses the usage of Monte Carlo simulation techniques in solving various problems in the areas of signal processing, wireless communications, and bioinformatics. General features and some applications of Markov chain Monte Carlo (MCMC) and sequential Monte Carlo (SMC) techniques are presented.
Chapter 13 is dedicated to the general problem of statistical inference in graphs. The main focus is on factor graphs and message passing algorithms. Basic concepts regarding factor graphs and their construction are first presented. Common features of factor graphs with random fields and Bayesian networks are also described. The message passing algorithm, and in particular the sum-product and the max-product algorithms, for inference in factor graphs are presented. Various algorithms such as BCJR, Viterbi algorithm, Kalman filtering, and EM algorithm are described as instances of message passing in factor graphs. The chapter ends with an application of sum-product algorithm to the carrier frequency offset synchronization of an orthogonal frequency division multiplexing (OFDM) system.
Chapter 14 presents an overview of the basic mathematical approaches for solving constrained and unconstrained optimization problems. The chapter first reviews basic concepts in convex analysis, and then establishes optimality conditions for determining the solutions of unconstrained and constrained optimization problems. In particular, Karush-Kuhn-Tucker (KKT) conditions, Lagrangian duality and applications to several wireless communications systems designs are discussed.
Chapter 15 focuses on optimization problems that assume a linear criterion as well as linear constraints. Such optimization problems are efficiently solved in practice using linear programming and mixed integer programming techniques. This chapter provides an introduction into the basic theory and the main algorithmic approaches that fall under the umbrella of linear programming and mixed integer programming techniques. A few typical signal processing problems that could be resolved using standard linear programming and mixed integer programming techniques are also presented.
Chapter 16 provides a summary of basic results and applications of majorization theory. Basic concepts, such as Schur-convexity, multiplicative majorization, Schur inequality, T-transform, and stochastic majorization, are described. Numerous applications of majorization theory in the design of wireless communications transceivers are presented as well.
Chapter 17 presents basic concepts and results from queueing theory, with special emphasis on the simple M/M/1 queue and the intermediate M/G/1 queue.
Chapter 18 focuses on modeling and optimization techniques for communication network design and planning. The main focus of Chapter 18 is on optimization of the capacity of network resources and traffic routing. The link capacity and routing modeling are formulated in terms of multicommodity flow networks (MFN), and integer programming techniques are proposed for optimization of multicommodity flow networks.
Chapter 19 presents the basic concepts and results from game theory: non-cooperative games, Nash equilibrium, cooperative games, games with incomplete information, repeated games, as well as a discussion of main applications of game theory to signal processing, communications, and networking.
Finally, Chapter 20 provides a short introduction into the theory of frames. Applications of frame theory to the sampling of analog signals and their reconstruction from discrete-time samples are presented. Important classes of frames such as wavelets and Weyl-Heisenberg frames are also presented.