Generative models are the new sparsity?

This post is about my latests preprint with Dustin Mixon about signal denosing with generative networks.

Exploiting the structure of signals is a key idea in signal processing. For instance, natural images are known to be sparse on wavelets basis, and sparsity allows for recovering signals from few measurements (à la compressed sensing).

Generative models

The current trend, that takes advantage of the empirical success of deep learning, is to learn the structure of the signal first, and then exploit it. One way to represent the structure of signals is through a generative model, i.e. a parametrization of the data

$$G:\mathbb R^{n}\to \mathbb R^N \quad n \ll N$$

such that $G(\mathbb R^n)$ is close to the probability density of the data of interest.

Very impressive generative models have been produced with autoencoders and generative adversarial networks. However, it is a hard engineering task that involves tuning a lot of parameters and hours if not days of training neural networks with highly dedicated hardware. There doesn’t seem to exist a provable way to produce them successfully and it is not clear whether a reasonable data distribution is actually learned. But there exist very impressive examples, like this one from Google:

Inverse problems with generative models

Once you have a good generative model you can do amazing things with it. Bora, Jalal, Price and Dimakis from UT Austin empirically showed that they can solve the compressed sensing problem with 10 times fewer measurements than classical compressed sensing requires by replacing the sparse signal assumption by an appropriate generative model $G$. Their theoretical result shows that under mild hypothesis, if $y=Ax^* +\eta$ ($\eta$ is the noise), then

$$\begin{equation}z^*=\arg \min_{z} \|AG(z)-y\|_2 \quad (1) \end{equation}$$

satisfies $G(z^*)\approx x^*$.

However, it is not obvious that one can efficiently solve the optimization problem (1) since its landscape may a priori have many local minima. Recent work by Hand and Voroninski shows the optimization problem (1) can be solved using local methods provided that $G=(\rho \circ G_\ell)\circ \ldots \circ (\rho\circ G_1)$ where $\rho(t)=ReLU(t)=\max\{0,t\}$ and $G_i$ are matrices with i.i.d. Gaussian entries properly scaled. There is no learning in this setting.

SUNLayer and denoising with generative models

Motivated by both works, Dustin and I studied the simpler inverse problem of signal denoising with generative networks. The aim is to explain the phenomenon illustrated in the figure at the top of this post, i.e. given $y=G(x^*)+\eta$ a noisy signal then one can denoise by finding

$$z^*=\arg\min_z \|G(z) - y\|_2 \quad (2)$$

and the optimization problem can be solved by local methods like gradient descent (i.e. no spurious critical points).

In order to do that we consider a simpler model for a generative model inspired by neural networks. One layer of the SUNLayer (spherical uniform neural layer) is defined as

$$\begin{align} L_n: S^n &\to \mathscr{L}^2(S^n) \\ x &\mapsto \rho(\langle x, \cdot \rangle) \end{align}$$

where $\rho$ is an arbitrary activation function. We aim to answer what properties good activation functions need to have in order to allow denoising with local methods in this simplified model.

Consider the decomposition of $\rho$ in the Gegenbauer polynomials (choosing the correct normalization of the polynomials will be important). If $\rho(t)= \sum_{k=0}^\infty a_k \varphi_{k,n}(t),$ let $g_\rho(t)=\sum_{k=0}^\infty a_k^2 \varphi_{k,n}(t)$. Then the critical points of (2) are close to $\pm x^*$ if $\inf_{t\in[-1,1]} |g_\rho'(t)|$ is not too small in comparison with $\|\eta\|$.

Spherical harmonics

Squaring the coefficients in the Gegenbauer decomposition may look a priori mysterious. However, it shows up naturally due to the nice properties of the spherical harmonics. Consider the simplified setting when there is no noise. We have

$$\arg\min_{z}\|L_n(z) - L(x^*) \|^2= \arg \min_z \|L_n(z)\|^2 + \|L_n(x^*)\|^2 -2\langle L_n(z), L_n(x^*) \rangle$$

and $\|L_n(x)\|^2 = \int_{S^n} \rho(\langle x,y \rangle)^2 dy = c_{\rho, n}$ independent of $x$. Now we use the relationship between the Gegenbauer polynomials and the spherical harmonics (see chapter 2 of [Morimoto, Analytic functionals on the sphere, 1998]). Decompose $\mathscr{L}^2(S^n)=\oplus_{k=0}^\infty \mathcal H_n^k(S^n)$ where $\mathcal H_n^k(S^n)$ are the spherical harmonics (homogeneous polynomials in $n+1$ variables, of degree $k$, with Laplacian 0, restricted to the sphere). In particular $\mathcal H_n^k(S^n)$ is a finite dimensional vector space. Let $\{Y_1, \ldots Y_r\}$ a basis of $\mathcal H_n^k(S^n)$, then define the bilinear form $F_k(\sigma,\tau) = \sum_{s=1}^r Y_s(\sigma) \overline{Y_s(\tau)}$ for $\sigma, \tau \in S^n$.

It turns out $F_k$ is a reproducing kernel: $\langle F_k(x,\cdot), F_k(y,\cdot) \rangle = F_k(x,y)$ and it also satisfies that $F_k(x,y)$ only depends on the inner product $t:=\langle x, y\rangle$ and in fact $F_k(x,y)=\varphi_{k,n}(t)$. Then

$$\begin{align} \langle L_n(z), L_n(x^*) \rangle &= \langle \rho(\langle z,\cdot \rangle), \rho(\langle x^*,\cdot \rangle) \rangle \\ &= \langle \sum_{k=0}^\infty a_k \varphi_{k,n}(\langle z,\cdot \rangle), \sum_{k=0}^\infty a_k \varphi_{k,n}(\langle x^*,\cdot \rangle) \rangle \\ &= \langle \sum_{k=0}^\infty a_k F_k(z,\cdot), \sum_{k=0}^\infty a_k F_k(\langle x^*,\cdot) \rangle \\ &= \sum_{k=0}^\infty a_k^2\langle F_k(z,\cdot), F_k(\langle x^*,\cdot) \rangle \\ &= \sum_{k=0}^\infty a_k^2 \varphi_{n,k}(\langle z, x^*\rangle). \end{align}$$

Therefore $\arg\min_{z}\|L_n(z) - L(x^*) \|^2 = \arg\max_z \langle L_n(z), L_n(x^*) \rangle = \arg\max_z \sum_{k=0}^\infty a_k^2 \varphi_{n,k}(\langle z, x^*\rangle)$

and a simple computation shows that the only critical points are $z=\pm x^*$ if $g_\rho'(t)>0$ for all $t\in [-1,1]$. The analysis for the noisy case that we do in the paper is still simple but more interesting, and it involves considering tight frames in $\mathcal H^k_n(S^n)$.