Mathematical Toolkit - Autumn 2021

TTIC 31150/CMSC 31150

T Th 9:30 - 10:50 am (Zoom)

Discussion: W 4-5 pm (Zoom)

Office Hours: M 2-3 pm (Shashank), W 3-4 pm (Madhur), F 4-5 pm (Tushant)

TAs: Shashank Srivastava, Tushant Mittal

The course is aimed at first-year graduate students and advanced undergraduates. The goal of the course is to collect and present important mathematical tools used in different areas of computer science. The course will mostly focus on linear algebra and probability. We intend to cover the following topics and examples:

Abstract linear algebra: vector spaces, linear transformations, Hilbert spaces, inner product, Gram-Schmidt orthogonalization, eigenvalues and eigenvectors, SVD.
Least squares, iterative solvers for systems of linear equations, spectral graph theory, perturbation and stability of eigenvalues
Discrete probability: random variables, Markov, Chebyshev and Chernoff-Hoeffding bounds
Gaussian variables, concentration inequalities, dimension reduction.
Spectral partitioning and clustering.
Additional topics (to be chosen from based on time and interest): Martingales, Markov Chains, Random Matrices, Tensors, Chaining Methods

The course will have 5 homeworks (60 percent), a midterm (15 percent), and a final (25 percent).

There is no textbook for this course. Please see the "Resources" and "Recommended Books" sections below for some useful references.

Homeworks and Announcements

Homework 1 (Due on 10/14/21).
Homework 2 (Due on 10/26/21).
Homework 3 (Due on 11/12/21).
Homework 4 (Due on 11/23/21).
Homework 5 (Due on 12/08/21).

Lecture Plan and Notes

9/28: Fields and vector spaces.
[Jamboard] [Notes] [Video]
9/30: Bases of vector spaces, Lagrange interpolation, linear transformations.
[Jamboard] [Notes] [Video]
10/5: Eigenvalues and eigenvectors. Inner products.
[Jamboard] [Notes] [Video]
10/7: Orthogonality and orthonormality. Adjoints.
[Jamboard] [Notes] [Video]
10/12: Self-adjoint operators. Real spectral theorem.
[Jamboard] [Notes] [Video]
10/14: Rayleigh quotients. Singular Value Decomposition.
[Jamboard] [Notes] [Video]
10/19: Singular Value Decomposition for matrices, Low-rank approximation
[Jamboard] [Notes] [Video]
10/21: Least squares approximation using SVD, Gershgorin disc theorem and applications
[Jamboard] [Notes] [Video]
10/26: Solving systems of linear equations, steepest descent, conjugate gradient method
[Jamboard] [Notes] [Video]
11/2: Basics of probability: the finite case
[Jamboard] [Notes] [Video]
11/4: Independence, discrete random variables, coupon collection
[Jamboard] [Notes] [Video]
11/9: Polynomial identity lemma, probabilistic method
[Jamboard] [Notes] [Video]
11/11: The probabilistic method. Markov's and Chebyshev's inequalities.
[Jamboard] [Notes] [Video]
11/16: Threshold phenomena in random graphs, Chernoff-Hoeffding bounds
[Jamboard] [Notes] [Video]
11/18: Applications of Chernoff/Hoeffding bounds. Probability over uncountable spaces.
[Jamboard] [Notes] [Video]
11/30: Random variables on uncountable spaces. Gaussian random variables.
[Jamboard] [Notes] [Video]
12/02: More on Gaussians. Johnson-Lindenstrauss dimension reduction.
[Jamboard] [Notes] [Video]

Resources

REU courses on Linear Algebra and Combinatorics by Laci Babai (with a great collection of problems).
Thirty three miniatures by Jiri Matousek (a preliminary version is available for download).
Lx=b by Nisheeth Vishnoi.
Lecture notes on foundations of probability by Terry Tao.

Recommended Books

There is no textbook for this course. The following books may be useful as references:

The Linear Algebra a Beginning Graduate Student Ought to Know
(by Jonathan S. Golan)
Foundations of Data Science (by Blum, Hopcroft and Kannan)
Probability and Computing (by Mitzenmacher and Upfal)
The Probabilistic Method (by Alon and Spencer)
High-Dimensional Probability (by Roman Vershynin)