Home Research Teaching Publications index

CS 531: High Dimensional Data Science

January 2021

The objective is to understand the theoretical foundations of high dimensional data science. This is an elective course offered to undergraduate and postgraduate students.

Time

Place

Pre-requisite

  1. Algorithm Design
  2. Probability - video lectures by Prof.John Tsitsiklis
  3. Linear algebra - video lectures by Prof. Gilbert Strang
  4. Linear algebra - video lectures by 3blue1brown
  5. Single variable Calculus - video lecture by Prof. David Jerison

Books

  1. Foundations of Data science by Blum, Hopcroft and Kannan - online pdf
  2. Understanding machine learning by Shai Shalev-Shwartz and Shai Ben-David

Reference

Syllabus (not necessarily in this order)

  1. High Dimensional Space - The geometry of high dimension, properties of unit ball, Random projects and Johnson-Lindenstrauss Lemma, Separating gaussians
  2. Singular Value Decomposition (SVD) - Introduction to SVD, best k-rank approximations, left singular vectors, power method for SVD, applications of SVD.
  3. Compressed sensing

Academic Honesty

We expect every student to follow the highest standards of integrity and academic honesty. Copying/sharing code in exams, homeworks, labs are not allowed. All answers have to be written in your own words. You need to cite any idea you have taken from internet or text book to answer a question. See the IIT Goa policy for academic malpractices.

Course Schedule

# Date Topic Video Resources Other Resources
Introduction to Linear algebra
1 1/2/21 Vectors: magnitude & direction, linear combination, independence, span, basic, norms, inner product, orthogonal vectors
2 2/2/21 Matrices: column/row vectors, special matrices, matrix addition, matrix times a vector - multiple ways to see this, matrix multiplication, rank of a matrix, special matrices - identity matrix, diagonal matrix, inverse matrix
3 8/2/21 Eigen values and vectors: Computing them, Properties, Special matrices and their eigen values and eigen vectors Youtube PDF
4 9/2/21 Eigen values and vectors: Properties of eigen values and eigen vectors, Diagonalization Youtube PDF
5 15/2/21 Tutorial google drive 1 google drive 2
7 22/2/21 Discussion on sample linear algebra questions google drive
8 23/2/21 Markov chains and Google matrix google drive
9 24/2/21 Computing the Google page rank google drive
10 1/3/21 Singular Value Decomposition (SVD) google drive
11 2/3/21 Best k-rank approximation google drive
12 8/3/21 Principle component analysis google drive
13 10/3/21 Computing eigen values google drive
14 Mid semester exam
15 22/3/21 Mid semester answers google drive
16 22/3/21 Introduction to Probability google drive
17 5/4/21 Discrete Probability Review Youtube
18 6/4/21 Normal Distribution Review Youtube
19 12/4/21 Random points in high dimensional space google drive
20 17/4/21 High dimensional volume (CORRECTION: The formula for volume I wrote was correct. But the formula for Gamma function I wrote was wrong.) google drive
21 19/4/21 Introduction and applications of Johnson Lindenstrauss lemma google drive
22 20/4/21 Proof of Johnson Lindenstrauss Lemma (CORRECTION: I said that expectation of the square root of something is the square root of expectation. This claim is not correct. However our proof is not wrong as I had said in the lecture we can assume A = 1/sqrt(k) R and we need not assume my above 'claim'.) google drive
23 26/4/21 Introduction to Randomized algorithms google drive
24 27/4/21 Completing JL lemma proof google drive
25 3/5/21 Applications of JL lemma google drive
25 4/5/21 Applications of JL lemma continued google drive

Thank you