Fiches de cours

Convex geometry: Probablistic methods and metric embeddings

MATH-698

Lecturer(s) :

Naszódi Márton

Language:

English

Summary

The concentration of measure phenomenon is widely used in asymptotic geometric analysis, discrete mathematics and computer science. We introduce concentration and consider applications, such as embedding Euclidean spaces in normed spaces, or representing finite normed spaces in Euclidean space.

Content

We start with basics of the theory of normed spaces, including the Banach-Mazur distance.

Then, we introduce John's ellipsoid, a fundamental tool in approximation arguments.

The concentration of measure phenomenon will be demonstrated on the sphere.

We present Milman's proof of Dvoretzky's theorem on O(log d)-dimensional Euclidean subspaces of d-dimensional normed spaces. This instructive proof demonstrates the power of the concentration phenomenon in the study of convexity and combines several geometric and probabilistic arguments.

We then show the Johnson-Lindenstrauss flattening lemma and Bourgain's theorem on embeddings into Euclidean spaces.

If time permits, lower bounds on the dimension of the ambient space will also be presented.

Keywords

high dimensional, finite normed space, isometry, Euclidean subspace, maximum norm, flattening, embedding

Learning Prerequisites

Required courses

The course is self-contained, but prior knowledge of basic probability is an asset.

Learning Outcomes

By the end of the course, the student must be able to:

Resources

Bibliography

-- Shiri Artstein-Avidan, Apostolos Giannopoulos, and Vitali D. Milman: Asymptotic geometric analysis. Part I, Mathematical Surveys and Monographs, vol. 202, American Mathematical Society, Providence, RI, 2015.
-- Jirí Matousek, Lectures on discrete geometry, Graduate Texts in Mathematics, vol. 212, Springer-Verlag, New York, 2002.

In the programs

    • Semester
    • Exam form
       Written
    • Credits
      2
    • Subject examined
      Convex geometry: Probablistic methods and metric embeddings
    • Lecture
      28 Hour(s)

Reference week

 
      Lecture
      Exercise, TP
      Project, other

legend

  • Autumn semester
  • Winter sessions
  • Spring semester
  • Summer sessions
  • Lecture in French
  • Lecture in English
  • Lecture in German