Counting faces of randomly projected polytopes when the projection radically lowers dimension

Donoho, David¹ ; Tanner, Jared²

¹ Department of Statistics, Stanford University, 390 Serra Mall, Sequoia Hall, Stanford, California 94305
² Department of Statistics, Stanford University 390 Serra Mall, Sequoia Hall, Stanford, California 94305

Journal of the American Mathematical Society, Tome 22 (2009) no. 1, pp. 1-53

Résumé

Let $Q = Q_N$ denote either the $N$-dimensional cross-polytope $C^N$ or the $N-1$-dimensional simplex $T^{N-1}$. Let $A = A_{n,N}$ denote a random orthogonal projector $A: \mathbf {R}^{N} \mapsto bR^n$. We compare the number of faces $f_k(AQ)$ of the projected polytope $AQ$ to the number of faces of $f_k(Q)$ of the original polytope $Q$. We concentrate on the case where $n$ and $N$ are both large, but $n$ is much smaller than $N$; in this case the projection dramatically lowers dimension. We consider sequences of triples $(k,n,N)$ where $N = N_n$ is not exponentially larger than $n$. We identify thresholds of the form $const \cdot n \log (n/N)$ where the relationship of $f_k(AQ)$ and $f_k(Q)$ changes abruptly. These properties of polytopes have significant implications for neighborliness of convex hulls of Gaussian point clouds, for efficient sparse solution of underdetermined linear systems, for efficient decoding of random error correcting codes and for determining the allowable rate of undersampling in the theory of compressed sensing. The thresholds are characterized precisely using tools from polytope theory, convex integral geometry, and large deviations. Asymptotics developed for these thresholds yield the following, for fixed $\epsilon > 0$. With probability tending to 1 as $n$, $N$ tend to infinity: (1a) for $k (1-\epsilon ) \cdot n [2e\ln (N/n)]^{-1}$ we have $f_k(AQ) = f_k(Q)$, (1b) for $k > (1 +\epsilon ) \cdot n [2e\ln (N/n)]^{-1}$ we have $f_k(AQ) f_k(Q)$, with ${\mathcal E}$ denoting expectation, (2a) for $k (1-\epsilon ) \cdot n [2\ln (N/n)]^{-1}$ we have ${\mathcal E} f_k(AQ) > (1-\epsilon ) f_k(Q)$, (2b) for $k > (1 +\epsilon ) \cdot n [2\ln (N/n)]^{-1}$ we have ${\mathcal E} f_k(AQ) \epsilon f_k(Q)$. These asymptotically sharp transitions in the behavior of face numbers as $k$ varies relative to $n \log (N/n)$ are proven, interpreted, and related to the above-mentioned applications.

Détail

DOI : 10.1090/S0894-0347-08-00600-0

Bibliographie

[1] Affentranger, Fernando, Schneider, Rolf Random projections of regular simplices Discrete Comput. Geom. 1992 219 226

[2] Bleistein, Norman, Handelsman, Richard A. Asymptotic expansions of integrals 1986

[3] Bã¶Rã¶Czky, Kã¡Roly, Jr., Henk, Martin Random projections of regular polytopes Arch. Math. (Basel) 1999 465 473

[4] Candã¨S, Emmanuel J., Romberg, Justin, Tao, Terence Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information IEEE Trans. Inform. Theory 2006 489 509

[5] Candes, Emmanuel J., Tao, Terence Decoding by linear programming IEEE Trans. Inform. Theory 2005 4203 4215

[6] Candes, Emmanuel J., Tao, Terence Near-optimal signal recovery from random projections: universal encoding strategies? IEEE Trans. Inform. Theory 2006 5406 5425

[7] Cheney, E. W. Introduction to approximation theory 1998

[8] Donoho, David L. Compressed sensing IEEE Trans. Inform. Theory 2006 1289 1306

[9] Donoho, David L. For most large underdetermined systems of equations, the minimal 𝑙₁-norm near-solution approximates the sparsest near-solution Comm. Pure Appl. Math. 2006 907 934

[10] Donoho, David L. High-dimensional centrally symmetric polytopes with neighborliness proportional to dimension Discrete Comput. Geom. 2006 617 652

[11] Donoho, David L., Tanner, Jared Neighborliness of randomly projected simplices in high dimensions Proc. Natl. Acad. Sci. USA 2005 9452 9457

[12] Donoho, David L., Tanner, Jared Sparse nonnegative solution of underdetermined linear equations by linear programming Proc. Natl. Acad. Sci. USA 2005 9446 9451

[13] Berlekamp, Elwyn R., Mceliece, Robert J., Van Tilborg, Henk C. A. On the inherent intractability of certain coding problems IEEE Trans. Inform. Theory 1978 384 386

[14] Gale, David Neighboring vertices on a convex polyhedron 1956 255 263

[15] Gale, David Neighborly and cyclic polytopes 1963 225 232

[16] Grã¼Nbaum, Branko Convex polytopes 2003

[17] Hall, Peter, Marron, J. S., Neeman, Amnon Geometric representation of high dimension, low sample size data J. R. Stat. Soc. Ser. B Stat. Methodol. 2005 427 444

[18] High dimensional probability. III 2003

[19] Hueter, Irene Limit theorems for the convex hull of random points in higher dimensions Trans. Amer. Math. Soc. 1999 4337 4363

[20] Linial, Nathan, Novik, Isabella How neighborly can a centrally symmetric polytope be? Discrete Comput. Geom. 2006 273 281

[21] Matouå¡Ek, Jiå™Ã­ Lectures on discrete geometry 2002

[22] Mcmullen, P., Shephard, G. C. Diagrams for centrally symmetric polytopes Mathematika 1968 123 138

[23] Ruben, Harold On the geometrical moments of skew-regular simplices in hyperspherical space, with some applications in geometry and mathematical statistics Acta Math. 1960 1 23

[24] Rudelson, Mark, Vershynin, Roman Geometric approach to error-correcting codes and reconstruction of signals Int. Math. Res. Not. 2005 4019 4041

[25] Schneider, Rolf Neighbourliness of centrally symmetric polytopes in high dimensions Mathematika 1975 176 181

[26] Vershik, A. M., Sporyshev, P. V. Asymptotic behavior of the number of faces of random polyhedra and the neighborliness problem Selecta Math. Soviet. 1992 181 201