Skip to Main Content

Journal of the American Mathematical Society

Published by the American Mathematical Society, the Journal of the American Mathematical Society (JAMS) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

ISSN 1088-6834 (online) ISSN 0894-0347 (print)

The 2020 MCQ for Journal of the American Mathematical Society is 4.79.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

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 PDF
J. Amer. Math. Soc. 22 (2009), 1-53 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
Similar Articles
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.
  • © 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