  In this paper, based on a successively accuracy-increasing approximation of
the $\ell_0$ norm, we propose a new algorithm for recovery of sparse vectors
from underdetermined measurements. The approximations are realized with a
certain class of concave functions that aggressively induce sparsity and their
closeness to the $\ell_0$ norm can be controlled. We prove that the series of
the approximations asymptotically coincides with the $\ell_1$ and $\ell_0$
norms when the approximation accuracy changes from the worst fitting to the
best fitting. When measurements are noise-free, an optimization scheme is
proposed which leads to a number of weighted $\ell_1$ minimization programs,
whereas, in the presence of noise, we propose two iterative thresholding
methods that are computationally appealing. A convergence guarantee for the
iterative thresholding method is provided, and, for a particular function in
the class of the approximating functions, we derive the closed-form
thresholding operator. We further present some theoretical analyses via the
restricted isometry, null space, and spherical section properties. Our
extensive numerical simulations indicate that the proposed algorithm closely
follows the performance of the oracle estimator for a range of sparsity levels
wider than those of the state-of-the-art algorithms.
