Counting faces of randomly projected polytopes when the projection radically lowers dimension
HTML articles powered by AMS MathViewer
- by David L. Donoho and Jared Tanner
- J. Amer. Math. Soc. 22 (2009), 1-53
- DOI: https://doi.org/10.1090/S0894-0347-08-00600-0
- Published electronically: July 10, 2008
- PDF | Request permission
Abstract:
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.
References
- Fernando Affentranger and Rolf Schneider, Random projections of regular simplices, Discrete Comput. Geom. 7 (1992), no. 3, 219–226. MR 1149653, DOI 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 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 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 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 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 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 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 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 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 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 10.1109/tit.1978.1055873
- David Gale, Neighboring vertices on a convex polyhedron, Linear inequalities and related systems, 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, DOI 10.1007/978-1-4613-0019-9
- 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 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, DOI 10.1007/978-3-0348-8059-6
- 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 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 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, DOI 10.1007/978-1-4613-0039-7
- P. McMullen and G. C. Shephard, Diagrams for centrally symmetric polytopes, Mathematika 15 (1968), 123–138. MR 238180, DOI 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 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 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 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
Similar Articles
- 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
Bibliographic 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. - © Copyright 2008
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - 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
- MathSciNet review: 2449053