Under minimal assumptions on X, centrally symmetric random polytopes generated by N ≳ n copies of X contain the polar of its floating body with high probability.
A Quotient Property for Matrices with Heavy-Tailed Entries and its Application to Noise-Blind Compressed Sensing
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
abstract
For a large class of random matrices $A$ with i.i.d. entries we show that the $\ell_1$-quotient property holds with probability exponentially close to 1. In contrast to previous results, our analysis does not require concentration of the entrywise distributions. We provide a unified proof that recovers corresponding previous results for (sub-)Gaussian and Weibull distributions. Our findings generalize known results on the geometry of random polytopes, providing lower bounds on the size of the largest Euclidean ball contained in the centrally symmetric polytope spanned by the columns of $A$. At the same time, our results establish robustness of noise-blind $\ell_1$-decoders for recovering sparse vectors $x$ from underdetermined, noisy linear measurements $y = Ax + w$ under the weakest possible assumptions on the entrywise distributions that allow for recovery with optimal sample complexity even in the noiseless case. Our analysis predicts superior robustness behavior for measurement matrices with super-Gaussian entries, which we confirm by numerical experiments.
representative citing papers
The sharp MSE bound for the ℓ1-minimum-norm interpolator under isotropic Gaussian covariates is recovered via the geometry of symmetric Gaussian polytopes, without the convex Gaussian min-max theorem.
citing papers explorer
-
On the geometry of polytopes generated by heavy-tailed random vectors
Under minimal assumptions on X, centrally symmetric random polytopes generated by N ≳ n copies of X contain the polar of its floating body with high probability.
-
Minimum Norm Interpolation via The Local Theory of Banach Spaces: The Role of Gaussianity
The sharp MSE bound for the ℓ1-minimum-norm interpolator under isotropic Gaussian covariates is recovered via the geometry of symmetric Gaussian polytopes, without the convex Gaussian min-max theorem.