A Note on the Complexity of Proximal Iterative Hard Thresholding Algorithm

The iterative hard thresholding(IHT)algorithm is a powerful and efficient algorithm for solving l_(0)-regularized problems and inspired many applications in sparse-approximation and image-processing fields.Recently,some convergence results are established for the proximal scheme of IHT,namely proximal iterative hard thresholding(PIHT)algorithm(Blumensath and Davies,in J Fourier Anal Appl 14:629–654,2008;Hu et al.,Methods 67:294–303,2015;Lu,Math Program 147:125–154,2014;Trzasko et al.,IEEE/SP 14th Workshop on Statistical Signal Processing,2007)on solving the related l_(0)-optimization problems.However,the complexity analysis for the PIHT algorithm is not well explored.In this paper,we aim to provide some complexity estimations for the PIHT sequences.In particular,we show that the complexity of the sequential iterate error is at o(1/k).Under the assumption that the objective function is composed of a quadratic convex function and l_(0)regularization,we show that the PIHT algorithm has R-linear convergence rate.Finally,we illustrate some applications of this algorithm for compressive sensing reconstruction and sparse learning and validate the estimated error bounds.

迭代硬阈值压缩感知重构算法——IIHT

研究了压缩感知信号重构算法的理论,针对迭代硬阈值(IHT)重构算法对测量矩阵的过分依赖、计算复杂度高、运算时间长的缺点,通过修订迭代硬阈值重构算法的代价函数和自适应地调整迭代步长的选取原则,设计了一种迭代硬阈值重构算法——IIHT。IIHT算法显著提高了信号精确重构的概率,降低了算法的计算复杂度,进一步减少了算法的运算时间,加快了算法的收敛速度。

基于IHT算法的EMT金属探伤稀疏成像方法

为提高电磁层析成像(electromagnetic tomography,EMT)技术在金属结构缺陷检测时图像重建的效果,研究了基于迭代硬阈值(iterative hard thresholding,IHT)算法的稀疏成像方法。该文对传统图像重建算法的出发点、计算过程进行分析,再根据金属结构上缺陷分布的稀疏特性,选择稀疏成像方法;结合l_(2)、l_(1)、l_(0)范数约束下解的特点,选择l_(0)范数进行正则化约束解的范围,采用迭代硬阈值算法进行图像重建,并与Landweber迭代算法、Tikhonov正则化算法的图像重建效果进行对比。软件仿真和硬件实验均表明:l_(0)范数约束下的迭代硬阈值稀疏成像算法能够提高金属缺陷的图像重建质量;得到的图像相对误差比Landweber迭代算法、Tikhonov正则化算法降低10%;重建图像所用的时间减少一半。

基于回溯的迭代硬阈值算法

针对压缩传感(Compressed sensing,CS)理论中迭代硬阈值(Iterative hard thresholding,IHT)算法迭代次数多和时间长的问题,提出基于回溯的迭代硬阈值算法(Backtracking-based iterative hard thresholding,BIHT),该算法通过加入回溯的思想,优化了IHT算法迭代支撑的选择,减少支撑被反复选择的次数.模拟实验表明,在保证重建质量的前提下,相比较于IHT和正规化迭代硬阈值(Normalized IHT,NIHT)算法,BIHT算法的重建时间降低了2个数量级.用本身稀疏的0-1随机信号的重建实验表明,若测量次数和稀疏度相同,BIHT算法的重建概率高于IHT算法.

Geophysical data sparse reconstruction based on L0-norm minimization

Missing data are a problem in geophysical surveys, and interpolation and reconstruction of missing data is part of the data processing and interpretation. Based on the sparseness of the geophysical data or the transform domain, we can improve the accuracy and stability of the reconstruction by transforming it to a sparse optimization problem. In this paper, we propose a mathematical model for the sparse reconstruction of data based on the LO-norm minimization. Furthermore, we discuss two types of the approximation algorithm for the LO- norm minimization according to the size and characteristics of the geophysical data： namely, the iteratively reweighted least-squares algorithm and the fast iterative hard thresholding algorithm. Theoretical and numerical analysis showed that applying the iteratively reweighted least-squares algorithm to the reconstruction of potential field data exploits its fast convergence rate, short calculation time, and high precision, whereas the fast iterative hard thresholding algorithm is more suitable for processing seismic data, moreover, its computational efficiency is better than that of the traditional iterative hard thresholding algorithm.

