[Mini-Course] Metric Embeddings - What, How and Why? Professor Sylvester Eriksson-Bique (University of Jyväskylä)

Date

Wednesday, February 21, 2024 - 10:00 to Friday, March 1, 2024 - 12:00

Location

L4F01 + Zoom

Description

Title: Metric Embeddings - What, How and Why?

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

Time: 

Lecture 1 Feb 21, Wednesday  10:00-12:00 L4F01
Lecture 2 Feb 26, Monday 14:00-16:00 L4F01
Lecture 3 Feb 28, Wednesday 14:00-16:00 L4F01
Lecture 4 Mar 1, Friday 10:00-12:00 L4F01

Each lecture is 45 mins+15 mins break+45 mins+15 mins discussion.

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.

 

 

 

 

Attachments

All-OIST Category: 

Subscribe to the OIST Calendar: Right-click to download, then open in your calendar application.