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 |