The theory of compressive sensing has shown that sparse signals can be reconstructed exactly from remarkably few measurements. In [Chartrand, 2007], it was shown empirically that using ℓp minimization with p < 1 can do so with fewer measurements than with p=1. In this paper we consider the use of iteratively reweighted algorithms for computing local minima of the nonconvex problem. In particular, a particular regularization strategy is found to greatly improve the ability of a reweighted least-squares algorithm to recover sparse signals, with exact recovery being observed for signals that are much less sparse than required by an unregularized version (such as FOCUSS, [Rao, 1999]). Improvements are also observed for the reweighted-ℓ1 approach of Candès, Wakin, and Boyd.