  In recent years, patch-based image restoration approaches have demonstrated
superior performance compared to conventional variational methods. This paper
delves into the mathematical foundations underlying patch-based image
restoration methods, with a specific focus on establishing restoration
guarantees for patch-based image inpainting, leveraging the assumption of
self-similarity among patches. To accomplish this, we present a reformulation
of the image inpainting problem as structured low-rank matrix completion,
accomplished by grouping image patches with potential overlaps. By making
certain incoherence assumptions, we establish a restoration guarantee, given
that the number of samples exceeds the order of $rlog^2(N)$, where $N\times N$
denotes the size of the image and $r > 0$ represents the sum of ranks for each
group of image patches. Through our rigorous mathematical analysis, we provide
valuable insights into the theoretical foundations of patch-based image
restoration methods, shedding light on their efficacy and offering guidelines
for practical implementation.
