  Sparse signal recovery has been dominated by the basis pursuit denoise (BPDN)
problem formulation for over a decade. In this paper, we propose an algorithm
that outperforms BPDN in finding sparse solutions to underdetermined linear
systems of equations at no additional computational cost. Our algorithm, called
WSPGL1, is a modification of the spectral projected gradient for $\ell_1$
minimization (SPGL1) algorithm in which the sequence of LASSO subproblems are
replaced by a sequence of weighted LASSO subproblems with constant weights
applied to a support estimate. The support estimate is derived from the data
and is updated at every iteration. The algorithm also modifies the Pareto curve
at every iteration to reflect the new weighted $\ell_1$ minimization problem
that is being solved. We demonstrate through extensive simulations that the
sparse recovery performance of our algorithm is superior to that of $\ell_1$
minimization and approaches the recovery performance of iterative re-weighted
$\ell_1$ (IRWL1) minimization of Cand{\`e}s, Wakin, and Boyd, although it does
not match it in general. Moreover, our algorithm has the computational cost of
a single BPDN problem.