语音重构的DCT域加速Landweber迭代硬阈值算法

重构信号的最基本理论依据是该信号在某个变换域是稀疏的或近似稀疏的。基于语音信号在DCT域的近似稀疏性,可以采用压缩感知(Compressed Sensing,CS)理论对其进行重构。压缩感知理论中的迭代硬阈值(Iterativehard thresholding,IHT)算法以其较好的性能被广泛用来重构信号,但其收敛速度比较慢,如何提高收敛速度,一直是迭代硬阈值算法研究的重点之一。针对压缩感知理论中的IHT算法收敛速度相当慢的问题,提出了语音重构的DCT域加速Landweber迭代硬阈值(Accelerated Landweber iterative hard thresholding,ALIHT)算法。该算法对原始语音信号做DCT变换,然后在DCT域将每一步Landweber迭代分解为矩阵计算和求解两步,通过修改其中的矩阵计算部分实现Landweber迭代加速,最后通过迭代硬阈值对信号做阈值处理。实验结果表明,加速Landweber迭代硬阈值算法加快了收敛速度、减少了计算量。

用于电阻层析成像的快速自适应硬阈值迭代算法

针对电阻层析成像技术图像重建具有严重病态性的问题,提出了一种稀疏重建算法——快速自适应硬阈值迭代算法,研究了噪声对该算法在电阻层析成像图像重建效果上的影响,并通过仿真和模型实验测试了该算法的性能.结果表明:一定强度范围内的噪声对硬阈值迭代算法、自适应硬阈值迭代算法和快速自适应硬阈值迭代算法的影响较小.快速自适应硬阈值迭代算法成像速度更快,且该算法重建图像的空间分辨率相对其他两种算法也有较大的提高.

脉冲噪声环境下一种改进的压缩感知洛伦兹迭代硬阈值重构算法

求解洛伦兹范数下的最优化问题是实现脉冲噪声环境下压缩感知重构的有效途径。但是洛伦兹迭代硬阈值(LIHT)算法随着脉冲噪声中脉冲数量的增加,重构性能明显下降。文中针对这一问题,提出一种改进的洛伦兹迭代硬阈值(MLIHT)算法。MLIHT算法中采用Barzilai-Borwein(BB)方法来设置步长μ,引入l1范数来寻找最优参数γ。将MLIHT算法分别应用到高斯稀疏信源和0-1稀疏信源的压缩感知脉冲噪声重构中,并且进行仿真实验和实验结果分析。实验结果表明,MLIHT算法对于脉冲噪声中脉冲的数量和幅度均不敏感,而且MLIHT算法实现有效重构所需的观测数要少于LIHT算法。

基于压缩感知的稀疏多径信道估计

提出了一种基于压缩感知理论的稀疏多径信道估计方法。利用训练序列设计了一种简化的Toeplitz结构观测矩阵,证明了观测矩阵满足限制等距特性,可以作为压缩感知的观测矩阵。根据此矩阵的近似正交性特点对正则化迭代硬阈值算法进行简化,并引入精英策略提出一种归档正则化迭代硬阈值估计算法。仿真结果表明,该估计方法相对于迭代最小二乘法具有更优的性能,且提出的归档正则化迭代硬阈值算法兼具收敛速度快和稳定性高的优点。

语音压缩感知硬阈值梯度追踪重构算法

本文基于语音信号在DCT域的近似稀疏性,采用压缩感知(Compressed Sensing,CS)理论对其进行压缩采样和重构。CS中的梯度追踪(Gradient Pursuit,GP)算法因计算量小,迭代硬阈值(Iterative Hard Threshold,IHT)算法因实现简单,被广泛用来重构信号。针对压缩感知理论中的GP算法的支撑集在每次迭代时仅增加一个元素,以及该算法每步迭代时仅经过一次沿负梯度方向搜索求得的解可能不是最优解的问题,本文提出了语音重构的硬阈值梯度追踪(Hard Threshold Gradient Pursuit,HTGP)算法。该算法利用IHT算法的思想选择原子更新支撑集,每步迭代时支撑集中含有K个元素,而且HTGP算法每步迭代时经过k次沿负梯度方向搜索得到最优解来代替使用计算量巨大的最小二乘来求解。实验结果表明,压缩比相同的情况下,HTGP算法具有更快速的收敛性和更高的信噪比。

