Subspace Pursuit for Compressive Sensing: Closing the Gap Between Performance and Complexity
Subspace Pursuit for Compressive Sensing: Closing the Gap Between Performance and Complexity
复制标题
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Wei Dai;O. Milenkovic
中科院分区：
文献类型：
--
作者：
Wei Dai;O. Milenkovic
摘要：我们提出了一种用于重构有噪和无噪稀疏信号的新方法，称为子空间追踪算法。该算法有两个重要特性：计算复杂度低，与正交匹配追踪技术相当；重构精度与线性规划优化方法处于同一数量级。所给出的分析表明，在无噪情况下，只要传感矩阵满足具有常数参数的受限等距特性，所提算法就能精确重构任意稀疏信号。在有噪情况下以及信号并非完全稀疏时，可以证明重构的均方误差由测量和信号扰动能量的常数倍所界定。
Abstract : We propose a new method for reconstruction of sparse signals with and without noisy perturbations, termed the subspace pursuit algorithm. The algorithm has two important characteristics: low computational complexity, comparable to that of orthogonal matching pursuit techniques, and reconstruction accuracy of the same order as that of LP optimization methods. The presented analysis shows that in the noiseless setting, the proposed algorithm can exactly reconstruct arbitrary sparse signals provided that the sensing matrix satisfies the restricted isometry property with a constant parameter. In the noisy setting and in the case that the signal is not exactly sparse it can be shown that the mean squared error of the reconstruction is upper bounded by constant multiples of the measurement and signal perturbation energies.