Power-iterative strategy for ℓp−ℓ2 optimization for compressive sensing: Towards global solution

We study nonconvex relaxation of the combinatorial ℓ₀-minimization for compressive sensing. In an ℓ_p-ℓ₂ minimization setting with p <; 1, we propose an iterative algorithm with two distinct features: (i) use of a proximal-point (P-P) objective function composed of a convex quadratic term and an ℓ_p-norm term, and a fast parallel-based solver for global minimization of the P-P function in each iteration; and (ii) a power-iterative strategy that begins by solving a convex ℓ₁-ℓ₂ problem whose solution is then used to start next ℓ_p-ℓ₂ problem with p close to but less than one. The process continues with gradually reduced p until a target power p_t is reached. By simulations the algorithm is shown to offer considerable performance gain.