118 citations · 187 across the 9 of their papers we have counts for
9 papers
For-all Sparse Recovery in Near-Optimal Time
Anna C. Gilbert, Yi Li, Ely Porat +1
An approximate sparse recovery system in norm consists of parameters , , , an -by- measurement , and a recovery algorithm, . Given a vector,…
L2/L2-foreach sparse recovery with low risk
Anna C. Gilbert, Hung Q. Ngo, Ely Porat +2
In this paper, we consider the "foreach" sparse recovery problem with failure probability . The goal of which is to design a distribution over matrices and a de…
Sublinear Time, Measurement-Optimal, Sparse Recovery For All
Ely Porat, Martin J. Strauss
An approximate sparse recovery system in ell_1 norm formally consists of parameters N, k, epsilon an m-by-N measurement matrix, Phi, and a decoding algorithm, D. Given a vector, x,…
Approximate Sparse Recovery: Optimizing Time and Measurements
Anna C. Gilbert, Yi Li, Ely Porat +1
An approximate sparse recovery system consists of parameters , an -by- measurement matrix, , and a decoding algorithm, . Given a vector, , the system…
Combining geometry and combinatorics: A unified approach to sparse signal recovery
R. Berinde, A. C. Gilbert, P. Indyk +2
There are two main algorithmic approaches to sparse signal recovery: geometric and combinatorial. The geometric approach starts with a geometric constraint on the measurement matri…
Private Approximate Heavy Hitters
Martin J. Strauss, Xuan Zheng
We consider the problem of private computation of approximate Heavy Hitters. Alice and Bob each hold a vector and, in the vector sum, they want to find the B largest values along w…