Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Journal of the American Mathematical Society
Journal of the American Mathematical Society
ISSN 1088-6834(online) ISSN 0894-0347(print)

 

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
Published electronically: July 10, 2008
MathSciNet review: 2449053
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)


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


Additional Information

David L. Donoho
Affiliation: Department of Statistics, Stanford University, 390 Serra Mall, Sequoia Hall, Stanford, California 94305
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

DOI: http://dx.doi.org/10.1090/S0894-0347-08-00600-0
PII: S 0894-0347(08)00600-0
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.