** Time **

TuTh 12.30-1.50 in CSE 4258

Wells and Williams. Embeddings and Extensions in Analysis. Springer, 1975.

Deza and Laurent. Geometry of Cuts and Metrics. Springer, 1997.

Both of these are available online through Roger.

Mar 29. No class.

Mar 31. No class.

Reading:

Matousek. Embedding finite metrics into normed spaces.

Apr 5. Overview of course. Frechet embeddings.

Apr 7. Bourgain's embedding.

Apr 12. Bourgain's embedding (cont'd). Random projections of finite point sets.

Apr 14. Johnson-Lindenstrauss lemma (cont'd). Random projections of linear subspaces.

Apr 19. Multidimensional scaling: several variants, and statistical issues.

Reading:

Andoni, Indyk. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions.

Charikar. Similarity estimation techniques from rounding algorithms.

Beygelzimer, Langford, Kakade. Cover trees for nearest neighbor.

Apr 21. Locality-sensitive hashing.

Apr 26. Locality-sensitive hashing (cont'd).

Apr 28. Cover trees.

Reading:

Deza and Laurent: chapters 3,4,5,6.

Wells and Williams: chapter 1.

Schoenberg. Metric spaces and positive definite functions.

May 3. Embeddings into Lp spaces.

May 5. Similarity transforms, Lp embeddability, and functions of positive type.

May 10. Songbai

Arias-Castro. Some theory for ordinal embedding. [Songbai]

May 12. Andrew, Andy

Terada, von Luxburg. Local ordinal embedding. [Andrew]

Levy, Goldberg. Neural word embedding as implicit matrix factorization. [Andy]

May 17. No class

May 19. Ben

Krauthgamer, Lee, Mendel, Naor. Measured descent: a new embedding method for finite metrics. [Ben]

May 24. Jongha, Xinan

Ailon, Chazelle. The fast Johnson-Lindenstrauss transform and approximate nearest neighbors. [Jongha]

De Silva, Tenenbaum. Sparse multidimensional scaling using landmark points. [Xinan]

May 26. No class

May 31. Larry, Amanda

Shrivastava, Li. Asymmetric LSH for sublinear time maximum inner product search. [Larry]

Van der Maaten, Hinton. Visualizing data using t-SNE. [Amanda]

Jun 2. Akshay, Liam

Andoni, Razenshteyn. Optimal data-dependent hashing for approximate near neighbors. [Akshay]

Jun 7. Bryce, Julaiti

Smola, Gretton, Song, Scholkopf. A Hilbert space embedding for distributions. [Julaiti]

Rahimi, Recht. Random features for large-scale kernel machines. [Bryce]

Jun 9. Siva, Yan

Veldaldi, Zisserman. Efficient additive kernels via explicit feature maps. [Siva]

Abdullah, Andoni, Kannan, Krauthgamer. Spectral approaches to nearest neighbor search. [Yan]