CS6015: Linear Algebra and Random Processes

Course information

 Instructor Prashanth Wednesday 2:30pm to 3:30pm BSB 314 TAs Abhishek Monday 2:30pm to 3:30pm DON lab Hardi Tuesday 2:30pm to 3:30pm DON lab Ditty Wednesday 2:30pm to 3:30pm AIDB lab Jom Thursday 2:30pm to 3:30pm DON lab Purvi Friday 2:30pm to 3:30pm DON lab

Course Content

Linear Algebra

Matrices

Matrix Multiplication, Transposes, Inverses, Gaussian Elimination, factorization A=LU, rank

Vector spaces

Column and row spaces, Solving Ax=0 and Ax=b, Independence, basis, dimension, linear transformations

Orthogonality

Orthogonal vectors and subspaces, projection and least squares, Gram-Schmidt orthogonalization

Determinants

Determinant formula, cofactors, inverses and volume

Eigenvalues and Eigenvectors

Characteristic polynomial, Diagonalization, Hermitian and Unitary matrices, Spectral theorem, Change of basis

Positive definite matrices and singular value decomposition

Random processes

Preliminaries

Events, probability, conditional probability, independence, product spaces

Random Variables

Distributions, law of averages, discrete and continuous r.v.s, random vectors, Monte Carlo simulation

Discrete Random Variables

Probability mass functions, independence, expectation, conditional expectation, sums of r.v.s

Continuous Random Variables

Probability density functions, independence, expectation, conditional expectation, functions of r.v.s, sum of r.v.s, multivariate normal distribution, sampling from a distribution

Convergence of Random Variables

Modes of convergence, Borel-Cantelli lemmas, laws of large numbers, central limit theorem, tail inequalities

* Advanced topics (if time permits)

Markov chains, minimum mean squared error estimation

• Mid-term (Linear Algebra concepts): 30%

• Final exam (Probability concepts): 30%

• Quizzes: 20% (Best 5 out of 8)

• Programming Assignments: 20%

Target Audience

Masters (M.Tech/M.S.) and Ph.D. students

Important Dates

Problem Sets Quizzes Tutorials Mid-Sem End-Sem
Aug 7 Aug 16 Aug 11 When: 10am to 12pm, Sep 24      Where: CS34 and CS36 When: 1pm to 4pm, Nov 15      Where: CS34 and CS36
Aug 18 Aug 28 Sep 1
Aug 25 28 Sep 5 Sep 20
Sep 11 Sep 18 Oct 13
Sep 28 Oct 6 Oct 23
Oct 10 Oct 17 Nov 10
Oct 20 Oct 27
Oct 27 Nov 3

Textbooks

• Linear algebra and applications by Gilbert Strang

• Probability and random processes by Geoffrey Grimmett and David Stirzaker

Schedule

Lecture number Topics Covered Section reference (Strang's book) Part I: Linear Algebra Lecture 1 Course Organization Motivation for studying linear algebra Lecture 2 Geometry of linear equations - row picture, col picture Vector space, subspace - definition, examples Linear combinations, linear independence 1.2 Lecture 3 Transpose - properties Inverse Gaussian elimination 1.3 Lecture 4 Computational cost of elimination Matrix multiplication - four view Gauss-Jordan method 1.4 Lecture 5 Factorization A=LU and A=LDU Row exchanges, permutation matrices Uniqueness of LU/LDU factorization for invertible matrices 1.5 Lecture 6 Column and null spaces Null space computation by solving Ax=0 Pivot and free variables, special solutions row reduced echelon form 2.1, 2.2 Lecture 7 Dimension = number of vectors in any basis Rank, row-rank = col-rank rank + nullity = number of columns 2.3, 2.4 Lecture 8 Orthogonal vectors and subspaces Row space orthogonal to null space 3.1 Quiz 1 Lecture 9 Projection onto a line Projection onto a subspace 3.2 Lecture 10 Least squares data fitting Orthonormal vectors 3.3 Lecture 11 Four fundamental subspaces (again) Least squares data fitting 2.4, 3.3 Lecture 12 Orthogonal bases Gram Schmidt algorithm Factorization A=QR 3.4 Quiz 2 Lecture 13 Linear transformations: definition, matrix representation 2.6 Lecture 14 Composition of linear transformations Change of basis Change of basis: Section 46 of Halmos's text Lecture 15 Similarity of transformations Section 47 of Halmos's text Quiz 3 Lecture 16 Determinants: Properties, Formula 4.2, 4.3 Lecture 17 Determinants: Cofactors, Applications in graphs 4.3, 4.4 Graph applications: Section 3.3 of Goodaire's text Lecture 18 Eigenvalues and Eigenvectors 5.1 Lecture 19 Similarity and diagonalization 5.2 Lecture 20 Spectral theorem for real symmetric matrices: case when eigenvalues are distinct 5.5 Lecture 21 Complex vector space, Hermitian and unitary matrices 5.5 Quiz 4 Lecture 22 Schur's theorem Spectral theorem as a corollary 5.5 Lecture 23 Singular value decomposition 6.3 Mid-sem Exam

Lecture number Topics Covered Section reference (Grimmett's book) Part II: Random Processes Lecture 1 Events as sets, probability spaces 1.2 Lecture 2 Cardinality, countability and infinite sums Sections 4 and 5 of Manjunath Krishnapur's notes Lecture 3 Properties of probability measure 1.3 Lecture 4 Conditional probability 1.4 Quiz 5 Lecture 5 Independence Gambler's ruin 1.5 Lecture 6 Random variables and distribution function 2.1 Lecture 7 Uncountable probability spaces, distribution functions Section 14 of Manjunath Krishnapur's notes Lecture 8 Law of averages - Bernstein's inequality 2.2 Lecture 9 Discrete r.v.s - definition and examples Independence 3.1 Quiz 6 Lecture 10 Discrete r.v.s - expectation, higher moments and examples 3.3, 3.5 Lecture 11 Discrete r.v.s - joint distribution function Covariance, correlation 3.6 Lecture 12 Discrete r.v.s - conditional distribution and expectation 3.7 Lecture 13 Discrete r.v.s - conditional expectation Sums of r.v.s 3.7, 3.8 Quiz 7 Lecture 14 Continuous r.v.s - p.d.f., independence, expectation 4.1, 4.2, 4.3 Lecture 15 Continuous r.v.s - examples 4.4 Lecture 16 Continuous r.v.s - dependence 4.5 Quiz 8 Lecture 17 Continuous r.v.s - conditional distributions and expectation 4.6 Lecture 18 Continuous r.v.s - functions of r.v.s 4.7 Lecture 19 Continuous r.v.s - change of variables 4.7 Lecture 20 Continuous r.v.s - multivariate normal distribution 4.9