1 Introduction↩︎

In compressed sensing [2], the goal is to reconstruct a high-dimensional signal \(\mathbf{x} \in \mathbb{R}^n\) from a noisy low-dimensional linear transformation of it, \(\mathbf{y} = \mathbf{M}\mathbf{x} + \mathbf{w} \in \mathbb{R}^l,\, l < n\). Even in the absence of noise, the reconstruction would not be possible without a further assumption of signal structure, i.e., some restriction of the possible values of \(\mathbf{x}\). In early works in compressed sensing, the signal structure was encoded via sparsity, or sparsity with respect to a dictionary. A sufficient condition on the measurement matrix \(\mathbf{M}\) that enables robust recovery is the celebrated Restricted Isometry Property (RIP) [3]. Intriguingly, all known algorithms for certifying RIP either are computationally intractable or only function in the parameter regimes which are highly suboptimal [4], but a sub-gaussian measurement matrix with independent rows satisfies the RIP with high probability in near optimal parameter regimes [5].

More recently, compressed sensing ideas have been generalized to allow the signal structure to be almost arbitrary, encoded as a subset \(T \subset \mathbb{R}^n\), provided that the measurements are appropriately random. Gaussian measurement matrices are rotationally invariant [6], which allows them to be universally effective for general compressed sensing. This was proven using [7], [8] or generalizing [9]–[11] Gordon’s theorem [12], and also through a foundational result in conic geometry [13]. Sub-gaussian matrices, as defined later, are essentially the largest class of matrices that approximately satisfy rotation invariance, and also enjoy universal guarantees, although with different proof techniques relying on chaining arguments [1], [14], [15]. We also note a few results outside of the Gaussian or sub-gaussian framework: [16]–[19].

The recent results of [1] extend previous theory by allowing the measurement matrix to take the form \(\mathbf{M} = \mathbf{B}\mathbf{A}\) with arbitrary \(\mathbf{B}\) and sub-gaussian \(\mathbf{A}\) with independent rows. They prove a general restricted isometry property, thereby giving basic signal recovery guarantees for measurement matrices with dependent rows. This random model is compelling because real-data measurement matrices often have highly variable singular values, but sub-gaussian matrices with independent rows typically have nearly uniform singular values. In fact, under mild assumptions, the singular values of \(\mathbf{B A}\) concentrate around the singular values of \(\mathbf{B}\) (after rescaling), and so, one may target any singular value vector by adjusting the singular values of \(\mathbf{B}\). We build upon the work of [1] to show accurate signal recovery by the generalized Lasso, even in the presence of inexact optimization and/or a mismatch in the signal structure. We believe this provides the first general compressed sensing guarantees allowing any two of the following three items simultaneously (we allow all three): (i) the measurement matrix need not have independent rows, (ii) the signal may be estimated by generalized Lasso, but without exact optimization, and (iii) the signal is allowed to be only approximately structured, i.e. close to the structure set and not belonging to it. The improved dependence on the sub-gaussian parameter of the measurement matrix in [1] is reflected in our work as well.

Items (ii) and (iii) above make our framework well-suited to the setting in which the signal structure is the range of a neural network. Indeed, in recent years, it has been shown empirically that learning the appropriate signal structure by fitting it to the range of a neural network can be much more effective than using a predetermined structure such as sparsity [20]–[22]. In this case, one assumes that \(T\) is the range of a generative model \(G: \mathbb{R}^k \rightarrow \mathbb{R}^n\) which is already trained. While training often approximates the signal structure well, any new signal outside of the training set will typically be close, but not in \(T\); thereby necessitating item (iii). The standard method of estimating \(\boldsymbol{x}\) is to find the restricted least squares fit, i.e., to let the estimate \(\mathbf{\hat{x}}\) be the solution to the program, sometimes called generalized Lasso: \[ \label{program} \mathrm{minimize} \; ||\mathbf{y} - \mathbf{M}\mathbf{x}'||_2^2 \quad \mathrm{s.t.} \; \mathbf{x}' \in T.\tag{1}\] Since \(T = \mathrm{ran}(G)\) is non-convex, and no convex relaxation of such a program is known in general, typical gradient-descent-based algorithms would not be guaranteed to approach a global minimum; thereby necessitating item (ii). Our theory requires an upper bound of the Gaussian mean width of \({(T-T) \cap \mathbb{S}^{n-1}}\), which we give in Proposition 2 below; we believe this is novel.

2 Main Results↩︎

2.1 Problem Setup↩︎

