1.9k citations · 2.8k across the 40 of their papers we have counts for
4 papers · 2 filters
Lower Bounds for Compressed Sensing with Generative Models
Akshay Kamath, Sushrut Karmalkar, Eric Price
The goal of compressed sensing is to learn a structured signal from a limited number of noisy linear measurements . In traditional compressed sensing, "structure"…
Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filtering
Ilias Diakonikolas, Sushrut Karmalkar, Daniel Kane +2
We study high-dimensional sparse estimation tasks in a robust setting where a constant fraction of the dataset is adversarially corrupted. Specifically, we focus on the fundamental…
Separations and Equivalences between Turnstile Streaming and Linear Sketching
John Kallaugher, Eric Price
A longstanding observation, which was partially proven in \cite{LNW14,AHLW16}, is that any turnstile streaming algorithm can be implemented as a linear sketch (the reverse is trivi…
Estimating the Frequency of a Clustered Signal
Xue Chen, Eric Price
We consider the problem of locating a signal whose frequencies are "off grid" and clustered in a narrow band. Given noisy sample access to a function with Fourier spectrum i…