Greedy-Type Sparse Recovery From Heavy-Tailed Measurements

MCML Authors

Felix Krahmer

Prof. Dr.

Principal Investigator

Optimization & Data Analysis

Abstract

Recovering a s-sparse signal vector x∈Cn from a comparably small number of measurements y:=(Ax)∈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∈Cm×n.However, they require a strong concentration of A ∗ Ax 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 A ∗ Ax 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∈Cn up to a l 2 -error ∥x−x^∥2<∈ with high probability, while only requiring a bound on the fourth moment of the entries of A. The sample complexity is of the order O(slog(nlog(1∈))log(1∈)).

inproceedings

---

SampTA 2023

14th International Conference on Sampling Theory and Applications. Yale, CT, USA, Jul 10-14, 2023.

---

Authors

T. Fuchs • F. Krahmer • R. Kueng

---

Links

DOI

---

Research Area

 A2 | Mathematical Foundations