Recall that a random variable \(Z\) is called sub-gaussian, if its tail probability is dominated by that of a Gaussian random variable. An equivalent rigorous definition requires the sub-gaussian norm to be finite: \(||Z||_{\psi_2} \mathrel{\vcenter{:}}= \inf \big\{t > 0 \, \big | \; \mathbb{E}(Z^2/t^2) \leq 2 \big\} < \infty\). A random vector \(\mathbf{v} \in \mathbb{R}^n\) is sub-gaussian, if all of its one-dimensional marginals are sub-gaussian random variables. Mathematically, if \(||\langle \mathbf{\theta}, \mathbf{v} \rangle||_{\psi_2}\) is finite for all \(\mathbf{\theta} \in \mathbb{S}^{n-1}\), we define \(||\mathbf{v}||_{\psi_2} \mathrel{\vcenter{:}}= \sup_{\mathbf{\theta} \in \mathbb{S}^{n-1}} ||\langle \mathbf{\theta}, \mathbf{v} \rangle||_{\psi_2}\).

We will consider a random matrix \(\mathbf{A} \in \mathbb{R}^{m \times n}\) whose rows \(\{\mathbf{a}_1^\top, \cdots, \mathbf{a}_m^\top\}\) are statistically independent, mean-zero (\(\mathbb{E}\mathbf{a}_i = \mathbf{0}\)), isotropic (\(\mathbb{E} \mathbf{a}_i \mathbf{a}_i^\top = \mathbf{I}_n\)), and sub-gaussian with parameter \(K\) (\(||\mathbf{a}_i||_{\psi_2} \leq K\)). We let the measurement matrix be the product \(\mathbf{B}\mathbf{A}\), where \(\mathbf{B} \in \mathbb{R}^{l \times m}\) is arbitrary. In other words, we let every row of our measurement matrix be an arbitrary linear combination of \(\mathbf{a}_1^\top, \cdots, \mathbf{a}_m^\top\). Our goal is to determine the criteria that \(\mathbf{B}\), \(\mathbf{A}\), and the structure set \(T\) must satisfy for accurate recovery to be possible. Informally, one requires \(\mathbf{B}\) to be far from low-rank, otherwise, the number of independent effective measurements would not be sufficient. An appropriate quantity is the stable rank defined as \[\mathrm{sr}(\mathbf{B}) \mathrel{\vcenter{:}}= \frac{||\mathbf{B}||_F^2}{||\mathbf{B}||^2} = \frac{\sum_{i=1}^{\mathrm{rank}(\mathbf{B})} \sigma_i^2}{\max_{i} \sigma_i^2} \leq \mathrm{rank}(\mathbf{B}),\] where \(\sigma_i\)’s are the singular values of \(\mathbf{B}\). The main advantage of this definition over rank itself is that it is robust to the small non-zero singular values that increase the rank but do not contribute to an effective measurement, hence the name stable rank. Furthermore, one requires \(T\) to be small in some sense, ideally not to intersect the null space of \(\mathbf{M} = \mathbf{B}\mathbf{A}\). A useful notion of size is the Gaussian mean width defined as \[w(T) \mathrel{\vcenter{:}}= \mathbb{E} \sup_{\mathbf{v} \in T} \langle \mathbf{v}, \mathbf{g} \rangle,\] where the expectation is calculated with respect to \(\mathbf{g} \sim \mathcal{N}(\mathbf{0}, \mathbf{I}_n)\). The reader may consult [23] for some basic properties of Gaussian mean width. The following theorem gives the desired estimation bound.

2.2 Main Theorem↩︎

There are three sources of error present here: the additive noise \(\mathbf{w}\), the inaccuracy in optimization \(\epsilon\), and the model mismatch, i.e., \(\mathbf{x}\) not exactly belonging to \(T\). Note that \({\mathrm{sr}(\mathbf{B}) \leq \mathrm{rank}(\mathbf{B}) \leq \min(l,m)}\), so basically the effective number of measurements is bounded by the number of underlying independent measurements \(m\). When \(\mathbf{B}\) is a multiple of identity, the equality case \(\mathrm{sr}(\mathbf{B}) = m\) occurs.

