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

David L. Donoho, Jared Tanner

Abstract

This paper develops asymptotic methods to count faces of random high-dimensional polytopes. Beyond its intrinsic interest, our conclusions have surprising implications—in statistics, probability, information theory, and signal processing—with potential impacts in practical subjects like medical imaging and digital communications. Three such implications concern: convex hulls of Gaussian point clouds, signal recovery from random projections, and how many gross errors can be efficiently corrected from Gaussian error correcting codes.

Introduction: Challenging the Curse of Dimensionality

In classical geometry, projecting a complex 3D object onto a 2D plane typically results in significant information loss; edges overlap and vertices are obscured. For decades, it was assumed that projecting high-dimensional objects into much lower-dimensional spaces would be even more catastrophic. However, research by Donoho and Tanner reveals that high-dimensional shapes are remarkably robust. By calculating precise "phase transitions" in random projections, they demonstrate that sparse signals can be recovered and massive data errors corrected using far fewer measurements than previously thought possible.

The Three Mysteries of High Dimensions

The authors address three specific practical mysteries that defy low-dimensional intuition:

  1. Gaussian Point Clouds: Why does almost every point in a high-dimensional random cloud reside on its convex hull?
  2. Signal Recovery: What is the minimum number of random projections required to perfectly reconstruct a sparse signal?
  3. Error Correction: How many "gross errors" can a system tolerate while still allowing for perfect data recovery via linear programming?

Methodology: Proportional Growth and Combinatorial Geometry

The study shifts away from fixed-dimension asymptotics toward a proportional growth setting. In this framework, signal sparsity ($k$), the number of measurements ($n$), and the total dimensions ($N$) all scale together.

The core approach integrates:

  • Combinatorial Geometry: Utilizing the Affentranger-Schneider and Vershik-Sporyshev formulas to count the faces (vertices, edges, etc.) of projected polytopes, such as simplices and cross-polytopes.
  • Asymptotic Analysis: Defining "net exponents" ($\Psi$) to describe the growth or decay of the number of faces. The zeros of these exponents identify sharp boundaries known as Phase Transitions.
  • Neighborliness: Proving that random projections often preserve $k$-neighborliness—a property where every set of $k+1$ vertices defines a face.
Phase transition curves for random projections, illustrating the sharp boundaries between success and failure regions in high-dimensional space.

Key Insights: The Threshold Effect

A central finding is the existence of a sharp Phase Transition rather than a gradual decline in performance. If the number of measurements is just above a specific theoretical curve, success occurs with overwhelming probability; just below it, failure is almost certain.

This provides the theoretical justification for why $\ell_1$ minimization (linear programming) is an optimal tool for sparse signal recovery. It is not merely a heuristic but is geometrically destined to work under these high-dimensional conditions. Furthermore, these results indicate a high tolerance for malicious errors, provided the number of errors remains below the calculated threshold.

Empirical Validation and Asymptotic Behavior

The authors conducted 44,000 experiments with signal sizes of $N=10,000$, varying sparsity and measurement counts. The experimental results showed a remarkable match with the theoretical phase transition curves.

Detailed view of weak thresholds and their asymptotic behavior at small measurement rates.

Limitations and Future Work

While powerful, the theory has specific boundaries:

  • Gaussian Assumption: The proofs rely on Gaussian random matrices. While empirical evidence suggests these results extend to other distributions (e.g., Rademacher), formal proofs are more complex.
  • Scale Limits: The bounds are less effective when measurements and dimensions are very small; the theory is optimized for the "large-scale" regime.
  • Threshold Gaps: There remains a gap between "Weak" thresholds (where a typical face survives) and "Strong" thresholds (where all faces survive). Refining these estimates for very low-dimensional projections is an ongoing area of research.

Summary updated

Abstract

This paper develops asymptotic methods to count faces of random high-dimensional polytopes. Beyond its intrinsic interest, our conclusions have surprising implications - in statistics, probability, information theory, and signal processing - with potential impacts in practical subjects like medical imaging and digital communications. Three such implications concern: convex hulls of Gaussian point clouds, signal recovery from random projections, and how many gross errors can be efficiently corrected from Gaussian error correcting codes.
BibTeX
@article{donoho2008counting,
  author = {David L. Donoho and Jared Tanner},
  title = {{Counting faces of randomly-projected polytopes when the projection radically lowers dimension}},
  journal = {Journal of the American Mathematical Society},
  year = {2008},
  doi = {10.1090/s0894-0347-08-00600-0},
}
Figure