A universal sampling method for reconstructing signals with simple Fourier transforms
A universal sampling method for reconstructing signals with simple Fourier transforms
复制标题
一种通过简单傅里叶变换重建信号的通用采样方法
DOI：
10.1145/3313276.3316363
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
K. Krovacek
中科院分区：
文献类型：
--
作者：
I. Čižnár;A. Hoštacká;C. González;K. Krovacek
基于少量离散样本重构连续信号是科学和工程领域的一个基本问题。我们通常对具有“简单”傅立叶结构的信号感兴趣--例如，那些涉及有限范围内的频率、少量频率或几个频率块的频率--即，带宽受限、稀疏和多频带信号。更广泛地说，信号傅立叶功率谱的任何先验知识都可以限制其复杂性。直观地说，具有更高约束的傅立叶结构的信号需要更少的样本来重建。我们正式表明，这种直觉，粗略地说，一个连续的信号从一个给定的类可以近似重建使用的样本数量成比例的统计维数允许的功率谱的那一类。我们证明，在几乎所有的设置，这种自然的措施紧紧表征信号重建的样本复杂性。令人惊讶的是，我们还表明，一个通用的非均匀采样策略，可以实现任何类型的信号的最佳复杂性的对数因子。我们提出了一个有效的和一般的算法，用于恢复信号的采样。对于带宽受限和稀疏信号，我们的方法与最先进的方法相匹配，同时为更广泛的问题提供了第一个计算和样本有效的解决方案，包括一维的多频带信号重建和高斯过程回归任务。我们的工作是基于随机线性代数和约束傅立叶结构的信号重构问题之间的一种新的连接。我们扩展工具的基础上统计杠杆分数采样和基于列的矩阵重建的连续线性算子的信号重建问题中出现的近似。我们相信这些扩展是独立的利益，并作为一个基础，用于解决广泛的连续时间问题，使用随机方法。
Reconstructing continuous signals based on a small number of discrete samples is a fundamental problem across science and engineering. We are often interested in signals with "simple'' Fourier structure -- e.g., those involving frequencies within a bounded range, a small number of frequencies, or a few blocks of frequencies -- i.e., bandlimited, sparse, and multiband signals, respectively. More broadly, any prior knowledge on a signal's Fourier power spectrum can constrain its complexity. Intuitively, signals with more highly constrained Fourier structure require fewer samples to reconstruct. We formalize this intuition by showing that, roughly, a continuous signal from a given class can be approximately reconstructed using a number of samples proportional to the statistical dimension of the allowed power spectrum of that class. We prove that, in nearly all settings, this natural measure tightly characterizes the sample complexity of signal reconstruction. Surprisingly, we also show that, up to log factors, a universal non-uniform sampling strategy can achieve this optimal complexity for any class of signals. We present an efficient and general algorithm for recovering a signal from the samples taken. For bandlimited and sparse signals, our method matches the state-of-the-art, while providing the the first computationally and sample efficient solution to a broader range of problems, including multiband signal reconstruction and Gaussian process regression tasks in one dimension. Our work is based on a novel connection between randomized linear algebra and the problem of reconstructing signals with constrained Fourier structure. We extend tools based on statistical leverage score sampling and column-based matrix reconstruction to the approximation of continuous linear operators that arise in the signal reconstruction problem. We believe these extensions are of independent interest and serve as a foundation for tackling a broad range of continuous time problems using randomized methods.
DOI：
--
发表时间：
2017-11
期刊：
--
影响因子：
--
作者：
Xue Chen;Eric Price
通讯作者：
Xue Chen;Eric Price