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 $x$ from a limited number of noisy linear measurements $y\approx Ax$. In traditional compressed sensing, "structure"…