CS 594 Geometric algorithms for data analysis
Spring, 2018
Intructors:
Anastasios Sidiropoulos
Time:
Mon Wed, 4:005:15pm
Location:
TBH 180C
Office hours:
Mon 2:003:00pm, SEO 1240
Course description
Relevant textbooks

S. HarPeled, Geometric approximation algorithms. AMS, 2011.

J. Matousek, Lectures on discrete geometry. Springer, 2002.
Homework
TBA
Lectures

Jan 17, 2018. Lecture 1: Introduction. Clustering I.
Additional reading material:

Jan 22, 2018. Lecture 2: Clustering II.

Jan 24, 2018. Lecture 3: Clustering III.
Additional reading material:

Jan 29, 2018. Lecture 4: Dimensionality reduction.
Additional reading material:

Jan 31, 2018. Lecture 5: Geometric realizations of metrical data I:
Embedding into L_{∞}.
Bourgain's theorem and its extensions.
Additional reading material:

Feb 5, 2018. Lecture 6: Geometric realizations of metrical data II.

Feb 7, 2018. Lecture 7: Geometric realizations of graphs: Spectral embeddings. Spectral partitioning.
Additional reading material:

Feb 12, 2018. Lecture 8: Nearest neighbor search I.
Additional reading material:

Feb 14, 2018. Lecture 9: Nearest neighbor search II.

Feb 19, 2018. Lecture 10: Spaces of low intrinsic dimension.
Additional reading material:

Feb 21, 2018. Lecture 11: From metric spaces to graphs: Graph spanners.
Additional reading material:

Feb 26, 2018. Lecture 12: Metric learning.
Additional reading material:

Feb 28, 2018. Lecture 13: Deep metric learning.
Additional reading material:

Selforganizing neural network that discovers surfaces in randomdot stereograms, Becker, S. and Hinton, G.E., 1992.

Signature verification using a ``siamese'' time delay neural network, J. Bromley, I. Guyon, Y. Lecun, E. Sackinger, R. Shah, 1994.

Learning a similarity metric discriminatively, with application to face verification,
Chopra, S., Hadsell, R., & LeCun, Y., 2005.

Learning a nonlinear embedding by preserving class neighbourhood structure,
R. Salakhutdinov and G. Hinton, 2007.

Mar 5, 2018. Lecture 14: Earthmover distance.
Additional reading material:

Mar 7, 2018. Lecture 15: Geometric algorithms over data streams.
Additional reading material:

Mar 12, 2018. Guest lecture by prof. Xinhua Zhang: Optimization in geometric problems, with applications to SVMs.
Additional reading material:

Mar 14, 2018. Guest lecture by prof. Lev Reyzin: SVD, PCA and clustering spherical Gaussians.
Additional reading material:

Mar 19, 2018. Lecture 16: Sublinear time algorithms.
Additional reading material:

Mar 21, 2018. Lecture 17: Data analysis in the space of curves.
Additional reading material:

Apr 2, 2018. Lecture 18: Denoising metrical data sets I.

Apr 4, 2018. Lecture 18: Denoising metrical data sets II.

Apr 9, 2018. Lecture 19: Coresets.