基于回溯的共轭梯度迭代硬阈值重构算法

针对基于回溯的迭代硬阈值算法（BIHT）迭代次数多、重构时间长的问题,提出一种基于回溯的共轭梯度迭代硬阈值算法（BCGIHT）。首先,在每次迭代中采用回溯思想,将前一次迭代的支撑集与当前支撑集合并成候选集;然后,在候选集所对应的矩阵列张成的空间中选择新的支撑集,以此减少支撑集被反复选择的次数,确保正确的支撑集被快速找到;最后,根据前后迭代支撑集是否相等的准则来决定使用梯度下降法或共轭梯度法作为寻优方法,加速算法收敛。一维随机高斯信号重构实验结果表明,BCGIHT重构成功率高于BIHT及同类算法,重构时间低于BIHT 25%以上。Pepper图像重构实验结果表明,BCGIHT重构精度和抗噪性能与BIHT及同类算法相当,重构时间相较于BIHT减少50%以上。     

基于双阈值的压缩采样匹配追踪改进算法

针对基于压缩感知的压缩采样匹配追踪(CoSaMP)算法迭代次数严重依赖于信号稀疏度,候选原子冗余度大,从而导致最终的支撑原子集选择时间长、选择精度低等问题,提出一种基于双阈值的压缩采样匹配追踪算法.该算法利用模糊阈值进行支撑集候选原子的选择,引入残差与观测矩阵的相关度变化阈值作为迭代停止条件,对图像进行重构.仿真实验表明,所提出的算法重构速度快,重构效果优于CoSaMP算法.     

记忆梯度追踪压缩感知图像重构

目的：重构算法是压缩感知理论的关键问题之一,为了减少压缩感知方向追踪算法重建时间,并确保相对较高的重建精度,提出了一种非单调记忆梯度追踪（memory gradient pursuit,MGP）重构信号处理算法。方法：该算法建立在方向追踪框架下,采用正则化正交匹配策略实现了原子集的快速有效选择,对所选原子集利用非单调线性搜索准则确定步长,用记忆梯度算法计算更新方向,从而得到稀疏信号估计值。结果：该算法充分利用记忆梯度算法在Armijo线搜索下全局收敛性快速稳定的优点避免收敛到局部最优解,提升收敛效率。提出的MGP算法运行时间上比近似共轭梯度追踪算法缩短30%,可以精确重构一维信号和二维图像信号。结论：实验结果表明,该算法兼顾了效率和重建精度,有效提高信号重建性能,在相同测试条件下优于其他同类的重构算法。     

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

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

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

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

基于PageRank和谱方法的个性化推荐算法

传统的PageRank推荐算法的可扩展性较差。针对这一问题,提出融合PageRank和谱方法的个性化推荐算法。通过在PageRank算法迭代过程中加入候选集节点数来控制迭代的次数,同时利用阈值来修剪参与迭代的节点个数,从而得到候选节点集;采用谱聚类对候选集进行排序,归一化候选节点邻接矩阵,使用矩阵的特征值与特征向量来评估图中节点与目标节点之间的距离,从而产生最终的推荐列表。实验结果表明,所提推荐算法在保证推荐质量的前提下,提高了处理效率。     

递减候选集正则化子空间追踪算法

为提高压缩感知子空间追踪算法的信号重建概率及精度,提出一种递减候选集正则化子空间追踪算法.该算法基于CoSaMP/SP算法并加以改进,将迭代过程分成若干个阶段,在每个阶段均采用类CoSaMP/SP算法进行迭代计算,但各阶段的候选集原子个数依次递减,同时按正则化方法选择新的候选集原子.实验仿真对比结果表明,与同类算法相比,所提出算法能够以更高概率重建信号,在噪声环境下也具有较高的重建精度.     

基于改进StOMP算法图像压缩感知重构*

在图像压缩感知重建中,一些算法能够取得好的重构效果,但耗时较长;一些算法耗时较短,但又不能取得精确解。针对重构效果和耗时不能兼得的问题,本文基于小波域稀疏,选用常规观测矩阵进行观测采样,通过对观测结果预定义滤波、选取信号硬阈值,引入共轭梯度下降算法,对分段正交匹配追踪（StOMP）重建算法进行改进。提出重建图像的边缘相似度概念,并对不同压缩比下的观测信号重建进行实验仿真。结果表明,相对于改进前StOMP算法,改进后StOMP算法在迭代收敛时间较短的情况下,重构效果提升。在主观评价上,重建图像噪声点明显减少;客观评价上,PSNR值提高,达到预期效果。     

一种新的跳频信号重构算法

为解决跳频信号压缩感知重构中稀疏度未知和稀疏字典规模庞大的问题,提出了一种基于多峰值匹配的压缩感知重构算法。该算法借鉴传统匹配追踪类算法结构,采用多峰值匹配原则进行原子选择,通过一次迭代确定候选集,然后利用回溯思想对候选集进行二次筛选获得支撑集,实现了跳频信号的精确重构。仿真结果表明,该算法重构性能与传统正交匹配追踪算法相近,同时重构速度大大提高。     

曲波域高斯混合尺度模型的图像压缩重构

