• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Information Sciences and Systems, 2009. CISS 2009 >Simple deterministically constructible RIP matrices with sublinear fourier sampling requirements
【24h】

Simple deterministically constructible RIP matrices with sublinear fourier sampling requirements

机译：具有亚线性傅立叶采样要求的简单可确定性构造的RIP矩阵

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We present a deterministic number theoretic construction for matrices with the restricted isometry property (RIP). Furthermore, we show that the number theoretic properties of our RIP matrices allow their products with discrete Fourier transform (DFT) matrices to be well approximated via a few highly sparse matrix multiplications. Hence, our RIP matrices may be approximately multiplied by the DFT of any input vector in sublinear-time by reading only a small fraction of its entries. As a consequence, we obtain small deterministic sample sets which are guaranteed to allow the recovery of near-optimal sparse Fourier representations for all periodic functions having an integrable second derivative over a single period. Explicit bounds are provided for the sizes of our RIP matrices, the sizes of their associated sublinear Fourier sampling sets, and the errors incurred by quickly approximating their products with DFT matrices. The Fourier sampling requirements obtained herein improve on previous deterministic Fourier sampling results in [1], [2].
机译：我们提出了具有受限等距特性（RIP）的矩阵的确定性数论构造。此外，我们表明，RIP矩阵的数论性质使它们的离散傅里叶变换（DFT）矩阵乘积可以通过一些高度稀疏的矩阵乘法很好地近似。因此，通过仅读取其项的一小部分，我们的RIP矩阵可以在亚线性时间内近似乘以任何输入向量的DFT。结果，我们获得了小的确定性样本集，这些样本集可保证允许在单个周期内恢复具有可积分二阶导数的所有周期函数的接近最佳的稀疏傅里叶表示。我们为RIP矩阵的大小，与之相关的亚线性傅里叶采样集的大小，以及通过DFT矩阵快速近似其乘积而引起的误差，提供了明确的界限。本文获得的傅立叶采样要求比[1]，[2]中先前的确定性傅立叶采样结果有所改善。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号