Metric Representations - Algorithms and Geometry

Explore the intricacies of metric representations in this 56-minute lecture delivered by Anna Gilbert from Yale University at the virtual 2022 Joint Mathematics Meetings. Delve into the algorithms and geometry behind metric representations, starting with classical multi-dimensional scaling and progressing through metric repair definitions and problem formulations. Examine optimization techniques, including the Project and Forget method, and learn about metric violations through separation oracles and shortest paths. Understand the Bregman projection and theoretical results summarized in the Summary Theorem. Investigate extensions, applications, and traditional techniques for metric repair, including three repair scenarios. Conclude with insights into graph metric repair and dimensionality reduction algorithms, gaining a comprehensive understanding of this complex mathematical topic.

Intro
Metric representations: Algorithms and Geometry
Classical multi-dimensional scaling
Metric repair: definitions
Metric Repair Formally
General problem formulation: metric constrained problems
Optimization techniques: existing methods
Project and Forget
Metric violations: Separation oracle
Metric violations: shortest path
Bregman projection
Theoretical results: Summary Theorem
Extensions and applications
Metric repair: traditional techniques
Three Repair Scenarios: Constrain P
Extensions and generalizations
Graph metric repair: results summary
Dimensionality Reduction Algorithms