压缩传感理论将信号的采样与压缩同时进行,利用信号在变换基上可以稀疏表示的先验知识,从比香农采样少的多的观测值中重构原始信号。近年来,两步迭代阈值算法作为一种求解反问题的优化方法,因其与多尺度几何分析存在紧密联系,且算法参数少,思想比较简单等特点,已经应用到了压缩重构中。但其使用时域的软硬阈值算子,不能获得很好的图像稀疏表示,从而使得算法重构精度不高。针对上述问题,本文在研究两步迭代阈值算法的基础上,提出了一种自适应的两步迭代阈值算法。该算法利用当前估计值提供的信息自适应估计步长参数,保证了估计值向最优解方向移动,提高了算法的重构精度,且针对其稀疏表示信号能力不足的缺点,运用高斯混合尺度模型对曲波邻域系数进行建模,充分利用曲波变换平移不变性和多方向选择性的优点,增加了图像表示的稀疏度。最后将其应用到图像压缩重构中,实验结果表明,该算法在峰值信噪比和主观视觉上都优于小波域高斯混合尺度模型和曲波硬阈值重构方法。     

多视三角化的迭代算法

多视三角化是在给定测量点对应和摄像机投影矩阵的情况下,求解相应的空间点的过程.由于测量点存在测量误差,所以只能求解在某种准则下的最优空间点.文中提出一种新的优化准则:在空间平面矩阵最小奇异值为0的约束下最小化估计点到测量点的L2-范数距离.在此基础上,采用该准则约束的Sampson近似得到一种简单的迭代求解方法;通过空间平面矩阵最小奇异值单调递减的条件和共轭梯度方法得到另一种收敛性更好的迭代算法.实验结果表明,这2种迭代算法不仅迭代次数及运算时间明显少于黄金标准算法,而且能得到基本相同的计算精度.     

Arithmetically improved algorithmic performance

An augmented set of floating-point arithmetic operations which includes the accurate inner product can be routinely employed with benefit in some standard iterative numerical algorithms. Benefits include the requirement of fewer iterations for achieving computational convergence criteria and more accurate results for a given number of iterations. Not all algorithms are benefited, but favorable results have been obtained for the QR algorithm, the conjugate gradient algorithm and the separating hyperplane algorithm.     

分段迭代匹配追踪图像重构算法

目的 压缩采样匹配追踪（CoSaMP）算法虽然引入回溯的思想,但其原子选择需要大量的观测值且在稀疏度估计不准确时,会降低信号重构精度,增加重构时间,降低重构效率。为提高CoSaMP算法的重构精度,改善算法的重构性能,提出了一种基于广义逆的分段迭代匹配追踪（StIMP）算法。方法 为保证迭代时挑选原子的精确性和快速性,对观测矩阵广义逆化,降低原子库中原子的相干性;原子更新结合正交匹配追踪（OMP）算法筛选原子的准确性与CoSaMP算法的回溯性,将迭代过程分为两个阶段：第1阶段利用OMP算法迭代K/2次;第2阶段以第1阶段OMP算法迭代所得的残差和原子为输入,并采用CoSaMP算法继续迭代,同时改变原子选择标准,从而精确快速地重构出稀疏信号。结果 对于1维的高斯随机信号,无论在不同的稀疏度还是观测值下,相比于OMP、CoSaMP、正则化正交匹配追踪（ROMP）算法和傅里叶类圆环压缩采样匹配追踪（FR-CoSaMP）算法,StIMP算法更加稳健,且具有更高重构成功率;对于2维图像信号,在各个采样率下,StIMP算法的峰值信噪比（PSNR）均高于其他重构算法,在采样率为0.7时,StIMP算法的平均PSNR值比OMP、CoSaMP、ROMP和FR-CoSaMP算法分别高2.14 dB、1.20 dB、3.67 dB和0.90 dB,平均重构时间也较OMP、CoSaMP和FR-CoSaMP算法短。结论 提出了一种改进的重构算法,对1维高斯随机信号和2维图像信号均有更好的重构效率和重构效果,与原算法和现有的主流图像重构方法相比,StIMP算法更具高效性和实用性。     

基于回代信赖域的电阻层析成像算法

针对电阻层析成像(ERT)技术中反演问题的病态性,提出一种改进的回代信赖域算法BTR(Backtracking Trust Region),并将其应用于气/水两相流的可视化测量。该算法通过信赖域算法获得迭代方向,通过回代技术获得迭代步长,可在减小重建误差的同时,提高成像速度。利用Comsol软件进行仿真,并设计ERT系统对各种典型流型进行测量,验证了算法的可行性。通过与Landweber算法、共轭梯度算法和现存的信赖域算法的比较,证明本文方法明显改进了成像精度和实时性。     

Automatic tuning of iterative computation on heterogeneous multiprocessors with ADITHE

This work studies the problem of balancing the workload of iterative algorithms on heterogeneous multiprocessors. An approach, called ADITHE, is proposed and evaluated. Its main features are: (1) using a homogeneous distribution of the workload on the heterogeneous system, the speed of every node is estimated during the first iterations of the algorithm; (2) according to the speed of every node, a new workload distribution is carried out; (3) the remaining iterations of the algorithm are executed. The result of this workload redistribution is that the execution times for every iteration at every node are similar and, consequently, the penalties due to synchronization between nodes at every iteration are mostly eliminated. This approach is appropriate for iterative algorithms with similar workload at every iteration, and with a relevant number of iterations. The high portability of ADITHE is guaranteed because the estimation of speed of nodes is included in the execution of the parallel algorithm. There is a wide variety of iterative algorithms related to science and engineering which can take advantage of ADITHE. An example of this kind of algorithms (morphological processing of hyperspectral images) is considered in this work to evaluate its performance when ADITHE is applied. The analysis of the results shows that ADITHE significantly improves the performance of parallel iterative algorithms on heterogeneous platforms.