Towards Data-Driven Guarantees for Sparse Signal Recovery

The recovery of sparse signals from linear measurements can typically be formulated as quadratic optimization problems while adhering to the sparsity constraint. We present a novel approach to sparse signal recovery, generally referred to as MERIT, that provides data-aware guarantees for the obtained solutions. Specifically, we show that in case theoretical guarantees exist, our data-driven results match and revalidate them. Furthermore, we showcase the potential to approximate the desired sparse solutions with high precision across a variety of other scenarios, particularly under noisy measurements. In this paper, for the first time in the literature, we introduce the concept of the approximation ratio and its corresponding lower bound, which we term the sub-optimality guarantee for sparse signal recovery. This framework quantifies the deviation between the relaxed problem and the original problem when both the signal and the sampling matrix are held constant. Data-driven approaches demonstrate their potential utility, particularly when there is a lack of information on the statistical properties of measurements, and one seeks guarantees tailored to specific cases.