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

Time
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.


Schedule

Mar 29. No class.

Mar 31. No class.

Part I: Embeddings into finite dimensional Euclidean space

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.

Part II: Nearest neighbor search

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.

Part III: Embeddings into Hilbert space

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.

Part IV: Student presentations

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


Related papers

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]