2018/06/11 by Felix Krahmer, Krahmer, Felix, Christian Kümmerle +3 · 3 citations
Computer Science · Engineering · Mathematics · #15A52 #46B09 #46B20 #52A22 #65K10 #Distributed Sensor Networks and Detection Algorithms #FOS: Mathematics #Functional Analysis (math.FA) #Microwave Imaging and Scattering Analysis #Optimization and Control (math.OC) #Probability (math.PR) #Sparse and Compressive Sensing Techniques #math.FA #math.OC #math.PR #msc:15A52 #msc:46B09 #msc:46B20 #msc:52A22 #msc:65K10
paper · pdf · doi:10.48550/arxiv.1806.04261
22 pages, 2 figures
arxiv created 2018/06/11 · openalex publication_date 2018/06/11 · arxiv updated 2018/06/13 · openalex created_date 2018/06/21 · openalex updated_date 2026/07/28
For a large class of random matrices A with i.i.d. entries we show that the ℓ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 ℓ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.