CS6015: Linear Algebra and Random Processes
Course information
When: Jul-Nov 2017
Lectures: Slot B
Where: CS34
Teaching Assistants: Purvi Goel, Ditty Matthew, Hardi Shaileshbhai Shah, Abhishek kumar, Jom Kuriakose
Office Hours:
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
Grading
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 |
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 |
Problem sets
Quizzes/Exams
Tutorials
Textbooks
Linear algebra and applications by Gilbert Strang
Probability and random processes by Geoffrey Grimmett and David Stirzaker
Additional references:
Linear Algebra: Pure and Applied by Edgar Goodaire
ECE 313 UIUC course lecture notes by Bruce Hajek
Introduction to probability models by Sheldon Ross
Schedule
Part I: Linear Algebra | ||
Lecture number | Topics Covered | Section reference (Strang's book) |
---|---|---|
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 |
Part II: Random Processes | ||
Lecture number | Topics Covered | Section reference (Grimmett's book) |
---|---|---|
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 |