University of British Columbia
A sparsity-free compressed sensing theory with applications in generative model recovery
Abstract
dc:descriptionWe study the problem of reconstructing a high-dimensional signal x∈ℝⁿ from a low-dimensional noisy linear measurement y=Mx+e∈ℝˡ, assuming x admits a certain structure. We model the measurement matrix as M=BA, with arbitrary B∈ℝˡˣᵐ and sub-gaussian A∈ℝᵐˣⁿ; therefore allowing for a family of random measurement matrices which may have heavy tails, dependent rows and columns, and a large dynamic range for the singular values. The structure is either given as a non-convex cone T⊂ℝⁿ, or is induced via minimizing a given convex function f(·). We prove, in both cases, that an approximate empirical risk minimizer robustly recovers the signal if the effective number of measurements is sufficient, even in the presence of a model mismatch. While in classical compressed sensing the number of independent (sub)-gaussian measurements regulates the possibility of a robust reconstruction, here in our setting the effective number of measurements depends on the properties of B. We show that, in this model, the stable rank of B indicates the effective number of measurements, and an accurate recovery is guaranteed whenever it exceeds the effective dimension of the structure set. We apply our results to the special case of generative priors, i.e. when x is close to the range of a Generative Neural Network (GNN) with ReLU activation functions. Also, if the GNN has random weights in the last layer, our theory allows a partial Fourier measurement matrix, thus taking the first step in a theoretical analysis of compressed sensing MRI with GNN. Our work relies on a recent result in random matrix theory by Jeong, Li, Plan, and Yilmaz.
Degree
thesis:*- Name thesis:degree_name
- Master of Science - MSc
- Level thesis:degree_level
- master's
- Discipline thesis:degree_discipline
- Mathematics
- Grantor dc:publisher
- University of British Columbia
- Year dc:date
- 2022
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Naderi, Alireza
- Contributors dc:contributor
-
- Plan, Yaniv
Rights
dc:rights- Statement dc:rights
-
- Attribution-NonCommercial-NoDerivatives 4.0 International
- Language dc:language
- eng
Identifiers
dc:identifier.*- Handle dc:identifier
- http://hdl.handle.net/2429/81286