  The $\ell^0$ minimization of compressed sensing is often relaxed to $\ell^1$,
which yields easy computation using the shrinkage mapping known as soft
thresholding, and can be shown to recover the original solution under certain
hypotheses. Recent work has derived a general class of shrinkages and
associated nonconvex penalties that better approximate the original $\ell^0$
penalty and empirically can recover the original solution from fewer
measurements. We specifically examine p-shrinkage and firm thresholding. In
this work, we prove that given data and a measurement matrix from a broad class
of matrices, one can choose parameters for these classes of shrinkages to
guarantee exact recovery of the sparsest solution. We further prove convergence
of the algorithm iterative p-shrinkage (IPS) for solving one such relaxed
problem.
