Beyond Independent Measurements: General Compressed Sensing with GNN Application

We consider the problem of recovering a structured signal x ∈ ℝn from noisy linear observations y =M x+w. The measurement matrix is modeled as M = BA, where B ∈ ℝl × m is arbitrary and A ∈ ℝm × n has independent sub-gaussian rows. By varying B, and the sub-gaussian distribution of A, this gives a family of measurement matrices which may have heavy tails, dependent rows and columns, and singular values with a large dynamic range. When the structure is given as a possibly non-convex cone T subset ℝn, an approximate empirical risk minimizer is proven to be a robust estimator if the effective number of measurements is sufficient, even in the presence of a model mismatch. In classical compressed sensing with independent (sub-)gaussian measurements, one asks how many measurements are needed to recover x? In our setting, however, the effective number of measurements depends on the properties of B. We show that the effective rank of B may be used as a surrogate for the number of measurements, and if this exceeds the squared Gaussian mean width of (T-T) cap mathbbSn-1, then accurate recovery is guaranteed. Furthermore, we examine the special case of generative priors in detail, that is when x lies close to T = ran(G) and G: ℝk rightarrow ℝn is a Generative Neural Network (GNN) with ReLU activation functions. Our work relies on a recent result in random matrix theory by Jeong, Li, Plan, and Yilmaz arXiv:2001.10631. .