Date Topics Homework and reading assignments
High-dimensional data
9/7 overview; volumes; probability HW0 (due 9/12); Ball lec 1; BHK 2.1-2.4, 12.4
9/14 probability; random linear maps BHK 2.7; Dasgupta and Gupta; Ailon and Chazelle sec 2
9/21 subspace embeddings HW1 [.tex] (due 9/30); BHK 10.3; Drineas et al
9/28 clustering BHK 8.1-8.3; Arthur and Vassilvitskii
10/5 high-dimensional Gaussians BHK 2.6, 2.8, 2.9, 12.6
Low-rank matrix approximation
10/12 PCA and SVD HW2 [.tex] (due 10/28); Notes on PCA/SVD; BHK 3.4-3.9.3
10/19 random vectors and matrices Ahlswede-Winter notes; Tropp sec 2
10/26 random matrices; perturbations BHK 3.7, 7.3; Davis-Kahan notes
11/2 planted partitions; NMF HW3 [.tex] (due 11/21); BHK 8.6, 9.1; McSherry; Lee & Seung
Higher-order interactions
11/9 moments and tensors optional readings: convex polytopes paper; hardness paper
11/16 tensor decompositions latent variable models paper sec 2–3
11/23 Extended office hours
11/30 power iteration latent variable models paper sec 4–5; optional: odeco paper
Computation
12/7 Randomized NLA (Guest video lecture)