Title: Metric Embeddings - What, How and Why?

Speaker: Professor Sylvester Eriksson-Bique (University of Jyväskylä)

Time: 

Each lecture is 45 mins+15 mins break+45 mins+15 mins discussion. Lecture notes are available at here.

Also available in zoom. Zoom registration 

Syllabus: 

• Definitions: Finite metric spaces and graph metrics, l_p metrics, doubling metric spaces, trees, Fréchet embeddings
• Kuratowski Embedding
• Bourgain Embedding Theorem
• Assouad Embedding theorem
• Cut-Cone decomposition and isometric embedding of l_2 into L^1
• Goemans-Linial semidefinite relaxation for the Sparsest Cut Problem
• Non-embedding theorems, including Laakso diamond graph
• Embedding simple graphs, e.g. trees. – depending on time.

Abstract/Description:

This will be a course on metric embeddings to Euclidean space. Algorithms manipulate data, which often can come to us in a complicated form. To enhance our computational abilities, we represent data in different spaces, where computations are easier, via metric embeddings. We will discuss what metric embeddings are and introduce the most important terminology and methods. Then, we see some important classical theorems on existence of embeddings (Assouad, Bourgain and Kuratowski). Given these embeddings, we will discuss their importance to application and tell about the sparsest cut problem and its semi-definite relaxation. Finally, we discuss some ways embeddings may fail to exist, and how simple geometry can help to find embeddings. The focus is on the math, but wherever possible, we make remarks on and give references to more algorithmic results. We may also mention some open mathematical problems of various difficulty.

At the end of the course, by active participation, you should expect to know what metric embeddings are. You would have starting points for further reading and a general view of the field and be able to state why its exciting. You could construct simple embeddings and identify (some) obstructions to embeddability.

Prerequisites: We will be mostly self-contained, but familiarity with the following will be of great help since we will just state these without proof: basic probability (e.g. independence, Chebychev inequality, sums of i.i.d. Normal random variables), basic linear algebra, calculus (Hölder's inequality), familiarity with inner products and norms, graphs and metric spaces (definition enough), basic optimization (e.g. simplex method). This is a mathematical course, so a general familiarity with proofs and a Bachelor's level maturity with mathematics should suffice, which usually includes the previous topics.