Greedy-type sparse recovery from heavy-tailed measurements

Tim Fuchs, Felix Krahmer, Richard Kueng

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

Recovering a s-sparse signal vector x in Cn from a comparably small number of measurements y: = (Ax) in Cm is the underlying challenge of compressed sensing. By now, a variety of efficient greedy algorithms has been established and strong recovery guarantees have been proven for random measurement matrices A in Cm × n.However, they require a strong concentration of AAx around its mean x (in particular, the Restricted Isometry Property), which is generally not fulfilled for heavy-tailed matrices. In order to overcome this issue and even cover applications where only limited knowledge about the distribution of the measurements matrix is known, we suggest substituting AAx by a median-of-means estimator.In the following, we present an adapted greedy algorithm, based on median-of-means, and prove that it can recover any s-sparse unit vector x in Cn up to a l2-error | x - x |_2 < in with high probability, while only requiring a bound on the fourth moment of the entries of A. The sample complexity is of the order \mathcalO\left( s\left( n\left( \frac1 in ) )\left( \frac1 in ) ).

Original languageEnglish
Title of host publication2023 International Conference on Sampling Theory and Applications, SampTA 2023
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9798350328851
DOIs
StatePublished - 2023
Externally publishedYes
Event2023 International Conference on Sampling Theory and Applications, SampTA 2023 - New Haven, United States
Duration: 10 Jul 202314 Jul 2023

Publication series

Name2023 International Conference on Sampling Theory and Applications, SampTA 2023

Conference

Conference2023 International Conference on Sampling Theory and Applications, SampTA 2023
Country/TerritoryUnited States
CityNew Haven
Period10/07/2314/07/23

Fingerprint

Dive into the research topics of 'Greedy-type sparse recovery from heavy-tailed measurements'. Together they form a unique fingerprint.

Cite this