The problem of recovering a structured signal $\mathbf{x} \in \mathbb{C}^p$
from a set of dimensionality-reduced linear measurements $\mathbf{b} = \mathbf
{A}\mathbf {x}$ 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}\boldsymbol{\Psi}$ for some orthonormal
basis matrix $\boldsymbol{\Psi}\in \mathbb{C}^{p \times p}$ and subsampling
operator $\mathbf{P}_{\Omega}: \mathbb{C}^{p} \rightarrow \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,\dotsc,\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.

该研究提出了一种基于学习的方法来选择优化恢复性能的固定索引集，通过解决组合优化问题最大化能量捕获。结果表明，该方法在各种数据集上都是有效的。