Sketching and Embeddings 1/2
433 views · Published 28 March 2016 · 47:29 · Indexed 14 November 2026
Channel: Institut Henri Poincaré · 2016 · Science & Technology
By Alex Andoni (Columbia) Abstract: Sketching for distance estimation is the problem where we need to design a possibly randomized function f from a metric space to short strings, such that from f(x) and f(y) we can estimate the distance between x and y. This problem is a core problem in both the streaming and nearest neighbor search areas. We will discuss this problem and its connections to the theory of metric embeddings. In particular, we will discuss when and why sketching is equivalent to embedding into normed space such as ℓ1.
More from this channel
-
29:47
10 ans du Groupe Calcul : Histoire du Calcul - Introduction
-
52:14
Gauss, Jacobi, Seidel, Richardson, Krylov: the Invention of Iterative Methods
-
55:33
Les "invariants arithmétiques" de H. Poincaré
-
1:08:53
Henri Poincaré, a founding father of the modern theory of PDEs
-
57:13
Sympletic topology from Poincaré to Gromov
-
57:35
Structural Realism, Then and Now
-
46:26
Poincaré inequalities in probability and geometric analysis
-
1:02:05
On the contributions of Henri Poincaré to modern geophysics...