基于小波树结构和迭代收缩的图像压缩感知算法研究

模型化压缩感知图像重构在标准压缩感知重构的基础上利用了小波树结构的先验知识,分别用贪婪树逼近和最优树逼近的方法求解重构优化问题。该文以模型化压缩感知重构中已有的小波树结构为基础,依据对大量自然图像小波系数关系的统计结果,提出了基于相邻系数、父系数与子系数之间统计相依关系的小波系数合理树结构,并结合小波系数合理树结构的思想,改进了普通迭代硬阈值压缩感知图像重构算法和基于最优树的模型化压缩感知图像重构算法。实验结果表明,该文算法能获得更高的图像重构质量。

基于冗余字典的联合稀疏同步迭代硬阈值算法

为了改进基于压缩感知(CS)的欠Nyquist采样系统在冗余字典条件下信号重构的效果,研究了基于ε-闭包的分块联合稀疏模型的同步迭代硬阈值(SIHT)算法。分析了采样系统基于多测量向量(MMV)的CS合成模型,提出了ε-闭包的分块相干性和约束等距特性(RIP)概念;在迭代过程中根据冗余字典分块相干性,对更新支撑集进行优选从而完成算法改进;给出了迭代收敛常数,并分析了改进型算法的收敛特性。仿真实验结果表明,相比传统算法,改进型算法在采样系统足够的通道数条件下重构成功率可达到100%,噪声抑制能力能够提高7 d B^9 d B,总运算时间可以降低至少37.9%,信号重构收敛速度更快。

稀疏补分析模型下迭代硬阈值正交投影

为了从含噪声的测量矢量中重构信号,研究了稀疏补分析模型理论及其迭代硬阈值正交投影算法。通过采用稀疏补正交投影修改了稀疏补分析模型下迭代硬阈值算法的迭代追踪过程;分析了迭代步长和稀疏补取值大小对算法收敛速度和重构性能的影响,找出了选取最优迭代步长和最佳稀疏补取值方法;提出并实现了稀疏补分析模型下迭代硬阈值正交投影算法,给出了算法收敛的充分条件和重构信号误差范围。仿真实验结果表明,算法的平均运算时间仅仅为AIHT、AL1和GAP算法的19%、11%和10%;算法重构信号的综合平均峰值信噪比(PSNR)比AIHT算法提高了0.89 dB,但比AIHT、AL1算法稍逊色。算法在满足给定条件下能够以高概率实现含噪信号重构,重构信号的综合平均PSNR与典型算相比没有明显下降,但运算时间大为缩短,收敛速度更快。

图像分块压缩感知中的自适应粒重建算法

在图像分块压缩感知(Block compressed sensning,BCS)框架下,基于平滑投影Landweber迭代的重建算法能以低计算复杂度确保良好率失真性能,尤其是采用主成分分析(Principle component analysis,PCA)作自适应硬阈值收缩。然而,在PCA学习过程中忽略了图像局部结构特性平稳,会影响Landweber迭代重建性能的提升。针对该问题,本文采用粒计算(Granular computing,Gr C)理论,根据图像子块结构特性将图像分解为若干粒,再实施PCA学习各粒的稀疏表示基底,并对粒内子块硬阈值收缩去噪。由于粒内图像子块具有平稳的结构特性,可有效改善硬阈值收缩性能。实验结果表明,与传统算法相比,本文算法重建图像的整体客观质量较优,且可更好地保护边缘与纹理等重要细节,主观视觉质量良好,与此同时,保证了较低的重建计算复杂度。

基于混合梯度的硬阈值追踪算法

