...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Information Theory, IEEE Transactions on >Approximation Algorithms for Model-Based Compressive Sensing
【24h】

Approximation Algorithms for Model-Based Compressive Sensing

机译：基于模型的压缩感知的近似算法

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

摘要

Compressive sensing (CS) states that a sparse signal can be recovered from a small number of linear measurements, and that this recovery can be performed efficiently in polynomial time. The framework of model-based CS (model-CS) leverages additional structure in the signal and provides new recovery schemes that can reduce the number of measurements even further. This idea has led to measurement-efficient recovery schemes for a variety of signal models. However, for any given model, model-CS requires an algorithm that solves the model-projection problem: given a query signal, report the signal in the model that is closest to the query signal. Often, this optimization can be computationally very expensive. Moreover, an approximation algorithm is not sufficient for this optimization to provably succeed. As a result, the model-projection problem poses a fundamental obstacle for extending model-CS to many interesting classes of models. In this paper, we introduce a new framework that we call approximation-tolerant model-CS. This framework includes a range of algorithms for sparse recovery that require only approximate solutions for the model-projection problem. In essence, our work removes the aforementioned obstacle to model-CS, thereby extending model-CS to a much wider class of signal models. Interestingly, all our algorithms involve both the minimization and the maximization variants of the model-projection problem. We instantiate this new framework for a new signal model that we call the constrained earth mover distance (CEMD) model. This model is particularly useful for signal ensembles, where the positions of the nonzero coefficients do not change significantly as a function of spatial (or temporal) location. We develop novel approximation algorithms for both the maximization and the minimization versions of the model-projection problem via graph optimization techniques. Leveraging these algorithms and our framework results in a nearly sample-optimal sparse recov- ry scheme for the CEMD model.
机译：压缩感测（CS）指出，可以从少量的线性测量中恢复稀疏信号，并且可以在多项式时间内有效地执行此恢复。基于模型的CS框架（model-CS）充分利用了信号中的其他结构，并提供了可以进一步减少测量数量的新恢复方案。这个想法导致了针对各种信号模型的测量有效的恢复方案。但是，对于任何给定的模型，model-CS都需要一种解决模型投影问题的算法：给定查询信号，在模型中报告最接近查询信号的信号。通常，这种优化在计算上可能非常昂贵。而且，近似算法不足以使该优化可证明成功。结果，模型投影问题对将模型CS扩展到许多有趣的模型类别构成了根本障碍。在本文中，我们介绍了一个新的框架，称为近似公差模型CS。该框架包括用于稀疏恢复的一系列算法，这些算法仅需要模型投影问题的近似解即可。从本质上讲，我们的工作消除了模型CS的上述障碍，从而将模型CS扩展到了更广泛的信号模型类别。有趣的是，我们所有的算法都涉及模型投影问题的最小化和最大化变体。我们为新的信号模型实例化了这个新框架，我们将其称为约束推土机距离（CEMD）模型。该模型对于信号集合特别有用，在信号集合中，非零系数的位置不会随空间（或时间）位置而显着变化。我们通过图形优化技术针对模型投影问题的最大化和最小化版本开发了新颖的近似算法。利用这些算法和我们的框架，可为CEMD模型提供近乎样本最佳的稀疏恢复方案。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号