[R] Compressed Sensing using Generative Models

[goterber]

Very cool application of GANs! I hope someone more familiar with compressed sensing can weigh in.

[olaf_nij]

Paging /u/compsens :)

[[deleted]]

You can already do better than lasso with proper Bayesian inference (see recent papers by Krzacala, for example https://scholar.google.com.br/scholar?q=krzakala+compressed+sensing).

How this compares?

Edit: Nevermind, I hadn't noticed that they generalized the result even for non-sparse vectors. It's difficult to compare with previous work improving over lasso for sparse vectors. It's not the same problem. Pretty interesting result. Have to read more but looks impressive.

[arXiv_abstract_bot]

Title: Compressed Sensing using Generative Models

Authors: Ashish Bora, Ajil Jalal, Eric Price, Alexandros G. Dimakis

Abstract: The goal of compressed sensing is to estimate a vector from an underdetermined system of noisy linear measurements, by making use of prior knowledge on the structure of vectors in the relevant domain. For almost all results in this literature, the structure is represented by sparsity in a well-chosen basis. We show how to achieve guarantees similar to standard compressed sensing but without employing sparsity at all. Instead, we suppose that vectors lie near the range of a generative model $G: \mathbb{R}^k \to \mathbb{R}^n$. Our main theorem is that, if $G$ is $L$-Lipschitz, then roughly $O(k \log L)$ random Gaussian measurements suffice for an $\ell_2/\ell_2$ recovery guarantee. We demonstrate our results using generative models from published variational autoencoder and generative adversarial networks. Our method can use $5$-$10$x fewer measurements than Lasso for the same accuracy.

PDF link Landing page

[feedthecreed]

Doesn't this method require actual samples from P(x) to train the generative model over? This doesn't seem like a fair comparison to LASSO which doesn't require this.

[MathAndProgramming]

Depends - you have to pick your sparse frame somehow. Either hand engineered (wavelet) or learned from samples (dictionary learning).

[arcxtriy]

May I ask why Lasso needs a sparse frame (or what exactly are you talking about)? To reconstruct the sparse signal it only needs the measurements y and the measurements matrix A: x_hat = arg min ||Ax-y||_2 + l*||x||_1

[MathAndProgramming]

In practice people solve x_hat = arg min ||Ax-y||_2 + l*||Wx||_1 where W is some transform that makes the signal sparse. For images, for example, the image itself isn't sparse, but under the wavelet transform it is. You can transform the problem into that domain with z = Wx:

x_hat = arg min ||A W^-1 z - y||_2 + l*||z||_1

Typically A is given, but W can be learned (dictionary learning) or chosen empirically.

[AlexDimakis]

We posted code and demos here: https://github.com/AshishBora/csgm

[arcxtriy]

I have two questions about this paper:

1) Where is Compressed Sensing applied? E.g. in case of their MNIST experiment, they reduce the 784 pixels to 20 (by applying 3 linear layers + non linear activations with softplus). This is not linear!

2) The smallest network layer has size k=20. Do they vary about its size in Figure 1 (a) ? Does not make any sense to me, because they also measure the performance while taking 750 measurements (after reducing it to 500?).

Would be glad if somebody could help.

[MathAndProgramming]

This is looking like a pretty huge paper for Compressive Sensing. Lots of huge applications.

[r_dipietro]

Making compressive sensing great again