Radii of Euclidean sections of \(\ell_p\)-balls

The celebrated Dvoretzky theorem asserts that every \(N\)-dimensional convex body admits central sections of dimension \(d = \Omega(\log N)\), which is nearly spherical. For many instances of convex bodies, typically unit balls with respect to some norm, much better lower bounds on \(d\) have been o...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2024-10
Main Authors: Szarek, Stanislaw, Wolff, Pawel
Format: Article
Language:English
Subjects:
Approximation
Computer science
Euclidean geometry
Lower bounds
Questions
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The celebrated Dvoretzky theorem asserts that every \(N\)-dimensional convex body admits central sections of dimension \(d = \Omega(\log N)\), which is nearly spherical. For many instances of convex bodies, typically unit balls with respect to some norm, much better lower bounds on \(d\) have been obtained, with most research focusing on such lower bounds and on the degree of approximation of the section by a \(k\)-dimensional Euclidean ball. In this note we focus on another parameter, namely the radius of the approximating ball. We focus on the case of the unit ball of the space \(\ell_1^N\) (the so-called cross-polytope), which is relevant to various questions of interest in theoretical computer science. We will also survey other instances where similar questions for other normed spaces (most often \(\ell_p\)-spaces or their non-commutative analogues) were found relevant to problems in various areas of mathematics and its applications, and state some open problems. Finally, in view of the computer science ramifications, we will comment on the algorithmic aspects of finding nearly spherical sections.
ISSN:2331-8422