2D sparse signal recovery via 2D orthogonal matching pursuit

Recovery algorithms play a key role in compressive sampling (CS).Most of current CS recovery algo-rithms are originally designed for one-dimensional (1D) signal,while many practical signals are two-dimensional (2D).By utilizing 2D separable sampling,2D signal recovery problem can be converted into 1D signal recovery problem so that ordinary 1D recovery algorithms,e.g.orthogonal matching pursuit (OMP),can be applied directly.However,even with 2D separable sampling,the memory usage and complexity at the decoder are still high.This paper develops a novel recovery algorithm called 2D-OMP,which is an extension of 1D-OMP.In the 2D-OMP,each atom in the dictionary is a matrix.At each iteration,the decoder projects the sample matrix onto 2D atoms to select the best matched atom,and then renews the weights for all the already selected atoms via the least squares.We show that 2D-OMP is in fact equivalent to 1D-OMP,but it reduces recovery complexity and memory usage significantly.What’s more important,by utilizing the same methodology used in this paper,one can even obtain higher dimensional OMP (say 3D-OMP,etc.) with ease.     

基于MP算法的语音信号稀疏分解

语音信号稀疏分解是一种新的语音信号分解方法,可以将语音信号分解为很简洁的近似表达形式。在语音信号稀疏分解的基础上,可应用于语音处理的多个方面,如语音压缩、语音去噪和语音识别等。研究利用Matching Pursuit（MP）算法实现语音信号的稀疏分解,实验结果表明基于MP算法的语音信号稀疏分解具有较好的重建精度和较高的稀疏度。     

Accelerating 2D orthogonal matching pursuit algorithm on GPU

Two-dimensional orthogonal matching pursuit (2D-OMP) algorithm is an extension of the one-dimensional OMP (1D-OMP), whose complexity and memory usage are lower than the 1D-OMP when they are applied to 2D sparse signal recovery. However, the major shortcoming of the 2D-OMP still resides in long computing time. To overcome this disadvantage, we develop a novel parallel design strategy of the 2D-OMP algorithm on a graphics processing unit (GPU) in this paper. We first analyze the complexity of the 2D-OMP and point out that the bottlenecks lie in matrix inverse and projection. After adopting the strategy of matrix inverse update whose performance is superior to traditional methods to reduce the complexity of original matrix inverse, projection becomes the most time-consuming module. Hence, a parallel matrix–matrix multiplication leveraging tiling algorithm strategy is launched to accelerate projection computation on GPU. Moreover, a fast matrix–vector multiplication, a parallel reduction algorithm, and some other parallel skills are also exploited to boost the performance of the 2D-OMP further on GPU. In the case of the sensing matrix of size 128 \(\times \) 256 (176 \(\times \) 256, resp.) for a 256 \(\times \) 256 scale image, experimental results show that the parallel 2D-OMP achieves 17 \(\times \) to 41 \(\times \) (24 \(\times \) to 62 \(\times \) , resp.) speedup over the original C code compiled with the O \(_2\) optimization option. Higher speedup would be further obtained with larger-size image recovery.     

基于压缩感知信号重建的自适应正交多匹配追踪算法*

近年来出现的压缩感知理论为信号处理的发展开辟了一条新的道路,不同于传统的奈奎斯特采样定理,它指出只要信号具有稀疏性或可压缩性,就可以通过少量随机采样点来恢复原始信号。在研究和总结传统匹配算法的基础上,提出了一种新的自适应正交多匹配追踪算法(adaptive orthogonal multi matching pursuit,AOMMP)用于稀疏信号的重建。该算法在选择原子匹配迭代时分两个阶段,引入自适应和多匹配的原则,加快了原子的匹配速度,提高了匹配的准确性,实现了原始信号的精确重建。最后与传统OMP算法     

回溯正则化分段正交匹配追踪算法

针对分段正交匹配追踪（StOMP）算法对信号重构效果较差的问题,提出一种回溯正则化分段正交匹配追踪（BR-StOMP）算法。首先,该算法采用正则化思想选取能量较大的原子,以减少阈值阶段候选集中的原子;然后,利用回溯对原子进行检验,并对解的支撑集中的原子重新筛选一次,同时删除对解的贡献较低的原子,提高算法的重构率;最后,对感知矩阵进行归一化处理,使算法更加简单。仿真结果表明：BR-StOMP算法与正交匹配追踪（OMP）算法相比较峰值信噪比提高8%~10%左右,运行时间减少70%~80%;与StOMP算法相比较,峰值信噪比提高19%~35%。BR-StOMP算法能够精确地恢复信号,重建效果优于OMP算法和StOMP算法。     

一种稀疏自适应的正交互补匹配追踪算法

