We present a method for improving a Non Local Means operator by computing its\nlow-rank approximation. The low-rank operator is constructed by applying a\nfilter to the spectrum of the original Non Local Means operator. This results\nin an operator which is less sensitive to noise while preserving important\nproperties of the original operator. The method is efficiently implemented\nbased on Chebyshev polynomials and is demonstrated on the application of\nnatural images denoising. For this application, we provide a comprehensive\ncomparison of our method with leading denoising methods.\n