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

Authors:
David L. Donoho and Jared Tanner

Journal:
J. Amer. Math. Soc. **22** (2009), 1-53

MSC (2000):
Primary 52A22, 52B05, 52B11, 52B12, 62E20, 68P30, 68P25, 68W20, 68W40, 94B20, 94B35, 94B65, 94B70

DOI:
https://doi.org/10.1090/S0894-0347-08-00600-0

Published electronically:
July 10, 2008

MathSciNet review:
2449053

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

- Fernando Affentranger and Rolf Schneider,
*Random projections of regular simplices*, Discrete Comput. Geom.**7**(1992), no. 3, 219–226. MR**1149653**, DOI https://doi.org/10.1007/BF02187839 - Norman Bleistein and Richard A. Handelsman,
*Asymptotic expansions of integrals*, 2nd ed., Dover Publications, Inc., New York, 1986. MR**863284** - Károly Böröczky Jr. and Martin Henk,
*Random projections of regular polytopes*, Arch. Math. (Basel)**73**(1999), no. 6, 465–473. MR**1725183**, DOI https://doi.org/10.1007/s000130050424 - Emmanuel J. Candès, Justin Romberg, and Terence Tao,
*Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information*, IEEE Trans. Inform. Theory**52**(2006), no. 2, 489–509. MR**2236170**, DOI https://doi.org/10.1109/TIT.2005.862083 - Emmanuel J. Candes and Terence Tao,
*Decoding by linear programming*, IEEE Trans. Inform. Theory**51**(2005), no. 12, 4203–4215. MR**2243152**, DOI https://doi.org/10.1109/TIT.2005.858979 - Emmanuel J. Candes and Terence Tao,
*Near-optimal signal recovery from random projections: universal encoding strategies?*, IEEE Trans. Inform. Theory**52**(2006), no. 12, 5406–5425. MR**2300700**, DOI https://doi.org/10.1109/TIT.2006.885507 - E. W. Cheney,
*Introduction to approximation theory*, AMS Chelsea Publishing, Providence, RI, 1998. Reprint of the second (1982) edition. MR**1656150** - David L. Donoho,
*Compressed sensing*, IEEE Trans. Inform. Theory**52**(2006), no. 4, 1289–1306. MR**2241189**, DOI https://doi.org/10.1109/TIT.2006.871582 - David L. Donoho,
*For most large underdetermined systems of equations, the minimal $l_1$-norm near-solution approximates the sparsest near-solution*, Comm. Pure Appl. Math.**59**(2006), no. 7, 907–934. MR**2222440**, DOI https://doi.org/10.1002/cpa.20131 - David L. Donoho,
*High-dimensional centrally symmetric polytopes with neighborliness proportional to dimension*, Discrete Comput. Geom.**35**(2006), no. 4, 617–652. MR**2225676**, DOI https://doi.org/10.1007/s00454-005-1220-0 - ---,
*Neighborly polytopes and sparse solutions of underdetermined linear equations*, Technical report Stanford University, Department of Statistics, $\#$ 2005-04 (2005). - David L. Donoho and Jared Tanner,
*Neighborliness of randomly projected simplices in high dimensions*, Proc. Natl. Acad. Sci. USA**102**(2005), no. 27, 9452–9457. MR**2168716**, DOI https://doi.org/10.1073/pnas.0502258102 - David L. Donoho and Jared Tanner,
*Sparse nonnegative solution of underdetermined linear equations by linear programming*, Proc. Natl. Acad. Sci. USA**102**(2005), no. 27, 9446–9451. MR**2168715**, DOI https://doi.org/10.1073/pnas.0502269102 - ---,
*Finite dimensional phase transition for the expected number of randonly-projected simplices and cross-polytopes*, preprint (2007). - M. F. Duarte, M.B. Wakin, and R.G. Baraniuk,
*Fast reconstruction of piecewise smooth signals from random projections*, Proceedings SPARS 05, Rennes, France, 2005. - Elwyn R. Berlekamp, Robert J. McEliece, and Henk C. A. van Tilborg,
*On the inherent intractability of certain coding problems*, IEEE Trans. Inform. Theory**IT-24**(1978), no. 3, 384–386. MR**495180**, DOI https://doi.org/10.1109/tit.1978.1055873 - David Gale,
*Neighboring vertices on a convex polyhedron*, Linear inequalities and related system, Annals of Mathematics Studies, no. 38, Princeton University Press, Princeton, N.J., 1956, pp. 255–263. MR**0085552** - David Gale,
*Neighborly and cyclic polytopes*, Proc. Sympos. Pure Math., Vol. VII, Amer. Math. Soc., Providence, R.I., 1963, pp. 225–232. MR**0152944** - Branko Grünbaum,
*Convex polytopes*, 2nd ed., Graduate Texts in Mathematics, vol. 221, Springer-Verlag, New York, 2003. Prepared and with a preface by Volker Kaibel, Victor Klee and Günter M. Ziegler. MR**1976856** - Peter Hall, J. S. Marron, and Amnon Neeman,
*Geometric representation of high dimension, low sample size data*, J. R. Stat. Soc. Ser. B Stat. Methodol.**67**(2005), no. 3, 427–444. MR**2155347**, DOI https://doi.org/10.1111/j.1467-9868.2005.00510.x - Jarvis Haupt and Robert A. Nowak,
*Signal reconstruction from noisy randomized projections with applications to wireless sensing*, Tech. report, Electrical Engineering, University of Wisconsin, 2005. - Jørgen Hoffmann-Jørgensen, Michael B. Marcus, and Jon A. Wellner (eds.),
*High dimensional probability. III*, Progress in Probability, vol. 55, Birkhäuser Verlag, Basel, 2003. Papers from the 3rd International Conference held in Sandjberg, June 24–28, 2002. MR**2033877** - Irene Hueter,
*Limit theorems for the convex hull of random points in higher dimensions*, Trans. Amer. Math. Soc.**351**(1999), no. 11, 4337–4363. MR**1670156**, DOI https://doi.org/10.1090/S0002-9947-99-02499-X - M. Kendall, A. Stuart, and J.K. Ord,
*Kendall’s advanced theory of statistics*, Edward Arnold, London, 1991. - Nathan Linial and Isabella Novik,
*How neighborly can a centrally symmetric polytope be?*, Discrete Comput. Geom.**36**(2006), no. 2, 273–281. MR**2252105**, DOI https://doi.org/10.1007/s00454-006-1235-1 - Jiří Matoušek,
*Lectures on discrete geometry*, Graduate Texts in Mathematics, vol. 212, Springer-Verlag, New York, 2002. MR**1899299** - P. McMullen and G. C. Shephard,
*Diagrams for centrally symmetric polytopes*, Mathematika**15**(1968), 123–138. MR**238180**, DOI https://doi.org/10.1112/S0025579300002473 - Harold Ruben,
*On the geometrical moments of skew-regular simplices in hyperspherical space, with some applications in geometry and mathematical statistics*, Acta Math.**103**(1960), 1–23. MR**121713**, DOI https://doi.org/10.1007/BF02546523 - Mark Rudelson and Roman Vershynin,
*Geometric approach to error-correcting codes and reconstruction of signals*, Int. Math. Res. Not.**64**(2005), 4019–4041. MR**2206919**, DOI https://doi.org/10.1155/IMRN.2005.4019 - ---,
*Sparse reconstruction by convex relaxation: Fourier and gaussian measurements*, Proceedings Conference on Information Science and Systems (CISS) 2006, Princeton University, 2006. - Rolf Schneider,
*Neighbourliness of centrally symmetric polytopes in high dimensions*, Mathematika**22**(1975), no. 2, 176–181. MR**405244**, DOI https://doi.org/10.1112/S0025579300006045 - J.A. Tropp and Anna Gilbert,
*Signal recovery from partial information by orthogonal matching pursuit*, Tech. report, Mathematics Department, University of Michigan, 2005. - Y. Tsaig and D.L. Donoho,
*Extensions of compressed sensing*, EURASIP Journal of Applied Signal Processing**86**(2006), no. 3, 549–571. - A. M. Vershik and P. V. Sporyshev,
*Asymptotic behavior of the number of faces of random polyhedra and the neighborliness problem*, Selecta Math. Soviet.**11**(1992), no. 2, 181–201. Selected translations. MR**1166627**

Retrieve articles in *Journal of the American Mathematical Society*
with MSC (2000):
52A22,
52B05,
52B11,
52B12,
62E20,
68P30,
68P25,
68W20,
68W40,
94B20,
94B35,
94B65,
94B70

Retrieve articles in all journals with MSC (2000): 52A22, 52B05, 52B11, 52B12, 62E20, 68P30, 68P25, 68W20, 68W40, 94B20, 94B35, 94B65, 94B70

Additional Information

**David L. Donoho**

Affiliation:
Department of Statistics, Stanford University, 390 Serra Mall, Sequoia Hall, Stanford, California 94305

MR Author ID:
59130

Email:
donoho@stanford.edu

**Jared Tanner**

Affiliation:
Department of Statistics, Stanford University 390 Serra Mall, Sequoia Hall, Stanford, California 94305

Email:
tanner@math.utah.edu

Received by editor(s):
July 5, 2006

Published electronically:
July 10, 2008

Additional Notes:
The first author acknowledges partial support from NSF DMS 05-05303, 01-40698 (FRG), and NIH

The second author acknowledges support from NSF fellowship DMS 04-03041 and thanks John E. and Marva M. Warnock for their generous support in the form of an endowed chair.

Article copyright:
© Copyright 2008
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication.