Abstract:

Basis pursuit has promising applications and becomes a hotspot research topic in recent years. The proximal point algorithm is an effective way for solving basis pursuit problems. We propose a new algorithm, which combines the proximal point algorithm and the idea of linearized Bregman algorithm to solve this problem under the Lagrange dual analysis. Compared with the original linearized Bregman algorithm, the proposed algorithm can avoid the dependency of parameter selection on the model, so its application is beyond the compressed sensing problems. In order to accelerate the convergence speed of the new algorithm, every subproblem is speeded up by Nestrove acceleration scheme. In the simulations on sparse recovery problems of both compressed sensing and noncompressed sensing, we test the influence of parameter selections on the algorithm’s convergence, and the results demonstrate the advantage of this new algorithm.

Key words: basis pursuit;proximal point algorithm;linearized Bregman iteration;sparse recovery;dual analysis