Efficient Sketches for the Set Query Problem
Eric Price · 2011
We develop an algorithm for estimating the values of a vector x ∊ ℝn over a support S of size k from a randomized sparse binary linear sketch Ax of size O(k). Given Ax and S, we can recover x′ with ‖x′ − xs‖2 < ε ‖x − xs‖2 with probability at least 1 − k−Ω(1). The recovery takes O(k) time.