What happens if we have more effective measurements than needed? The energy of the noise that appears in the total error in (?? ) is decreased by the oversampling factor \({\mathrm{sr}(\mathbf{B})}/w^2(T')\). In other words, if we have some control over the measurement matrix, then we are able to denoise the original signal by increasing \(\mathrm{sr}(\mathbf{B})\). In case of \(\mathbf{B} = \mathbf{I}_m\), this simply means increasing the number of measurements \(m\). This denoising effect is well known for stochastic noise, but we believe that it had previously been shown only for non-random noise under the assumption of a Gaussian measurement matrix, as in [11]. We note, it is important here that the noise is fixed i.e., not chosen adversarially depending on the realization of \(\mathbf{A}\).

3 Application on Generative Neural Networks↩︎

Due to the success of deep generative neural networks to learn complex structures, recent works on compressed sensing have considered generative priors instead of the traditional sparsity [20]. While some works require the trained network \(G: \mathbb{R}^k \rightarrow \mathbb{R}^n\) to be \(L\)-Lipschitz [20] and prove that \(\mathcal{O}(k \log L)\) number of measurements would suffice for a recovery guarantee, a drawback of such analysis is that the Lipschitz constant of the network cannot be calculated solely based on its architecture. Here we present a different approach: we give an upper bound of the Gaussian mean width of \(T' = \big(\mathrm{ran}(G) - \mathrm{ran}(G)\big) \cap \mathbb{S}^{n-1}\), which only depends on the hyperparameters of the model. Then we apply Theorem 1 to achieve a recovery guarantee for compressed sensing with generative priors.

3.1 GNN and Guassian Mean Width↩︎

A \(d\)-layer GNN with ReLU activation function is a function \(G: \mathbb{R}^k \rightarrow \mathbb{R}^n\) of the form \[\label{gnn} G(\mathbf{z}) = \sigma(\mathbf{A}_d \sigma(\mathbf{A}_{d-1} \sigma( \dots \mathbf{A}_2 \sigma (\mathbf{A}_1 \mathbf{z}) \dots ))),\tag{2}\] where \(\sigma(\cdot) = \max(\cdot, 0)\) is applied entrywise and \(\mathbf{A}_i \in \mathbb{R}^{p_i \times p_{i-1}}\), \(p_0 = k\), and \(p_d = n\). The weight matrices \(\mathbf{A}_i\) are sometimes assumed to have iid Gaussian entries, however, our analysis puts no requirement on \(\mathbf{A}_i\). To bound the Gaussian mean width of \(\mathrm{ran}(G)\), we first show that the set is contained in a union of subspaces with minimal count. Note that the choice of ReLU activation function is not essential to what follows, and any piecewise linear function with only two pieces (e.g. leaky ReLU) could be substituted. Similar counting arguments have appeared in various theoretical works on expansive neural nets.

3.2 Compressed Sensing with Generative Priors↩︎

The effective number of measurements required for any recovery algorithm to be successful is \(\mathcal{O} \big( w^2(T') \big) = \mathcal{O} \big( kd \log (p'/k) \big)\). Typically, a GNN is assumed to be expansive, that is \(k = p_0 \leq p_1 \leq \cdots \leq p_d = n\). Thus, \(k \leq p' \leq n\), which slightly improves \(\mathcal{O}(kd \log n)\) in [20]. Moreover, by combining Theorem 1 and Proposition 2, we present a recovery guarantee for the compressed sensing with generative priors that not only allows for a much broader range of measurement matrices, but also demonstrates the dependence on their parameters.

Our analysis improves upon the best known results in three ways: Firstly, our result suggests a denoising behaviour as the number of measurements (or the stable rank of \(\mathbf{B}\)) increases, even though the noise is not assumed to be random. Intuitively, one expects a smaller error bound associated with less compression, and our theory highlights this dependence. In contrast, the bound in [20] shows constant dependence on the noise level, the optimization margin, and the model mismatch, regardless of the number of measurements. Secondly, we improve the logarithmic factor in the compression bound, i.e. we need \(\mathcal{O}(kd \log(p'/k)) \leq \mathcal{O}(kd \log(n/k))\) effective measurements, rather than \(\mathcal{O}(kd \log n)\). This was also available to the authors of [20], had they used a tighter inequality in proof of Lemma 8.3. Finally, we require milder conditions for the measurement matrix, allowing for a fixed mixing matrix to create dependence among the rows. This improvement is based on the geometry-preserving properties discussed in [1].

4 Summary↩︎

We achieve an estimation bound for the reconstruction of structured signals using noisy and dependent random measurements. The generality of our model enables its application on the non-traditional structure sets such as the range of a ReLU generative neural network. We believe that this is the first general compressed sensing result that specializes well to the generative structure. Whether a similar recovery guarantee is obtainable for GNNs with other activation functions (e.g. sigmoid or tanh), remains an open question.

5 Appendix↩︎

References↩︎