Learning-based Compressive Subsampling

Abstract

The problem of recovering a structured signal $\mathbf{x}\in {\mathbb{C}}^p$ from a set of dimensionality-reduced linear measurements $\mathbf{b}=\mathbf{Ax}$ arises in a variety of applications, such as medical imaging, spectroscopy, Fourier optics, and computerized tomography. Due to computational and storage complexity or physical constraints imposed by the problem, the measurement matrix $\mathbf{A}\in {\mathbb{C}}^{n\times p}$ is often of the form $\mathbf{A}={\mathbf{P}}_{\Omega }\mathbf{\Psi }$ for some orthonormal basis matrix $\mathbf{\Psi }\in {\mathbb{C}}^{p\times p}$ and subsampling operator ${\mathbf{P}}_{\Omega }:{\mathbb{C}}^p\to {\mathbb{C}}^n$ that selects the rows indexed by $\Omega$. This raises the fundamental question of how best to choose the index set $\Omega$ in order to optimize the recovery performance. Previous approaches to addressing this question rely on non-uniform \emph{random} subsampling using application-specific knowledge of the structure of $\mathbf{x}$. In this paper, we instead take a principled learning-based approach in which a \emph{fixed} index set is chosen based on a set of training signals ${\mathbf{x}}_1,\dots ,{\mathbf{x}}_m$. We formulate combinatorial optimization problems seeking to maximize the energy captured in these signals in an average-case or worst-case sense, and we show that these can be efficiently solved either exactly or approximately via the identification of modularity and submodularity structures. We provide both deterministic and statistical theoretical guarantees showing how the resulting measurement matrices perform on signals differing from the training signals, and we provide numerical examples showing our approach to be effective on a variety of data sets.

Submitted to IEEE Journal on Selected Topics in Signal Processing

References in corpus (5)

• On asymptotic structure in compressed sensing
• Breaking the coherence barrier: A new theory for compressed sensing
• Energy-aware adaptive bi-Lipschitz embeddings
• A totally unimodular view of structured sparsity
• A Primal-Dual Algorithmic Framework for Constrained Convex Minimization

Cited by in corpus (10)

• Learning Space Partitions for Nearest Neighbor Search
• Discrete Signal Processing with Set Functions
• Optimization methods for MR image reconstruction (long version)
• Learning-based Support Estimation in Sublinear Time
• Optimizing full 3D SPARKLING trajectories for high-resolution T2*-weighted Magnetic Resonance Imaging
• Bayesian Optimization of Sampling Densities in MRI
• Augmented Lagrangian-Based Decomposition Methods with Non-Ergodic Optimal Rates
• InSPECtor: an end-to-end design framework for compressive pixelated hyperspectral instruments
• A Weighted Generalized Coherence Approach for Sensing Matrix Design
• Approximation Guarantees of Local Search Algorithms via Localizability of Set Functions