On approximation by projections of polytopes with few facets
From MaRDI portal
Publication:476495
DOI10.1007/S11856-014-0017-3zbMATH Open1310.52007arXiv1209.6281OpenAlexW2119867895MaRDI QIDQ476495FDOQ476495
Authors: Alexander E. Litvak, Nicole Tomczak-Jaegermann, Mark Rudelson 
Publication date: 2 December 2014
Published in: Israel Journal of Mathematics (Search for Journal in Brave)
Abstract: We provide an affirmative answer to a problem posed by Barvinok and Veomett, showing that in general an n-dimensional convex body cannot be approximated by a projection of a section of a simplex of a sub-exponential dimension. Moreover, we establish a lower bound of the Banach-Mazur distance between n-dimensional projections of sections of an N-dimensional simplex and a certain convex symmetric body, which is sharp up to a logarithmic factor for all N>n.
Full work available at URL: https://arxiv.org/abs/1209.6281
Recommendations
- Approximation of general smooth convex bodies
- The surface area deviation of the Euclidean ball and a polytope
- The Alon–Milman Theorem for Non-symmetric Bodies
- scientific article; zbMATH DE number 665688
- Fine approximation of convex bodies by polytopes
- Best and random approximation of convex bodies by polytopes
- Approximation of the Euclidean ball by polytopes with a restricted number of facets
- On the complexity of the set of unconditional convex bodies
- scientific article; zbMATH DE number 846112
- Dropping a vertex or a facet from a convex polytope
Cites Work
- Entropy and asymptotic geometry of non-symmetric convex bodies
- Title not available (Why is that?)
- Title not available (Why is that?)
- Random walks and anO*(n5) volume algorithm for convex bodies
- Title not available (Why is that?)
- On Polyhedral Approximations of the Second-Order Cone
- Gelfand numbers of operators with values in a Hilbert space
- Approximation of the Sphere by Polytopes having Few Vertices
- Smallest singular value of random matrices and geometry of random polytopes
- Distances between non-symmetric convex bodies and the \(MM^*\)-estimate
- Title not available (Why is that?)
- Title not available (Why is that?)
- Almost Euclidean Quotient Spaces of Subspaces of a Finite-Dimensional Normed Space
- Convexity, complexity, and high dimensions
- The finite dimensional basis problem with an appendix on nets of Grassmann manifolds
- Diameter of the Minkowski compactum is approximately equal to n
- Projecting \(l_{\infty}\) onto classical spaces
- Title not available (Why is that?)
- Recent progress and open problems in algorithmic convex geometry
- Thrifty approximations of convex bodies by polytopes
- Title not available (Why is that?)
- Essentially-Euclidean convex bodies
- Title not available (Why is that?)
Cited In (9)
- Projecting \(l_{\infty}\) onto classical spaces
- On the isotropic constant of random polytopes
- On the Banach-Mazur distance to cross-polytope
- Inner and outer approximations of polytopes using boxes.
- On polyhedral approximations of the positive semidefinite cone
- Dvoretzky's theorem and the complexity of entanglement detection
- On the complexity of the set of unconditional convex bodies
- Approximation of convex functions by projections of polyhedra
- On the geometry of random convex sets between polytopes and zonotopes
This page was built for publication: On approximation by projections of polytopes with few facets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q476495)
