LOSoft: ℓ 0 Minimization via Soft Thresholding

We propose a new algorithm for finding sparse solution of a linear system of equations using $\ell_{0}$ minimization. The proposed algorithm relies on approximating the non-smooth $\ell_{0}$ (pseudo) norm with a differentiable function. Unlike other approaches, we utilize a particular definition of $\ell_{0}$ norm which states that the $\ell_{0}$ norm of a vector can be computed as the $\ell_{1}$ norm of its sign vector. Then, using a smooth approximation of the sign function, the problem is converted to $\ell_{1}$ minimization. This problem is solved via iterative proximal algorithms. Our simulations on both synthetic and real data demonstrate the promising performance of the proposed scheme.