Efficient Compressive Sensing with Deterministic Guarantees Using Expander Graphs
Efficient Compressive Sensing with Deterministic Guarantees Using Expander Graphs
复制标题
DOI：
10.1109/itw.2007.4313110
复制
发表时间：
2007-09
期刊：
影响因子：
--
通讯作者：
Weiyu Xu;B. Hassibi
中科院分区：
文献类型：
--
作者：
Weiyu Xu;B. Hassibi
压缩感知是一种新兴的技术，它可以通过比n小得多的测量来恢复n维稀疏信号向量。然而，现有的压缩感知方法可能仍然遭受相对高的恢复复杂度，例如O（n3），或者只能在信号超稀疏时有效地工作，有时没有确定性的性能保证。在本文中，我们提出了一种压缩感知方案，使用基于扩展图的测量矩阵具有确定性的性能保证，并表明即使非零元素k的数量随n线性增长，信号恢复也可以实现复杂度为O（n）。我们还研究了压缩感知近似稀疏信号使用这种新方法。此外，所考虑的扩展图的明确的建设存在。仿真结果显示了新方法的性能和复杂度。
Compressive sensing is an emerging technology which can recover a sparse signal vector of dimension n via a much smaller number of measurements than n. However, the existing compressive sensing methods may still suffer from relatively high recovery complexity, such as O(n3), or can only work efficiently when the signal is super sparse, sometimes without deterministic performance guarantees. In this paper, we propose a compressive sensing scheme with deterministic performance guarantees using expander-graphs-based measurement matrices and show that the signal recovery can be achieved with complexity O(n) even if the number of nonzero elements k grows linearly with n. We also investigate compressive sensing for approximately sparse signals using this new method. Moreover, explicit constructions of the considered expander graphs exist. Simulation results are given to show the performance and complexity of the new method.