Lecture

Embeddings into l_inf

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

In course

MATH-513: Metric embeddings

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 proble ...

Description

This lecture discusses embeddings into l_inf, focusing on a theorem related to finite metric spaces. The instructor explains the application of the theorem with examples and explores Frechet embeddings, open balls, and random selection of points.

Official source

Related concepts (17)

Metric space

In mathematics, a metric space is a set together with a notion of distance between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general setting for studying many of the concepts of mathematical analysis and geometry. The most familiar example of a metric space is 3-dimensional Euclidean space with its usual notion of distance. Other well-known examples are a sphere equipped with the angular distance and the hyperbolic plane.

Compact space

In mathematics, specifically general topology, compactness is a property that seeks to generalize the notion of a closed and bounded subset of Euclidean space. The idea is that a compact space has no "punctures" or "missing endpoints", i.e., it includes all limiting values of points. For example, the open interval (0,1) would not be compact because it excludes the limiting values of 0 and 1, whereas the closed interval [0,1] would be compact.

Intrinsic metric

In the mathematical study of metric spaces, one can consider the arclength of paths in the space. If two points are at a given distance from each other, it is natural to expect that one should be able to get from the first point to the second along a path whose arclength is equal to (or very close to) that distance. The distance between two points of a metric space relative to the intrinsic metric is defined as the infimum of the lengths of all paths from the first point to the second.

Metrizable topological vector space

In functional analysis and related areas of mathematics, a metrizable (resp. pseudometrizable) topological vector space (TVS) is a TVS whose topology is induced by a metric (resp. pseudometric). An LM-space is an inductive limit of a sequence of locally convex metrizable TVS.

Ball (mathematics)

In mathematics, a ball is the solid figure bounded by a sphere; it is also called a solid sphere. It may be a closed ball (including the boundary points that constitute the sphere) or an open ball (excluding them). These concepts are defined not only in three-dimensional Euclidean space but also for lower and higher dimensions, and for metric spaces in general. A ball in n dimensions is called a hyperball or n-ball and is bounded by a hypersphere or (n−1)-sphere.

Related lectures (10)

Randomness in Social Process

Explores randomness in social processes, focusing on the selection of authority roles.

Quantum Random Number Generation

Explores quantum random number generation, discussing the challenges and implementations of generating good randomness using quantum devices.

Weibull Model: Random Data

Explores the Weibull model's application to random data and its significance in analyzing material strength and failure probability.

Probability Convergence

Explores probability convergence, discussing conditions for random variable sequences to converge and the uniqueness of convergence.

Lp Cone and Approximate Embeddings