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

Donoho, David L.; Tanner, Jared

Discrete Comput. Geom. 43, No. 3, 522-541 (2010).

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.

Reviewer: Viktor Oganyan (Erevan)

MSC:

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)

Keywords:

zonotope; random polytopes; random cones; random matrices; arrangements of hyperplanes

References:

[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