基于A*OMP算法的稀疏信号重构理论及应用研究

Compressed sensing is a new paradigm of signal acquisition, which senses a sparse signal by taking a set of incomplete measurements and recovers the signal by solving an optimization problem. It is one of the hottest research topics in signal processing, system identification and pattern recognition. The reconstruction algorithm is an important part of compressed sensing. Due to its computational simplicity and competitive performance, greedy method has gained considerable popularity in practical applications. The project analyzes the A*OMP algorithm that has low complexity, the contents are as follows: ① under the perturbations of additive noise and multiplicative noise, this project researches the theoretical performance of the A*OMP algorithm and obtains a sufficient condition for support recovery of sparse signals with A*OMP. We also evaluate the performance of A*OMP using the numerical simulations. ② Based on A*OMP, a new algorithm that aims to reconstruct block sparse signal will be proposed. We also discuss the proposed algorithm's theoretical performance and evaluate the performance of the proposed algorithm through real experiments on face recognition. ③ using the prior statistical information of sparse signals, a new greedy algorithm is designed with the help of best-first search method in the A*OMP algorithm. We also research its theoretical performance and evaluate the performance of the proposed algorithm through real experiments on image denoising and image inpainting. The implementation of this project could enrich the theory and application of sparse reconstruction algorithm.

压缩感知利用原始信号的稀疏性，从远少于信号元素个数的测量出发，通过求解稀疏优化问题来重构完整的原始稀疏信号。它是近年来信号处理、系统辨识和模式识别等领域的研究热点之一。重构算法是压缩感知理论的核心。贪婪算法以其计算简便及较低的复杂度，在实际中得到了广泛应用。本项目针对贪婪算法中的A*OMP算法的理论及应用展开研究，具体研究内容如下：① 加性噪声及乘性噪声干扰的情形下，建立A*OMP算法重构稀疏信号支撑集的充分条件并且利用数值仿真实验评估算法在噪声下的重构性能；② 基于A*OMP算法，提出适用于重构块稀疏信号的贪婪算法并对所提算法进行理论分析，将所提算法用于人脸识别问题中；③ 利用稀疏信号的先验统计信息，在A*OMP算法基础上提出高效的稀疏重构算法并对其理论性能进行研究，将所提算法用于图像去噪及图像修复中。本项目的研究成果能够进一步丰富稀疏重构算法的理论及应用。

传统的信号采样过程中，对信号中存在的大量冗余数据进行了采集，从而加大了采样成本，造成数据存储空间的浪费。针对传统的信号采样和处理中所出现的问题，2006年，Candes、Donoho和Tao等人提出了一种集采样和压缩合并进行的信号处理理论—压缩感知理论。该理论指出,如果原始信号本身是稀疏的或者可以稀疏表示的，借助相关算法，就能从远少于Nyquist采样数据中重构出原始信号。因此，压缩感知理论凭着自身的优越性受到研究人员的高度关注，在应用数学、计算机科学和电气工程等众多领域得到广泛的应用。.项目实施三年来，申请人以第一作者共发表8篇文章（其中7篇SCI，1篇中文核心），以通讯作者发表1篇SCI；培养7名硕士研究生，并且2名顺利毕业；邀请专家讲学20人次，圆满完成了项目的既定任务和目标，现将主要研究内容总结如下：.1.借助矩阵理论，函数逼近等相关理论，提出了保证A*OMP在噪声干扰情况下能够精确重构稀疏信号支撑集的充分条件。更多地，通过给出一个反例，证明了所提的条件在无噪干扰情况下是最优的。.2.通过构造一个完全平方式，利用一个改进的下界，提出了在三类不同噪声干扰下能够保证m^2OLS算法精确重构稀疏信号的充分条件。.3.查阅了相关文献之后，通过重新构造一个新的参数，给出了改进保证OMMP算法重构稀疏信号的充分条件。.4.通过引入一个超参数，给出了保证MOLS算法最多在有限步之后，能够精确重构稀疏信号的支撑集的充分条件，并且该条件与稀疏度K无关，是一个常数。.5.讨论了OLS算法在加性噪声和乘性噪声干扰下的理论性能。.6.对于二值信号重构问题，提出了二值匹配追踪算法，并且讨论了重构性能。.7.讨论了非负BOMP算法在重构块稀疏信号时的理论性能，并且利用仿真实验验证了所提算法在非负稀疏信号重构问题上的有效性。.8.讨论了NR-A*OMP算法在加性噪声和乘性噪声干扰下的理论性能。. 综上，本项目的研究结果包括理论分析，算法设计，应用举例等内容，结果丰富，内容翔实，对工程应用有一定指导意义，能够进一步丰富压缩感知重构算法的理论及应用。