Low-rank matrix approximation and nonlocal means (NLM) are two popular techniques for image restoration. Although the basic principle for applying these two techniques is the same, i.e., similar image patches are abundant in the image, previously published related algorithms use either low-rank matrix approximation or NLM because they manipulate the information of similar patches in different ways. We propose a method for image restoration by jointly using low-rank matrix approximation and NLM in a unified minimization framework. To improve the accuracy of determining similar patches, we also propose a patch similarity measurement based on curvelet transform. Extensive experiments on image deblurring and compressive sensing image recovery validate that the proposed method achieves better results than many state-of-the-art algorithms in terms of both quantitative measures and visual perception.