Fetching the paper…

Reading the bibliography…

2019

Lower Bounds for Compressed Sensing with Generative Models

Kamath, Akshay, Karmalkar, Sushrut, Price, Eric

Original
PDF
Post on X

Understand

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" is represented by sparsity in some known basis.
Inspired by the success of deep learning in modeling images, recent work starting with~\cite{BJPD17} has instead considered structure to come from a generative model $G: \mathbb{R}^k \to \mathbb{R}^n$.
We present two results establishing the difficulty of this latter task, showing that existing bounds are tight.

Lower Bounds for Compressed Sensing with Generative Models · Around

Built on

On data structures and asymmetric communication complexity
Peter Bro Miltersen, Noam Nisan, Shmuel Safra, and Avi Wigderson · 1998
Earlier work this paper cites.
Stable signal recovery from incomplete and inaccurate measurements
E. J. Candès, J. Romberg, and T. Tao · 2006
Earlier work this paper cites.
Constructing small-bias sets from algebraic-geometric codes
Avraham Ben-Aroya and Amnon Ta-Shma · 2009
Earlier work this paper cites.

Similar

Lower bounds for sparse recovery
K. Do Ba, P. Indyk, E. Price, and D. Woodruff · 2010
Cited alongside, same era.
Generative adversarial nets
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio · 2014
Cited alongside, same era.
Auto-encoding variational bayes
Diederik P. Kingma and Max Welling · 2014
Cited alongside, same era.

Then

Compressed sensing using generative models
Ashish Bora, Ajil Jalal, Eric Price, and Alexandros G. Dimakis · 2017
Later among the works it cites.
Information-theoretic lower bounds for compressive sensing with generative models, 2019
Zhaoqiang Liu and Jonathan Scarlett · 2019
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…