Metric embeddings

MATH-513 / 5 credits

Teacher:

Language: English

Remark: Pas donné en 2024-25

Summary

The course aims to introduce the basic concepts and results on metric embeddings, or more precisely on approximate embeddings. This area has been under rapid development since the 90's and it has strong impact on algorithms for discrete optimization problems.

Content

  • Metrics: l_p metrics, distortion
  • Dimension reduction by random projections: Johnson-Lindenstrauss lemma
  • Metrics of negative type
  • Error correction and compressed sensing
  • Lower bounds on distortion: Nonembeddability of expanders
  • Bourgains Theorem

Learning Prerequisites

Recommended courses

  • Linear algebra 1+2
  • Introduction to Algorithms or Discrete Optimization

Assessment methods

Written exam

Resources

Bibliography

Jiri Matousek: Lecture notes on metric embeddings

 

Ressources en bibliothèque

In the programs

  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Metric embeddings
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Type: optional
  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Metric embeddings
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Type: optional
  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Metric embeddings
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Type: optional
  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Metric embeddings
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Type: optional

Reference week

Related courses

Results from graphsearch.epfl.ch.