TY - JOUR

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

AU - Guédon, Olivier

AU - Krahmer, Felix

AU - Kümmerle, Christian

AU - Mendelson, Shahar

AU - Rauhut, Holger

N1 - Publisher Copyright:
© 2022 World Scientific Publishing Company.

PY - 2022/4/1

Y1 - 2022/4/1

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

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

KW - Random polytopes

KW - compressed sensing

KW - heavy tails

KW - random matrices

KW - small ball probability

KW - ℓ1 -quotient property

UR - http://www.scopus.com/inward/record.url?scp=85107609015&partnerID=8YFLogxK

U2 - 10.1142/S0219199721500565

DO - 10.1142/S0219199721500565

M3 - Article

AN - SCOPUS:85107609015

SN - 0219-1997

VL - 24

JO - Communications in Contemporary Mathematics

JF - Communications in Contemporary Mathematics

IS - 3

M1 - 2150056

ER -