Approximating General Norms by Euclidean Beyond the John’s Ellipsoid

  • Ilya Razenshteyn | Microsoft

John’s theorem proved in 1948 states that any centrally-symmetric convex body in R^d can be sandwiched by two ellipsoids up to a factor of sqrt{d}. In particular, it implies that any d-dimensional normed space embeds into a Euclidean space with distortion sqrt{d}, which is tight. During the talk, I will introduce an embedding found in 1993 by Daher, which allows to break through the sqrt{d} barrier for the distortion at a cost of weakening the guarantees achieved. Despite this weakening, the embedding ends up being useful for some applications, which I will mention. We also make the Daher’s embedding algorithmic. Based on a joint work with Alex Andoni, Assaf Naor, Sasho Nikolov and Erik Waingarten.

接下来观看