Compressed sensing based on group sparsity has shown great potential in image denoising. However, most existing methods considered Nonlocal Self-Similarity (NSS) prior of noisy images only in a block-wise manner, which reduced reconstruction quality. This paper introduced group sparsity residual and total variance as the supplemental constraint within the framework of compressed sensing based on group sparsity, and transformed the reconstruction problem into two issues: multiscale patch matching and decreasing group sparsity residual. Then, an effective iterative algorithm with adaptive regularization parameter was proposed to recover the noisy images after estimating original images’ group sparse coefficients and matching patches at multiple scales, which improved group sparsity learning’s performance in denoising and restoring fine structure. Experimental results demonstrated that the proposed algorithm outperforms the contrast benchmarking algorithms for images corrupted with strong noise, such as BM3D, WNNM when considering the visual results and the objective evaluation together.