Counting faces of randomly-projected polytopes when the projection radically lowers dimension
Lists
Only you see this
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},
}| High-Dimensional Centrally Symmetric Polytopes with Neighborliness Proportional to Dimension | Discret. Comput. Geom · 2006 |
| Counting the Faces of Randomly-Projected Hypercubes and Orthants, with Applications | Discret. Comput. Geom · 2010 |
| The minimum neighborliness of a random polytope | arXiv · 2023 |
| On the geometry of polytopes generated by heavy-tailed random vectors | arXiv · 2019 |
| Observed Universality of Phase Transitions in High-Dimensional Geometry, with Implications for Modern Data Analysis and Signal Processing | arXiv · 2009 |
| Universality in polytope phase transitions and message passing algorithms | The Annals of Applied Probability · 2015 |