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.
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