** 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. The covariance mapping. Distances of negative type and positive definite functions.

May 5. Schoenberg's mapping. Embeddings of positive-definite shift-invariant functions.

May 10. Songbai, Larry

May 12. Andrew

May 17. No class

May 19. Ben, Jongha

May 24. Siva

May 26. No class

May 31. Liam, Julaiti

Jun 2. Bryce, Thomas

Jun 7. Akshay

Jun 9. Man

** Embeddings of finite metrics**

Fakcharoenphol, Rao, Talwar. A tight bound on approximating arbitrary metrics by tree metrics.

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

** Random projections **

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

** Multidimensional scaling **

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

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

** Ordinal embedding**

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

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

** Nearest neighbor search**

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

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

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

** Embeddings in Hilbert space**

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

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

** Neural embeddings**

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