Open Collections

Abstract

In~\cite{bora2017compressed}, a mathematical framework was developed for compressed sensing guarantees in the setting where the measurement matrix is Gaussian and the signal structure is the range of a generative neural network (GNN). The problem of compressed sensing with GNNs has since been extensively analyzed when the measurement matrix and/or network weights follow a subgaussian distribution. In this thesis, we move beyond the subgaussian assumption to measurement matrices that are derived by sampling uniformly at random rows of a unitary matrix (including sub-sampled Fourier measurements as a special case). Specifically, we prove the first known restricted isometry guarantee for generative compressed sensing (GCS) with \emph{sub-sampled isometries}, and provide recovery bounds with nearly order-optimal sample complexity, addressing an open problem of~\cite[p.~10]{scarlett2022theoretical}. Recovery efficacy is characterized by the \emph{coherence}, a new parameter, which measures the interplay between the range of the network and the measurement matrix. Our approach relies on subspace counting arguments and ideas central to high-dimensional probability. Furthermore, we propose a regularization strategy for training GNNs to have favourable coherence with the measurement operator. We provide compelling numerical simulations that support this regularized training strategy: our strategy yields low coherence networks that require fewer measurements for signal recovery. This, together with our theoretical results, supports coherence as a natural quantity for characterizing GCS with sub-sampled isometries.