针对实际应用中信号稀疏度未知的缺点,提出了一种稀疏度自适应的正交互补匹配追踪算法。算法先初始化稀疏度,再通过互补正交匹配追踪重构信号,找到一个支撑集;若支撑集不满足条件,则按指定步长增加稀疏度,再次运用算法进行重构,直到支撑集满足条件,得到最优支撑集。实验结果表明,该算法可以准确有效地重构信号,并且在相同压缩比下,其重构质量（PSNR）优于其他几种算法。     

Two dimensional sparse signal reconstruction via 2D inverse-free sparse Bayesian learning

Dear editor,With the ability to reconstruct signals represented using sparse bases in a certain transform domain from an incom-plete set of samples,sparse sign...     

Pixel-level image fusion with simultaneous orthogonal matching pursuit

Pixel-level image fusion integrates the information from multiple images of one scene to get an informative image which is more suitable for human visual perception or further image-processing. Sparse representation is a new signal representation theory which explores the sparseness of natural signals. Comparing to the traditional multiscale transform coefficients, the sparse representation coefficients can more accurately represent the image information. Thus, this paper proposes a novel image fusion scheme using the signal sparse representation theory. Because image fusion depends on local information of source images, we conduct the sparse representation on overlapping patches instead of the whole image, where a small size of dictionary is needed. In addition, the simultaneous orthogonal matching pursuit technique is introduced to guarantee that different source images are sparsely decomposed into the same subset of dictionary bases, which is the key to image fusion. The proposed method is tested on several categories of images and compared with some popular image fusion methods. The experimental results show that the proposed method can provide superior fused image in terms of several quantitative fusion evaluation indexes.     

Automated identification of thoracolumbar vertebrae using orthogonal matching pursuit

A computer-assisted system that can automatically provide rapid localization and accurate labeling of vertebral disks and bodies is a highly desirable tool due to the large demand for the diagnostic imaging and surgical planning of the vertebral column structures. However, a reliable detection and definitive labeling of vertebrae can be difficult due to factors such as the limited imaging coverage and various vertebral anomalies particularly in the thoracolumbar and lumbosacral junctions. In this paper, we investigate the problem of identifying the last thoracic and first lumbar vertebrae in CT images. The main purpose of this study is to improve the accuracy of labeling vertebrae of an automatic spine labeling system especially when the field of view is limited in the lower spine region. We present a dictionary-based classification method using a cascade of simultaneous orthogonal matching pursuit classifiers on 2D vertebral regions extracted from the maximum intensity projection images. The performance of the proposed method in terms of accuracy and speed has been validated by experimental results on hundreds of CT images collected from various clinical sites.     

基于随机支撑挑选的广义正交匹配追踪算法

针对广义正交匹配追踪（GOMP）算法复杂度高、重构时间长的问题,提出了一种基于随机支撑挑选的GOMP（StoGOMP）算法。首先引入随机支撑挑选的策略,在每次迭代中随机生成一个概率值。然后通过比较此概率值与预设概率值的大小来决定候选支撑集的挑选方式：若此概率值小于预设概率值,则采用匹配计算方式;否则,采用随机选择方式。最后根据得到的候选支撑来更新残差。这种方式充分考虑了算法单次迭代复杂度和迭代次数之间的平衡,减少了算法的计算量。一维随机信号重构实验结果表明,在预设概率值为0.5、稀疏度为20时,StoGOMP算法相较GOMP算法达到100%重构成功率所需的采样数减少了9.5%。实际图像重构实验结果表明,所提出的算法具有与GOMP算法相当的重构精度,且在采样率为0.5时,所提算法的重构时间相较于原算法减少了27%以上,这说明StoGOMP算法能够有效减少信号的重构时间。     

Adaptive algorithm for sparse signal recovery

The development of compressive sensing in recent years has given much attention to sparse signal recovery. In sparse signal recovery, spike and slab priors are playing a key role in inducing sparsity. The use of such priors, however, results in non-convex and mixed integer programming problems. Most of the existing algorithms to solve non-convex and mixed integer programming problems involve either simplifying assumptions, relaxations or high computational expenses. In this paper, we propose a new adaptive alternating direction method of multipliers (AADMM) algorithm to directly solve the suggested non-convex and mixed integer programming problem. The algorithm is based on the one-to-one mapping property of the support and non-zero element of the signal. At each step of the algorithm, we update the support by either adding an index to it or removing an index from it and use the alternating direction method of multipliers to recover the signal corresponding to the updated support. Moreover, as opposed to the competing “adaptive sparsity matching pursuit” and “alternating direction method of multipliers” methods our algorithm can solve non-convex problems directly. Experiments on synthetic data and real-world images demonstrated that the proposed AADMM algorithm provides superior performance and is computationally cheaper than the recently developed iterative convex refinement (ICR) and adaptive matching pursuit (AMP) algorithms.     

正交匹配追踪算法的优化设计与FPGA实现

