Sept 9 
Course overview 


Sept 14 
High dimensional Euclidean space 
Lec 1 of Ball; Sec 2.12.4 of BHK 

Sept 16 
Probability 
Sec 12.4 of BHK; Notes on probability 
HW1 (due Fri Oct 2) 
Sept 21 
Probability; random linear maps 
Dasgupta and Gupta 

Sept 23 
Random linear maps; subspace embeddings 
Notes on JL lemma 

Sept 28 
Subspace embeddings; approximate least squares 


Sept 30 
Structured random linear maps 
Sec 2 of Ailon and Chazelle 

Oct 5 
Spectral decomposition; multivariate Gaussians 
Sec 2.6, 2.9, 12.6 of BHK 

Oct 7 
Separating Gaussian populations; projection pursuit 
Sec 2.8 of BHK 
HW2 (due Fri Oct 23) 
Oct 12 
PCA and SVD 
Notes on PCA/SVD 

Oct 14 
Matrix norms; lowrank matrix approximation 
Sec 3.43.6, 3.9 of BHK 

Oct 19 
Lowrank matrix approximation; power method 
Sec 3.73.10 of BHK 

Oct 21 
Power method; sketchandsolve low rank approximation 


Oct 26 
Sketchandsolve low rank approximation; kcenter clustering 
Notes on low rank approximations 
HW3 (due Mon Nov 9) 
Oct 28 
kmeans clustering; kmeans++ 
Sec 8.18.2 of BHK 

Nov 2 
No lecture 


Nov 4 
kmeans++; divideandconquer kmeans clustering 
Aggarwal, Deshpande, and Kannan
 
Nov 9 
kmeans + PCA; Euclidean embeddings 
Sec 8.4 of BHK; notes on kmeans 

Nov 11 
Embeddings into \(\ell_2\) and \(\ell_\infty\) 
Sec 15.4 of Matoušek 

Nov 16 
Fréchet embeddings 
Sec 15.7 of Matoušek 

Nov 18 
Embedding \(\ell_2^d\) into \(\ell_1^{O(d)}\); approximating sparsest cuts 
Sec 15.8 of Matoušek; notes on \(\ell_2^d \to \ell_1^{O(d)}\) 
HW4 (due Mon Dec 7) 
Nov 23 
Prony's method; uncertainty principle 
Sec 10.3 (intro), 10.4 of BHK 

Nov 25 
No lecture 


Nov 30 
Incoherence; orthogonal matching pursuit 
Notes on sparsity 

Dec 2 



Dec 7 
No lecture 


Dec 9 
Restricted isometry property; basis pursuit 
Sec 10.3 of BHK 

Dec 14 
Project presentations 


Dec 21 
Project presentations 

