pith. sign in

arxiv: 1907.07258 · v1 · pith:M2ARA7AInew · submitted 2019-07-16 · 🧮 math.PR · cs.IT· math.IT

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

Olivier Gu\'edon , Felix Krahmer , Christian K\"ummerle , Shahar Mendelson , Holger Rauhut This is my paper

Pith reviewed 2026-05-24 20:27 UTC · model grok-4.3

classification 🧮 math.PR cs.ITmath.IT
keywords random polytopesfloating bodyheavy-tailed distributionscentrally symmetric convex bodieshigh-probability containmentcompressive sensingnoise-blind recoveryunconditional structure
0
0 comments X

The pith

A random polytope generated by N copies of a heavy-tailed vector X contains the polar of X's floating body with high probability when N is linear in the dimension.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that under minimal assumptions on a random vector X in R^n, the centrally symmetric polytope formed by N independent copies contains, with high probability for N at least on the order of n, the polar of a deterministic floating body associated with X. This containment supplies a canonical inner body for the random polytope and resolves whether such polytopes must contain a deterministic set tied to the law of X. The same statement recovers earlier estimates for lighter-tailed vectors by explicit identification of their floating bodies and produces new bounds for heavy-tailed cases, including q-stable laws and vectors with unconditional structure. The geometric fact is then applied to obtain guarantees for noise-blind sparse recovery.

Core claim

Under minimal assumptions on X, for N ≳ n and with high probability, the polytope conv{±X_1, …, ±X_N} contains the polar of a certain floating body of X. Identifying the floating bodies for various distributions recovers known estimates and yields new ones for heavy-tailed X; the structural containment is used to study noise-blind sparse recovery.

What carries the argument

The polar of the floating body of X; it is the deterministic set shown to lie inside the random polytope with high probability.

If this is right

  • Estimates previously obtained for light-tailed vectors are recovered by computing the associated floating bodies.
  • New high-probability containment statements hold for q-stable random vectors and for vectors possessing an unconditional structure.
  • The containment is applied to derive recovery guarantees for noise-blind sparse recovery in compressive sensing.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The result suggests that floating-body polars may serve as canonical approximants for a broader family of random convex bodies generated by heavy-tailed measures.
  • The same minimal-assumption framework could be tested on non-symmetric or non-centered generating vectors to check whether analogous inner bodies appear.
  • In compressive sensing the containment may translate into uniform recovery bounds that remain valid across a wider range of measurement matrices.

Load-bearing premise

The random vector X must satisfy the minimal conditions that make its floating body well-defined and that guarantee the high-probability containment inside the polytope.

What would settle it

A concrete counter-example in which, for some X obeying the minimal assumptions and N linear in n, the generated polytope fails to contain the polar of the floating body on a set of positive probability that does not vanish as n grows.

read the original abstract

We study the geometry of centrally-symmetric random polytopes, generated by $N$ independent copies of a random vector $X$ taking values in $\mathbb{R}^n$. We show that under minimal assumptions on $X$, for $N \gtrsim 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 have been obtained previously, and thanks to the minimal assumptions on $X$ we derive estimates in cases that had been 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 3 minor

Summary. The paper studies centrally-symmetric random polytopes K_N generated by N i.i.d. copies of a random vector X in R^n. Under minimal assumptions on X, it proves that when N ≳ n, with high probability K_N contains the polar of a certain floating body associated to X. This resolves whether such polytopes contain a canonical deterministic body, recovers prior estimates for light-tailed and unconditional cases, extends the results to heavy-tailed distributions (q-stable, unconditional), and applies the structural containment to noise-blind sparse recovery in compressive sensing.

Significance. If the containment holds under the stated minimal assumptions, the work supplies a unified deterministic inner body for random polytopes across a wide range of tail behaviors, including previously inaccessible heavy-tailed regimes. The recovery of known results for q-stable and unconditional vectors, together with the application to noise-blind recovery, indicates both technical reach and concrete utility in high-dimensional probability and compressive sensing.

major comments (2)
  1. [§3, Theorem 3.1] §3, Theorem 3.1 (or the main containment theorem): the precise minimal assumptions on X (e.g., the exact integrability or tail conditions that guarantee the floating body is well-defined and the high-probability inclusion) must be stated explicitly before the theorem; the abstract refers to them as “minimal” but the derivation steps that verify they suffice for q-stable vectors are not visible without the full proof.
  2. [§5] §5 (application to noise-blind sparse recovery): the reduction from the geometric containment to the recovery guarantee appears to require an additional uniform bound on the floating-body radius that is not derived from the minimal assumptions alone; if this bound is obtained only under stronger moment conditions, the claim that the result applies verbatim to heavy-tailed X needs clarification.