设计了一种基于FPGA的正交匹配追踪(Orthogonal Matching Pursuit,OMP)算法的硬件优化结构,对OMP算法进行了改进,大大减少了乘法运算次数;在矩阵分解部分采用了交替柯列斯基分解(Alternative Cholesky Decomposition,ACD)方法避免开方运算,以减小计算延迟,整个系统采用并行计算、资源复用技术,在提高运算速度的同时减少资源利用。在Quartus II开发环境下对该设计进行了RTL级描述,在Altera公司的Cyclone II EP2C70F672C6上进行综合并完成时序仿真,仿真结果验证了设计的正确性。     

一种基于FPGA实现的优化正交匹配追踪算法设计

针对压缩感知重构算法中正交匹配追踪(OMP)算法在每次迭代中不能选取最优原子问题,对OMP算法进行优化设计,保证了每次迭代的当前观测信号余量最小,并提出了一种基于FPGA实现的优化OMP算法硬件结构设计。在矩阵分解部分采用了修正乔列斯基(Cholesky)分解方法,回避开方运算,以减少计算延时,易于FPGA实现。整个系统采用并行计算、资源复用技术,在提高运算速度的同时减少资源利用。在Quartus II开发环境下对该设计进行了RTL级描述,并在FPGA仿真平台上进行仿真验证。仿真结果验证了设计的正确性。     

基于互交替投影的块稀疏正交匹配追踪算法

针对块稀疏信号,理论分析和实验验证均表明算法精确重构的充分条件与矩阵块相关性和子相关性有关。在此基础上,提出了一种基于互交替投影的块稀疏正交匹配追踪算法(mutual alternating projection-block or-thogonal matching pursuit,MAP-BOMP)。该算法利用互交替投影方法不断构造新的测量矩阵和感知矩阵,使得矩阵块相关性和子相关性都很小,从而提高重构概率,并给出明确的算法收敛条件,降低了计算复杂度。通过与大多数已有块稀疏信号重构算法进行实验仿真对比,该算法在重构效果和重构速度上均优于其他算法。     

基于优化正交匹配追踪和深度置信网的声音识别

针对各种环境声音对声音事件识别的影响,提出一种基于优化的正交匹配追踪（OOMP）和深度置信网（DBN）的声音事件识别方法。首先,利用粒子群优化（PSO）算法优化OMP稀疏分解,在实现正交匹配追踪（OMP）的快速稀疏分解的同时,保留声音信号的主体部分,抑制噪声对声音信号的影响;接着,对重构声音信号提取Mel频率倒谱系数（MFCC）、OMP时-频特征和基音频率（Pitch）特征,组成OOMP的复合特征;最后,使用DBN对提取的OOMP特征进行特征学习,并对40种声音事件在不同环境不同信噪比下进行识别。实验结果表明,OOMP特征结合DBN的方法适用于各种环境声下的声音事件识别,而且能有效地识别各种环境下的声音事件,即使在信噪比（SNR）为0 dB的情况下,仍然能保持平均60%的识别率。     

ISAR imaging via sparse frequency-stepped chirp signal

Frequency-stepped chirp signal can simplify the designation of radar system.However,it has a shortcoming of Doppler ambiguity for high-speed moving targets.Therefore,it is of great significance to study how to increase its equivalent pulse repeat frequency.The back scattering field of the ISAR target has strong sparsity;that is to say,most energy is contributed merely by a few scattering centers.Hence,based on the theory of the sparse signal representation,a novel method for ISAR imaging via sparse frequency-stepped chirp signals is proposed by analyzing the signal model of the target.In the proposed method,part of sub-pulses of the frequency-stepped chirp signal is randomly selected to transmit,and then the 2D high-resolution image of the target can be constructed by sparse signal decomposition.At the cost of computational resources,the method can effectively resolve the problem of Doppler ambiguity,decrease the sidelobes and obtain a super-resolution image.Furthermore,the validity of the proposed approach is confirmed by the results of numerical simulations and real data.     

基于稀疏线性调频步进信号的ISAR成像

线性调频步进信号在简化雷达系统设计的同时,也存在对高速运动目标易出现Doppler模糊的问题,因此研究如何提高其等效的重复频率具有重要意义.由于ISAR目标的后向散射场具有较强的稀疏性,即大部分能量仅由少数散射中心贡献,所以本文基于稀疏信号表示理论,通过对目标回波模型的分析,提出了一种基于稀疏步进频率信号的逆合成孔径雷达成像方法.该方法通过随机地选择线性调频步进信号的部分子脉冲进行发射,然后使用稀疏信号分解的方法对目标图像进行重建以得到目标的二维高分辨图像.该方法以计算资源为代价,能够有效地去除方位Doppler模糊,同时还能够压低旁瓣并得到超分辨的图像.仿真和实测数据处理结果验证了本文方法的有效性.