Abstract A prominent property of natural images is that groups of similar patches within them tend to lie on low-dimensional subspaces. This property has been previously used for image denoising, with particularly notable success via weighted nuclear norm minimization (WNNM). In this paper, we extend the WNNM method into a general image restoration algorithm, capable of handling arbitrary degradations (e.g. blur, missing pixels, etc.). Our approach is based on a novel regularization term which simultaneously penalizes for high weighted nuclear norm values of all the patch groups in the image. Our regularizer is isolated from the data-term, thus enabling convenient treatment of arbitrary degradations. Furthermore, it exploits the fractal property of natural images, by accounting for patch similarities also across different scales of the image. We propose a variable splitting method for solving the resulting optimization problem. This leads to an algorithm that is quite different from “plug-and-play” techniques, which solve image-restoration problems using a sequence of denoising steps. As we verify through extensive experiments, our algorithm achieves state of the art results in deblurring and inpainting, outperforming even the recent deep net based methods