minor comments (3)
  1. [§4] Notation for the floating body (e.g., the parameter t or the level of truncation) should be fixed consistently between the statement of the main theorem and the examples in §4.
  2. The high-probability statement is given as “with high probability”; an explicit failure probability (e.g., 1−N^{−c} or exp(−c n)) would make the quantitative dependence on N and n clearer.
  3. A short comparison table or paragraph contrasting the new minimal assumptions with those in the cited works (e.g., the papers recovering the light-tailed case) would help readers see exactly which hypotheses have been relaxed.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive evaluation and constructive comments, which will improve the clarity of the manuscript. We respond to each major comment below and will incorporate the clarifications in a revised version.

read point-by-point responses

  1. Referee: [§3, Theorem 3.1] §3, Theorem 3.1 (or the main containment theorem): the precise minimal assumptions on X (e.g., the exact integrability or tail conditions that guarantee the floating body is well-defined and the high-probability inclusion) must be stated explicitly before the theorem; the abstract refers to them as “minimal” but the derivation steps that verify they suffice for q-stable vectors are not visible without the full proof.

    Authors: We agree that the minimal assumptions on X should be stated explicitly before Theorem 3.1. In the revision we will add a dedicated paragraph immediately preceding the theorem that lists the precise integrability and tail conditions ensuring the floating body is well-defined and the high-probability containment holds. For q-stable vectors we will insert a brief remark after the assumption statement noting that they satisfy the conditions (with the explicit verification remaining in the proof of the application, as it uses the specific tail decay of the stable law). revision: yes

  2. Referee: [§5] §5 (application to noise-blind sparse recovery): the reduction from the geometric containment to the recovery guarantee appears to require an additional uniform bound on the floating-body radius that is not derived from the minimal assumptions alone; if this bound is obtained only under stronger moment conditions, the claim that the result applies verbatim to heavy-tailed X needs clarification.

    Authors: The uniform bound on the floating-body radius follows directly from the minimal assumptions on X and the definition of the floating body; it does not require stronger moment conditions. The geometric containment already encodes the necessary control on the radius for the heavy-tailed cases (including q-stable), and this is used verbatim in the reduction to the recovery guarantee in §5. We will add one clarifying sentence in §5 that explicitly recalls how the radius bound is obtained from the minimal assumptions alone. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The central claim is a general high-probability containment theorem: under minimal assumptions on the random vector X, the random polytope generated by N independent copies contains (whp, for N ≳ n) the polar of a deterministically defined floating body associated with X. The floating body is constructed independently of the polytope and the result is derived via probabilistic arguments rather than by fitting parameters, renaming inputs, or reducing to self-citations. No load-bearing steps reduce by construction to the paper's own fitted quantities or prior self-referential definitions; the assumptions on X are external and the result recovers prior estimates without circularity. This is the most common honest finding for a self-contained mathematical theorem.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on unspecified minimal assumptions on the random vector X that ensure the floating body is well-defined; these are domain assumptions in convex geometry whose precise form is not visible from the abstract.

axioms (1)
  • domain assumption X satisfies minimal assumptions making the floating body well-defined and the containment hold
    Abstract invokes these assumptions without listing them; they are the load-bearing premise for all stated results.

pith-pipeline@v0.9.0 · 5722 in / 1206 out tokens · 23512 ms · 2026-05-24T20:27:16.714088+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

