Approximating General Norms by Euclidean Beyond the John’s Ellipsoid
Episode details
Episode description
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. See more at https://www.microsoft.com/en-us/research/video/approximating-general-norms-euclidean-beyond-johns-ellipsoid/
Watch also from the same channel
More episodes from this channel
You might be interested in
