基于回溯思想的多面体面追踪算法

Polytope Faces Pursuit Algorithm Based on Backtracking

多面体面追踪算法能有效求解基追踪算法(BP)的对偶问题,但是算法一步只能选择一个原子,算法效率比较低。为解决上述问题,采用回溯迭代的思想对多面体面追踪算法进行改进,改进后的稀疏度自适应的多面体面追踪算法一步可以选择多个原子,同时利用回溯思想将可信度较低的原子删除,不但提高了算法的速度和重构的精度,而且实现了对信号稀疏度的自适应。通过仿真证明改进后的多面体面追踪算法的重构效率明显优于多面体面追踪算法,而且重构时间明显降低。

Polytope faces pursuit algorithm can effectively solve the dual problem of basis pursuit （ BP）, but the algorithm chooses only one atom for one step, the efficiency is low. To solve the above problem, an improved sparsity adaptive polytope faces pursuit algorithm based on backtracking was proposed. The improved algorithm chooses a group of atoms at one step; meanwhile, it uses backtracking theory to delete the atoms with low reliability. In this way, the algorithm not only improves the speed and reconstructs the accuracy of the algorithm, but also achieves the sparsity adaptation. Experimental results show that reconstruction efficiency of the improved algorithm is significantly better than the normal polytope faces pursuit algorithm, and the reconstruction time can be significantly reduced.