We present gSUPPOSe, a novel, to the best of our knowledge, gradient-based implementation of the SUPPOSe algorithm that we have developed for the localization of single emitters. We study the performance of gSUPPOSe and compressed sensing STORM (CS-STORM) on simulations of single-molecule localization microscopy (SMLM) images at different fluorophore densities and in a wide range of signal-to-noise ratio conditions. We also study the combination of these methods with prior image denoising by means of a deep convolutional network. Our results show that gSUPPOSe can address the localization of multiple overlapping emitters even at a low number of acquired photons, outperforming CS-STORM in our quantitative analysis and having better computational times. We also demonstrate that image denoising greatly improves CS-STORM, showing the potential of deep learning enhanced localization on existing SMLM algorithms. The software developed in this work is available as open source Python libraries.