CS 594 Geometric algorithms for data analysis
Spring, 2018
Intructors:
Anastasios Sidiropoulos
Time:
Mon Wed, 4:00-5:15pm
Location:
TBH 180C
Office hours:
Mon 2:00-3:00pm, SEO 1240
Course description
Relevant textbooks
-
S. Har-Peled, Geometric approximation algorithms. AMS, 2011.
-
J. Matousek, Lectures on discrete geometry. Springer, 2002.
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:
-
Self-organizing neural network that discovers surfaces in random-dot 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: Earth-mover 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.