CS6015 - Linear Algebra and Random Processes

#### Course Syllabus

• Linear Algebra : Basic Topics: Fields, Vector Spaces, Basis, Subspaces. (1 week)
• Matrices: Matrices and Linear Transformations, Rank, Determinant (as a measure of volume of the space enclosed by the rows/columns of a matrix), trace of a matrix. Solving simultaneous equations using matrices: Gaussian Elimination. Overdetermined and underdetermine systems, Inverse, pseudo inverse. Condition number of a matrix, eigenvalues, eigenvectors, singular values, singular vectors. Computation of eigenvalues and eigen vectors (physical significance of eigen vectors and singular vectors � e.g image as a matrix). Eigen vectors of a symmetric positive definite matrix and its meaning. Diagonalization of a matrix and applications. Derivatives of scalars w.r.t a vector. Jacobian (4 weeks)
Short Exam on LA, Programming Assignment on Eigen/Singular values and vectors. e.g. image analysis and reconstruction using eigen decomposition.
• Orthogonality : Inner Product, Orthogonality, Gram-Schmidt Orthogonalization, Vector and Matrix Norms - Applications to optimization problems and graph theory, machine learning. (1 week)
• Probability and Random Processes: Basic Topics (recap) : Sample points and Sample spaces: Events, algebra of events, partitions, Bayes theorem, probability axioms, joint and conditional probability. (1 week)
Short Exam and written assignment on basics. Introduction to random variables and random vectors: Discrete and continuous random variables, random vectors. Transformation of continuous random variables and vectors by deterministic functions. Density functions of transformed continuous random variables and vectors (Jacobian). (2 weeks).
• Introduction to Random Processes: Statistical averages, ensemble and time averages. Random process (definition), Bernoulli random process, binomial process, sine wave process. Weak and strict sense stationarity of a random process. Ergodicity. Autocorrelation and Autocovariance functions of random processes, ACF and its relation to spectra (if time permits). Auto covariance matrix , properties of the autocovariance matrix. PCA/Eigen analysis of the ACF. Poisson process (application to arrival times, interarrival times etc.), Gaussian process, Martingale model and Markov Chains. Estimation of parameters from data: method of moments, method of maximum likelihood. Tests of fit: Chi-Squared, Student-t test, normality test. Cramer-Rao bound on estimators. Comparison of two different distributions of the same random variable/vector, Kullback Leibler divergence. (6 weeks)
Programming Assignments: (1) Eigen analysis of covariance matrix of sample data (2-D) generated from synthetic unimodal Gaussian distributions. (2) Generation of a random process from a given distribution, estimation of parameters, performing tests of fit.
• Tail Inequalities - Chernoff Bound, Chebyshev inequality, Azuma Hoeffding and Isoperimetric inequalities. Applications. (1 week)

#### Text Books:

• Linear Algebra and Its Applications - Gilbert Strang- Fourth Edition- Cengage Learning, 2006.
• Probability, Random Variables and Stochastic Processes, Papoulis and Unnikrishnan, Fourth Edition, 2002, available in paperback.
• Probability and Random Processes - an introduction for application scientists and engineers, W B Davenport, 1970, McGraw Hill.

#### Reference Books

• Probability and Statistics with Reliability, Queuing, and Computer Science Applications - Kishore S Trivedi, PHI.
• Linear Algebra (second edition )- Kenneth Hoffman and Ray Kunze, Prentice Hall India, 2013.
• Linear Algebra (Second Edition) - Cheney and Kincaid, Jones and Bartlett learning, 2014

#### Learning Outcomes:

• Be able to Identify and Comprehend linear algebraic structures that appear in various areas of computer science.
• Use linear algebraic methods to perform computational tasks.
• Identify and Apply properties of eigenvalues and orthogonality to analyze computational problems.
• Define and Apply various concepts of probability theory.
• Comprehend and Use the properties of random processes in real world situations.
• Identify and Set up relevant random experiments to apply tail inequalities.

None

#### Parameters

 Credits Type Date of Introduction 3-1-0-0-8-12 Core Jul 2015