2018/07/23 by Andoni, Alexandr, Kamma, Lior, Krauthgamer, Robert +1
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1807.08478
We introduce a batch version of sparse recovery, where the goal is to report a sequence of vectors A1',…,Am' ∈ ℝn that estimate unknown signals A1,…,Am ∈ ℝn using a few linear measurements, each involving exactly one signal vector, under an assumption of average sparsity. More precisely, we want to have \newline (1) ∑j ∈ [m]‖Aj- Aj'‖pp ≤ C ⋅ min \ ∑j ∈ [m]‖Aj - Aj^*‖pp \ for predetermined constants C ≥ 1 and p, where the minimum is over all A1^*,…,Am^*∈ℝn that are k-sparse on average. We assume k is given as input, and ask for the minimal number of measurements required to satisfy (1). The special case m=1 is known as stable sparse recovery and has been studied extensively. We resolve the question for p =1 up to polylogarithmic factors, by presenting a randomized adaptive scheme that performs O(km) measurements and with high probability has output satisfying (1), for arbitrarily small C > 1. Finally, we show that adaptivity is necessary for every non-trivial scheme.