Timezone: »

 
Poster
On the Power of Compressed Sensing with Generative Models
Akshay Kamath · Eric Price · Sushrut Karmalkar

Thu Jul 16 05:00 PM -- 05:45 PM & Fri Jul 17 04:00 AM -- 04:45 AM (PDT) @
in Poster Session 49 »
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 Bora-Jalal-Price-Dimakis'17 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 and strength of this latter task, showing that existing bounds are tight: First, we provide a lower bound matching the Bora et.al upper bound for compressed sensing with $L$-Lipschitz generative models $G$ which holds even for the more relaxed goal of \emph{non-uniform} recovery. Second, we show that generative models generalize sparsity as a representation of structure by constructing a ReLU-based neural network with $2$ hidden layers and $O(n)$ activations per layer whose range is precisely the set of all $k$-sparse vectors.
Keywords: Deep Generative Models · Sparsity and Compressed Sensing · Optimization - General

Author Information

Akshay Kamath (University of Texas at Austin)
Eric Price (UT-Austin)
Sushrut Karmalkar (University of Texas at Austin)

More from the Same Authors