压缩感知中基于梯度的贪婪重构算法综述

正交匹配追踪（OMP）算法是贪婪类算法中最经典的算法之一,但是对于大规模数据的重构问题却有着计算复杂度高、存储量大的缺点,而如果将最优化方法中的梯度与贪婪算法相结合,就会大大减少计算复杂度和存储需求.文中详述了梯度追踪算法,从理论上分析了这些算法的计算复杂度、存储需求和优缺点,并用这些算法分别重构一维信号和二维信号,分析重构效果.实验结果表明,梯度追踪算法的重构效果均比OMP好.尤其是基于变尺度法的梯度追踪算法,无论是重构时间还是重构效果,均优于OMP算法.

Survey on Gradient-Based Greedy Reconstruction Algorithms for Compressed Sensing

The orthogonal matching pursuit algorithm is one of the most classic greedy algorithms. It has the drawbacks of high computational complexity and large storage for the reconstruction of large-scale data. However, the computational complexity and large storage are reduced if the gradient from the optimization methods can be integrated into the greedy algorithm. This paper gives an overview of the gradient pursuit algorithms. The computational complexity, large storage, advantages and disadvantages of these algorithms are discussed by theoretical analyses. All of these algorithms are used to reconstruct one/two-dimensional signals. Experimental results show that the reconstruction performance of the gradient pursuit algorithm is better than that of the orthogonal matching pursuit algorithm. Especially the variable-metric based gradient pursuit algorithm, performs much better than the orthogonal matching pursuit algorithm in terms of the reconstruction performance and the reconstruction time.