Counting the faces of randomly-projected hypercubes and orthants, with applications. (English) Zbl 1191.52004

There are three fundamental regular polytopes in \({\mathbb R}^N\), \(N\geq 5\): the hypercube \(I^N\), the cross-polytope \(C^N\), and the simplex \(T^{N-1}\). For each of these, projecting the vertices into \({\mathbb R}^n\), \(n< N\), yields the vertices of a new polytope. In fact, up to translation and dilation, every polytope in \({\mathbb R}^n\) is obtained by rotating the simplex \(T^{N-1}\) and orthogonally projecting on the first \(n\) coordinates, for some choice of \(N\) and of \(N\)-dimensional rotation. Similarly, every centrally symmetric polytope can be generated by projecting the cross-polytope, and every zonotope by projecting the hypercube.
The paper is organized as follows: Section 1 contains formulations of the main results of the paper. Section 2 contains the proofs of the main results. Sections 3 and 4 are devoted to contrast the hypercube with other polytopes and with the cone. Section 5 is devoted to the application of face counting results in signal processing, information theory, and probability theory.


52A22 Random convex sets and integral geometry (aspects of convex geometry)
52B11 \(n\)-dimensional polytopes
52C35 Arrangements of points, flats, hyperplanes (aspects of discrete geometry)
Full Text: DOI arXiv


[1] Adamczak, R., Litvak, A.E., Pajor, A., Tomczak-Jaegermann, N.: Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling. arXiv:0904.4723v1 (2009) · Zbl 1222.52009
[2] Affentranger, F., Schneider, R.: Random projections of regular simplices. Discrete Comput. Geom. 7(3), 219-226 (1992) · Zbl 0751.52002
[3] Baryshnikov, Y.M.: Gaussian samplesm, regular simplices, and exchangeability. Discrete Comput. Geom. 17(3), 257-261 (1997) · Zbl 0897.60012
[4] Björner, A., Las Vergns, M., Sturmfels, B., White, N., Ziegler, G.: Oriented Matroids. Encyclopedia of Mathematics and Its Applications, vol. 46. Cambridge University Press, Cambridge (1999) · Zbl 0944.52006
[5] Bolker, E.D.: A class of convex bodies. Trans. Am. Math. Soc. 145, 323-345 (1969) · Zbl 0194.23102
[6] Böröczky, K., Jr., Henk, M.: Random projections of regular polytopes. Arch. Math. (Basel) 73(6), 465-473 (1999) · Zbl 0949.52001
[7] Bruckstein, A.M., Elad, M., Zibulevsky, M.: On the uniqueness of non-negative sparse and redundant representations. In: ICASSP 2008. Special session on Compressed Sensing, Las Vegas, Nevada (2008) · Zbl 1319.15007
[8] Buchta, C.: On nonnegative solutions of random systems of linear inequalities. Discrete Comput. Geom. 2(1), 85-95 (1987) · Zbl 0622.90054
[9] Cover, T.M.: Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition. IEEE Trans. Electron. Comput. EC-14(3), 326-334 (1965) · Zbl 0192.08403
[10] Donoho, D.L.: High-dimensional centrally-symmetric polytopes with neighborliness proportional to dimension. Discrete Comput. Geom. 35(4), 617-652 (2006) · Zbl 1095.52500
[11] Donoho, D.L.: Neighborly polytopes and sparse solutions of underdetermined linear equations. Technical Report, Stanford University (2006)
[12] Donoho, D.L., Tanner, J.: Neighborliness of randomly-projected simplices in high dimensions. Proc. Natl. Acad. Sci. USA 102(27), 9452-9457 (2005) · Zbl 1135.60300
[13] Donoho, D.L., Tanner, J.: Sparse nonnegative solutions of underdetermined linear equations by linear programming. Proc. Natl. Acad. Sci. USA 102(27), 9446-9451 (2005) · Zbl 1135.90368
[14] Donoho, D.L., Tanner, J.: Exponential bounds implying construction of neighborly polytopes, error-correcting codes and compressed sensing matrices by random sampling. Preprint (2007) · Zbl 1366.94233
[15] Donoho, D.L., Tanner, J.: Counting the faces of randomly-projected hypercubes and orthants, with applications. arXiv:0807.3590v1 (2008) · Zbl 1191.52004
[16] Donoho, D.L., Tanner, J.: Counting faces of randomly-projected polytopes when the projection radically lowers dimension. J. AMS 22(1), 1-53 (2009) · Zbl 1206.52010
[17] Donoho, D.L., Tanner, J.: Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing. Philos. Trans. A (2009) · Zbl 1185.94029
[18] Donoho, D.L., Johnstone, I.M., Hoch, J.C., Stern, A.S.: Maximum entropy and the nearly black object. J. R. Stat. Soc., Ser. B (Methodological) 54(1), 41-81 (1992) · Zbl 0788.62103
[19] Fuchs, J.-J.: On sparse representations in arbitrary redundant bases. IEEE Trans. Inf. Theory 50(6), 1341-1344 (2004) · Zbl 1284.94018
[20] Goodey, P.; Weil, W., Zonoids and generalisations, No. A, B, 1297-1326 (1993), Amsterdam · Zbl 0791.52006
[21] Grünbaum, B.: Convex Polytopes, 2nd edn. Graduate Texts in Mathematics, vol. 221. Springer, New York (2003). Prepared and with a preface by Volker Kaibel, Victor Klee, and Günter M. Ziegler
[22] Schläfli, L.: In: Gesammelte Mathematische Abhandlungen, vol. 1, pp. 209-212. Birkhäuser, Basel (1950)
[23] Schneider, R.; Weil, W., Zonoids and related topics, 296-317 (1983), Basel · Zbl 0524.52002
[24] Schneider, R., Weil, W.: Stochastic and Integral Geometry. Springer, Berlin (2008) · Zbl 1175.60003
[25] Vershik, A.M., Sporyshev, P.V.: Asymptotic behavior of the number of faces of random polyhedra and the neighborliness problem. Sel. Math. Sov. 11(2), 181-201 (1992) · Zbl 0791.52011
[26] Wendel, J.G.: A problem in geometric probability. Math. Scand. 11, 109-111 (1962) · Zbl 0108.31603
[27] Winder, R.O.: Partitions of n-space by hyperplanes. SIAM J. Appl. Math. 14(4), 811-818 (1966) · Zbl 0161.13601
[28] Ziegler, G.M.: Lectures on Polytopes. Graduate Texts in Mathematics, vol. 152. Springer, New York (1995) · Zbl 0823.52002
[29] Zong, C.: What is known about unit cubes. Bull. AMS 42(2), 181-211 (2005) · Zbl 1067.52010
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.