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

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.