CMSE 890-002: Topics Covered, and ResourcesI 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...
- Fast and small space algorithms for counting and collecting basic statistics [Morris, Flajolet, Flajolet & Martin]
- Locality Sensitive Hashing (LSH) for fast nearest neighbor calculations [Indyk et al., Andoni et al.]
- A review of the singular value decomposition, PCA, and related inequalities [Topics in Matrix Analysis by R. Horn and C. Johnson]
- Linear JL embeddings and their applications in fast randomized numerical linear algebra [Dasgupta et al., Woodruff, Halko et al., Rokhlin et al.]
- Finite metric space embeddings and their applications [Indyk, Linial et al., Matousek]
- Tensor basics and factorizations including the HoSVD, CPD, and Tensor Train decompositions [Kolda et al., Oseledets, De Lathauwer et al., Ozdemir et al.]
- 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]