...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Applied and Computational Harmonic Analysis >A sublinear algorithm for the recovery of signals with sparse Fourier transform when many samples are missing
【24h】

A sublinear algorithm for the recovery of signals with sparse Fourier transform when many samples are missing

机译：当缺少许多样本时使用稀疏傅里叶变换恢复信号的亚线性算法

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We present a sublinear randomized algorithm to compute a sparse Fourier transform for nonequispaced data of a special type. More precisely, we address the situation where a signal S is known to consist of N equispaced time samples, of which only L < N samples are available. If the ratio p = L/N is much smaller than 1, the available data typically look like nonequispaced samples, with little or no visible trace of the equispacing of the full set of N samples. We extend an approach for equispaced data that was presented in [J. Zou, A.C. Gilbert, M. Strauss, I. Daubechies, Theoretical and experimental analysis of a randomized algorithm for sparse Fourier transform analysis, J. Comput. Phys. 211 (2006) 572-595]; the extended algorithm reconstructs, from the incomplete data, a near-optimal B-term representation R with high probability 1 — δ, in time and space poly(B, log(N), log(1/δ), ε~(-1) ), such that ‖ S — R‖_2~2≤ (1 + ε) ‖S — R_(opt)~B‖_2~2, where R_(opt)~B is the optimal B-term Fourier representation of signal S. The sublinear poly (log N) time is compared to the superlinear O(L~(1+(d-1)/β) log L) time requirement of the present best known inverse nonequispaced fast Fourier transform (INFFT) algorithms, in the sense of weighted norm with the number of dimensions d and smoothness parameter β. Numerical experiments support the advantage of our algorithm in speed over other methods for sparse signals: it already outperforms the INFFT for large but realistic size N and works well even in the situation of a large percentage of missing data and in the presence of large noise.
机译：我们提出了一种亚线性随机算法，用于为特殊类型的非等距数据计算稀疏傅里叶变换。更准确地说，我们解决了信号S已知由N个等间隔时间样本组成的情况，其中只有L

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号