On the geometry of polytopes generated by heavy-tailed random vectors

Abstract

We study the geometry of centrally symmetric random polytopes, generated by N independent copies of a random vector X taking values in ℝn. We show that under minimal assumptions on X, for N ≲ n and with high probability, the polytope contains a deterministic set that is naturally associated with the random vector - namely, the polar of a certain floating body. This solves the long-standing question on whether such a random polytope contains a canonical body. Moreover, by identifying the floating bodies associated with various random vectors, we recover the estimates that were obtained previously, and thanks to the minimal assumptions on X, we derive estimates in cases that were out of reach, involving random polytopes generated by heavy-tailed random vectors (e.g., when X is q-stable or when X has an unconditional structure). Finally, the structural results are used for the study of a fundamental question in compressive sensing - noise blind sparse recovery. Show more