MTH 994-005: Topics Covered, and Resources
I plan to cover the following topics, time permitting. Note that the references linked to below are great resources, but will not contain everything I prove and discuss. I will be putting my own spin on things and emphasizing/deemphasizing/reinterpreting/adding to the material from these sources quite liberally. In short, come to class...- algorithms with best s-term approximation guarantees, and lower measurement bounds [Chapters 4 & 6 and Chapters 10 & 11 of Foucart and Rauhut, Cohen et al.]
- linear Johnson-Lindenstrauss (JL) embeddings of certain sets have the Restricted Isometry Property (RIP) [Baraniuk et al.]
- sub-Gaussian random matrices are linear JL embeddings with high probability [Chapters 7 & 8 of Foucart and Rauhut, Dasgupta et al.]
- Bounded Orthonormal Systems (BOS) and the RIP, RIP => JL embeddings, and tensor subspace embeddings [Chapters 9 & 12 of Foucart and Rauhut, Jin et al.]
- Gaussian Widths and Covering Numbers [Chapter 7 of Vershynin]
- Chaining and JL embeddings of arbitrary sets [Chapter 8 of Vershynin, Oymak et al.]
- Coherence, combinatorial properties, and sublinear-time algorithms [Chapter 5 of Foucart and Rauhut, Bailey et al., I'14]
- Sparse Fourier Transforms (SFTs) and rank-1 lattices for the approximation of functions of many variables [I'13, Merhi et al., Chapter 8 of Numerical Fourier Analysis]