40 extracted references · 40 canonical work pages · 2 internal anchors

  1. [1]

    Adamczak, A

    R. Adamczak, A. Litvak, A. Pajor, and N. Tomczak-Jaegerman n. Quantitative estimates of the convergence of the empirical covariance matrix in log-conca ve ensembles. J. AMS , 23(2):535–561, 2010

    work page 2010

  2. [2]

    Adamczak, A

    R. Adamczak, A. E. Litvak, A. Pajor, and N. Tomczak-Jaegerm ann. Restricted isometry property of matrices with independent columns and neighborly polyt opes by random sam- pling. Constr. Approx. , 34:61–88, 2011

    work page 2011

  3. [3]

    B´ ar´ any

    I. B´ ar´ any. Random polytopes, convex bodies, and approxima tion. In Stochastic geometry , volume 1892 of Lecture Notes in Math. , pages 77–118. Springer, Berlin, 2007. 21

    work page 2007

  4. [4]

    Blumer, A

    A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. Le arnability and the Vapnik- Chervonenkis dimension. J. ACM , 36:929–965, 1989

    work page 1989

  5. [5]

    C. Borell. Convex measures on locally convex spaces. Ark. Mat. , 12(1):239–252, 1974

    work page 1974

  6. [6]

    Bousquet

    O. Bousquet. A Bennett concentration inequality and its applicat ion to suprema of empirical processes. C. R. Math. , 334(6):495–500, 2002

    work page 2002

  7. [7]

    Brazitikos, A

    S. Brazitikos, A. Giannopoulos, P. Valettas, and B.-H. Vritsiou. Geometry of isotropic convex bodies. American Mathematical Society, Providence, Rhode Island, 2014

    work page 2014

  8. [8]

    Brugiapaglia and B

    S. Brugiapaglia and B. Adcock. Robustness to unknown error in s parse regularization. IEEE Trans. Inform. Theory , 64(10):6638–6661, 2018

    work page 2018

  9. [9]

    Chafa ¨ ı, O

    D. Chafa ¨ ı, O. Gu´ edon, G. Lecu´ e, and A. Pajor.Interactions between compressed sensing ran- dom matrices and high dimensional geometry , volume 37 of Panoramas et Synth` eses [Panora- mas and Syntheses] . Soci´ et´ e Math´ ematique de France, Paris, 2012

    work page 2012

  10. [10]

    Dafnis, A

    N. Dafnis, A. Giannopoulos, and A. Tsolomitis. Asymptotic shape of a random polytope in a convex body. J. Funct. Anal. , 257(9):2820 – 2839, 2009

    work page 2009

  11. [11]

    De la Pe˜ na and E

    V. De la Pe˜ na and E. Gin´ e.Decoupling. From dependence to independence. Randomly sto pped processes, U-statistics and processes, martingales and be yond. Springer Science & Business Media, 2012

    work page 2012

  12. [12]

    DeVore, G

    R. DeVore, G. Petrova, and P. Wojtaszczyk. Instance-opt imality in probability with an ℓ1- minimization decoder. Appl. Comput. Harmon. Anal. , 27(3):275 – 288, 2009

    work page 2009

  13. [13]

    Dirksen, G

    S. Dirksen, G. Lecu´ e, and H. Rauhut. On the gap between res tricted isometry properties and sparse recovery conditions. IEEE Trans. Inform. Theory , 64(8):5478–5487, 2018

    work page 2018

  14. [14]

    D. L. Donoho. Compressed sensing. IEEE Trans. Inform. Theory , 52(4):1289–1306, 2006

    work page 2006

  15. [15]

    S. Foucart. Stability and robustness of ℓ1-minimizations with Weibull matrices and redundant dictionaries. Linear Algebra Appl. , 441:4 – 21, 2014

    work page 2014

  16. [16]

    Foucart and H

    S. Foucart and H. Rauhut. A Mathematical Introduction to Compressive Sensing . Applied and Numerical Harmonic Analysis. Springer New York, 2013

    work page 2013

  17. [17]

    Giannopoulos and M

    A. Giannopoulos and M. Hartzoulaki. Random spaces generated by vertices of the cube. Discrete Comput. Geom. , 28(2):255–273, 2002

    work page 2002

  18. [18]

    E. D. Gluskin. Extremal properties of orthogonal parallelepipe ds and their applications to the geometry of Banach spaces. Sb. Math. , 64(1):85, 1989

    work page 1989

  19. [19]

    Gu´ edon, A

    O. Gu´ edon, A. Litvak, and K. Tatarko. Random polytopes obt ained by matrices with heavy tailed entries. To appear in Commun. Contemp. Math. , 2019

    work page 2019

  20. [20]

    Gu´ edon, P

    O. Gu´ edon, P. Nayar, and T. Tkocz. Concentration inequalitie s and geometry of convex bodies. In Analytical and probabilistic methods in the geometry of con vex bodies, volume 2 of IMPAN Lect. Notes , pages 9–86. Polish Acad. Sci. Inst. Math., Warsaw, 2014

    work page 2014

  21. [21]

    Haussler

    D. Haussler. Sphere packing numbers for subsets of the Boole an n-cube with bounded Vapnik- Chervonenkis dimension. J. Combinat. Theory, Ser. A , 69:217–232, 1995

    work page 1995

  22. [22]

    A Quotient Property for Matrices with Heavy-Tailed Entries and its Application to Noise-Blind Compressed Sensing

    F. Krahmer, C. K¨ ummerle, and H. Rauhut. A quotient property for matrices with heavy-tailed entries and its application to noise-blind compressed sensing. Preprint arXiv:1806.04261 , 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  23. [23]

    Krahmer, S

    F. Krahmer, S. Mendelson, and H. Rauhut. Suprema of chaos p rocesses and the restricted isometry property. Comm. Pure Appl. Math. , 67(11):1877–1904, 2014. 22

    work page 1904

  24. [24]

    Kwapie´ n and W

    S. Kwapie´ n and W. A. Woyczy´ nski. Random series and stochastic integrals: single and multiple. Probability and its Applications. Birkh¨ auser Boston, Inc., Boston , MA, 1992

    work page 1992

  25. [25]

    Ledoux and M

    M. Ledoux and M. Talagrand. Probability in Banach spaces . Classics in Mathematics. Springer-Verlag, Berlin, 2011. Isoperimetry and processes, Rep rint of the 1991 edition

    work page 2011

  26. [26]

    Litvak, A

    A. Litvak, A. Pajor, M. Rudelson, and N. Tomczak-Jaegerman n. Smallest singular value of random matrices and geometry of random polytopes. Adv. Math., 195(2):491 – 523, 2005

    work page 2005

  27. [27]

    Lutwak and G

    E. Lutwak and G. Zhang. Blaschke-Santal´ o inequalities. J. Diff. Geom. , 45:1–16, 1997

    work page 1997

  28. [28]

    Mendelson

    S. Mendelson. A few notes on statistical learning theory. In S. Mendelson and A. Smola, editors, Advanced Lectures on Machine Learning , volume 2600, pages 1–40. Springer, 2003

    work page 2003

  29. [29]

    Mendelson

    S. Mendelson. Learning without concentration. J. ACM , 62(3):21:1–21:25, June 2015

    work page 2015

  30. [30]

    On the geometry of random polytopes

    S. Mendelson. On the geometry of random polytopes. arXiv preprint arXiv:1902.01664, 2019

    work page internal anchor Pith review Pith/arXiv arXiv 1902

  31. [31]

    Mendelson and G

    S. Mendelson and G. Lecu´ e. Sparse recovery under weak mom ent assumptions. J. Eur. Math. Soc., 19(3):881–904, 2017

    work page 2017

  32. [32]

    Meyer and S

    M. Meyer and S. Reisner. Characterizations of affinely-rotatio n-invariant log-concave mea- sures by section-centroid location. In Geometric aspects of functional analysis (1989–90) , volume 1469 of Lecture Notes in Math. , pages 145–152. Springer, Berlin, 1991

    work page 1989

  33. [33]

    Mohri, A

    M. Mohri, A. Rostamizadeh, and A. Talwalkar. Foundations of Machine Learning . MIT Press, 2012

    work page 2012

  34. [34]

    S. J. Montgomery-Smith. The distribution of Rademacher sums . Proc. Amer. Math. Soc. , 109(2):517–522, 1990

    work page 1990

  35. [35]

    G. Paouris. Concentration of mass on convex bodies. Geom. Funct. Anal. , 16(5):1021–1049, 2006

    work page 2006

  36. [36]

    Sch¨ utt and E

    C. Sch¨ utt and E. Werner. The convex floating body. Math. Scand. , 66(2):275–290, 1990

    work page 1990

  37. [37]

    Talagrand

    M. Talagrand. Sharper bounds for Gaussian and empirical proc esses. Ann. Prob., 22(1):28–76, 1994

    work page 1994

  38. [38]

    Talagrand

    M. Talagrand. New concentration inequalities in product spaces . Invent. Math. , 126(3):505– 563, 1996

    work page 1996

  39. [39]

    V. N. Vapnik and A. Y. Chervonenkis. On the uniform convergen ce of relative frequencies of events to their probabilities. Theor. Probab. Appl. , 16:264–280, 1971

    work page 1971

  40. [40]

    Wojtaszczyk

    P. Wojtaszczyk. Stability and instance optimality for Gaussian m easurements in compressed sensing. Found. Comput. Math. , 10(1):1–13, 2010. 23

    work page 2010