Image denoising methods must effectively model, implicitly or explicitly, the vast diversity of patterns and textures that occur in natural images. This is challenging, even for modern methods that leverage deep neural networks trained to regress to clean images from noisy inputs. Meanwhile, a number of traditional image restoration methods have demonstrated the benefits of relying on "internal" image statistics: using the fact that the variability of patterns within a single image is far more limited than that across various images and scenes. A key obstacle with such approaches, however, is in accurately identifying recurring patterns from within a noisy observation. In this work, we propose a new method for natural image denoising that trains a deep neural network to determine whether noisy patches in a given image input share common underlying patterns. Specifically, given a pair of noisy patches, this network predicts whether different transform sub-band coefficients of the original noise-free patches are similar. The denoising algorithm then aggregates matched coefficients to obtain an initial estimate of the clean image. We show that this yields higher quality results than previous internal statistics-based approaches. Moreover, by providing this estimate, along with the original noisy image, as input to a standard regression-based denoising network, we demonstrate that our method is able to achieve state-of-the-art denoising performance.