针对压缩感知(CS)中迭代硬阈值类算法迭代次数多、重构时间长的问题,提出了一种基于混合梯度的硬阈值追踪(HGHTP)算法。首先,在每次迭代中计算当前迭代点处的梯度和共轭梯度,将梯度域与共轭梯度域下的支撑集混合取并集作为下一次迭代的候选支撑集,充分利用共轭梯度在支撑集选择策略中的有用信息,优化支撑集选择策略;然后,采用最小二乘法对候选支撑集进行二次筛选,快速精确地定位正确的支撑并更新稀疏系数。一维随机信号重构实验结果表明,HGHTP算法相较于同类迭代硬阈值算法,在保证重构成功率的前提下,需要的迭代次数更少。二维图像重构实验结果表明,HGHTP算法的重构精度和抗噪性能优于同类迭代阈值类算法,在保证重构精度的情况下,HGHTP算法的重构时间相比同类算法减少了32%以上。

自适应阈值的1-bit压缩感知算法

针对二进制迭代硬阈值(BIHT)算法中固定的量化阈值在一定程度上限制了该算法重构性能的问题,提出了一种基于自适应阈值的二进制迭代硬阈值(AT-BIHT)算法,用于实现可压缩信号的1-bit压缩感知(CS)采集与重构。该算法采用基于自适应阈值的二进制量化器替代了BIHT算法中的符号函数,根据已获得的重构信号为当前测量值的1-bit量化选择合适的量化阈值;在继承BIHT算法优点的基础上,有效提高了重构性能。仿真实验表明,对于随机稀疏信号和实际心电信号,AT-BIHT算法的重建性能均高于BIHT算法。

压缩感知中一种改进的迭代硬阈值算法

研究了压缩感知理论中一种改进的迭代硬阈值稀疏信号重构算法。针对现有IHT算法类最优秀的BIHT算法中回溯操作无法保证稀疏信号重构误差递减的问题,对稀疏重构误差及其差值进行了简单介绍和分析,提出了一种能够保证重构误差随迭代进行单调减小的重构算法,在每次迭代的回溯操作中选择能够保证重构误差逐渐减小的原子,并将其指标与估计支撑集合并,最后基于最小二乘法进行伪逆运算获取稀疏信号估计。对高斯稀疏信号和0-1稀疏信号进行了仿真,证明了优于IHT、NIHT以及BIHT算法的稀疏信号重构性能。

地震数据POCS插值重建中的一种新型质量控制准则

大多数地震数据插值重建方法利用的是迭代策略,因此,有必要建立合理的质量控制准则来适时终止迭代,在保证插值精度的同时,提高计算效率。利用迭代硬阈值方法及投影算子推导出凸集投影方法(POCS),基于观测数据置入前、后的数据体建立了新的质量控制准则,该控制准则仅利用了观测数据的信息,具有较好的适应性,可以进一步提高POCS插值重建方法的计算效率。利用两套模拟数据详细比较了3种质量控制准则(J1,J2和J3)的应用效果,验证了新提出的质量控制准则的有效性。实际资料应用效果表明该准则可以在保证插值精度的同时提高计算效率。

一种改进的迭代硬阈值算法

压缩感知重构算法直接影响信号重构速度和效果。迭代硬阈值(IHT)算法具有重构速度快的优点,但是其重构精度不高。提出一种改进的迭代硬阈值(MIHT)算法,在迭代硬阈值算法的基础上引入压缩采样匹配追踪(CoSaMP)算法中原子回溯的思想,保证每次迭代都能找到正确的索引集,提高算法的重构精度。Matlab仿真结果表明,本文提出的算法在重构精度上明显优于迭代硬阈值算法,而在迭代次数和重构时间上明显低于压缩采样匹配追踪算法。

变步长稀疏自适应的迭代硬阈值图像重构

针对压缩感知理论中迭代硬阈值IHT重构算法要求给定信号稀疏度的缺点,提出了一种变步长稀疏自适应迭代硬阈值VSSSAIHT算法。该算法在信号的稀疏度未知的情况下,通过相邻迭代残差的差值大小来选择合适的步长,以扩大重构信号的支撑集,不断逼近原始信号的稀疏度,逐步迭代恢复信号。仿真结果表明,与迭代硬阈值算法相比,VSSSAIHT算法改善了图像重构的质量,减少了算法运行的时间。