An ℓ1-algorithm for underdetermined systems and applications

In this work, we consider a homotopic principle for solving large-scale and dense ℓ₁ underdetermined problems and its applications. The idea consists of obtaining the solution of the problem by solving a sequence of linear equality constrained multiquadric problems that depends on a regularization parameter that converges to zero. The procedure generates a central path that converges to a point on the solution set of the ℓ₁-underdetermined problem. This allows us to mimic the path-following methodology for primal-dual interior-point methods. We present a numerical experimentation showing the capability and effectiveness of our algorithm for recovering sparse signals, and its applications to MRI compressed sensing, seismic reflection and speech separation problems.