Abstract
We provide an affirmative answer to a problem posed by Barvinok and Veomett in [4], showing that in general an n-dimensional convex body cannot be approximated by a projection of a section of a simplex of subexponential dimension. Moreover, we prove that for all 1 ≤ n ≤ N there exists an n-dimensional convex body B such that for every n-dimensional convex body K obtained as a projection of a section of an N-dimensional simplex one has
, where d(·, ·) denotes the Banach-Mazur distance and c is an absolute positive constant. The result is sharp up to a logarithmic factor.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
K. Ball, An elementary introduction to modern convex geometry, in Flavors of Geometry, Mathematical Sciences Research Institute Publications, Vol. 31, Cambridge University Press, Cambridge, 1997, pp. 1–58.
I. Bárány and Z. Füredy, Approximation of the sphere by polytopes having few vertices, Proceedings of the American Mathematical Society 102 (1988), 651–659.
A. Barvinok, Thrifty approximations of convex bodies by polytopes, International Mathematics Research Notices, to appear.
A. Barvinok and E. Veomett, The computational complexity of convex bodies, in Surveys on Discrete and Computational Geometry, Contemporary Mathematics, Vol. 453, American Mathematical Society, Providence, RI, 2008, pp. 117–137.
A. Ben-Tal and A. Nemirovski, On polyhedral approximations of the second-order cone, Mathematics of Operations Research 26 (2001), 193–205.
B. Carl and A. Pajor, Gelfand numbers of operators with values in a Hilbert space, Inventiones Mathematicae 94 (1988), 479–504.
E. D. Gluskin, Extremal properties of orthogonal parallelepipeds and their applications to the geometry of Banach spaces, (Russian) Matematicheskiĭ Sbornik 136(178) (1988), 85–96; translation in Mathematics of the USSR-Sbornik 64 (1989), 85–96.
E. D. Gluskin, Diameter of the Minkowski compactum is approximately equal to n. Functional Analysis and its Applications 15 (1981), 57–58; translation from Funktsionalnyĭ Analiz i ego Prilozheniya 15 (1981), 72–73.
F. John, Extremum problems with inequalities as subsidiary conditions, in Studies and Essays Presented to R. Courant on his 60th Birthday, January 8, 1948, Interscience Publishers, Inc., New York, 1948, pp. 187–204.
R. Kannan, L. Lovász and M. Simonovits, Random walks and O*(n 5) volume algorithm for convex bodies, Random Structures & Algorithms 2 (1997), 1–50.
H. König and N. Tomczak-Jaegermann, Projecting l ∞ onto classical spaces, Constructive Approximation 29 (2009), 277–292.
A. E. Litvak, V. D. Milman and N. Tomczak-Jaegermann, Essentially-Euclidean convex bodies, Studia Mathematica 196 (2010), 207–221.
A. E. Litvak, A. Pajor, M. Rudelson and N. Tomczak-Jaegermann, Smallest singular value of random matrices and geometry of random polytopes, Advances in Mathematics 195 (2005), 491–623.
A. E. Litvak and N. Tomczak-Jaegermann, Random aspects of high-dimensional convex bodies, in Geometric Aspects of Functional Analysis, Lecture Notes in Mathematics, Vol. 1745, Springer-Verlag, Berlin, 2000, pp. 169–190.
P. Mankiewicz and N. Tomczak-Jaegermann, Quotients of finite-dimensional Banach spaces; random phenomena, in Handbook of the Geometry of Banach Spaces, Vol. 2, North-Holland, Amsterdam, 2003, pp. 1201–1246.
V. D. Milman, Almost Euclidean quotient spaces of subspaces of a finite-dimensional normed space, Proceedings of the American Mathematical Society 94 (1985), 445–449.
V. D. Milman and A. Pajor, Entropy and asymptotic geometry of non-symmetric convex bodies, Advances in Mathematics 152 (2000), 314–335.
M. Rudelson, Distances between non-symmetric convex bodies and the MM*-estimate, Positivity 4 (2000), 161–178.
S. J. Szarek, The finite-dimensional basis problem with an appendix on nets of Grassmann manifolds, Acta Mathematica 151 (1983), 153–179.
S. J. Szarek, Nets of Grassmann manifold and orthogonal group, in Proceedings of research workshop on Banach space theory (Iowa City, Iowa, 1981), University of Iowa, Iowa City, IA, 1982, pp. 169–185.
S. J. Szarek, —sl Convexity, complexity, and high dimensions, in Proceedings of the International Congress of Mathematicians, Madrid, August 22–30, 2006, Vol. II, European Mathematical Society, Zurich, 2006, pp. 1599–1622.
N. Tomczak-Jaegermann, Banach-Mazur Distances and Finite-dimensional Operator Ideals, Pitman Monographs and Surveys in Pure and Applied Mathematics, Vol. 38,; John Wiley & Sons, Inc., New York, 1989.
S. S. Vempala, Recent progress and open problems in algorithmic convex geometry, in 30th International Conference on Foundations of Software Technology and Theoretical Computer Science, LIPIcs. Leibniz International Proceedings in Informatics, Vol. 8, Schloss Dagstuhl. Leibniz Zentrum für Informatik, Wadern, 2010, pp. 42–64.
Author information
Authors and Affiliations
Corresponding author
Additional information
In memoriam of Joram Lindenstrauss, a teacher and a colleague
Research partially supported by the E. W. R. Steacie Memorial Fellowship.
Research partially supported by NSF grant DMS 1161372.
This author holds the Canada Research Chair in Geometric Analysis.
Rights and permissions
About this article
Cite this article
Litvak, A.E., Rudelson, M. & Tomczak-Jaegermann, N. On approximation by projections of polytopes with few facets. Isr. J. Math. 203, 141–160 (2014). https://doi.org/10.1007/s11856-014-0017-3
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11856-014-0017-3