CS6015 - Linear Algebra and Random Processes

Course Data :

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.

Pre-Requisites

    None

Parameters

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

Previous Instances of the Course


© 2016 - All Rights Reserved - Dept of CSE, IIT Madras
Website Credits