CSE 291: Distances, similarities, and embeddings (Spring 2016)

TuTh 12.30-1.50 in CSE 4258

Useful texts

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.

Part I: Embeddings into finite dimensional Euclidean space

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.

Part II: Nearest neighbor search

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.

Part III: Embeddings into Hilbert space

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.

Part IV: Student presentations

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]