A Graduated Non-Convexity Technique for Dealing Large Point Spread Functions

This paper focuses on reducing the computational cost of a GNC Algorithm for deblurring images when dealing with full symmetric Toeplitz block matrices composed of Toeplitz blocks. Such a case is widespread in real cases when the PSF has a vast range. The analysis in this paper centers around the class of gamma matrices, which can perform vector multiplications quickly. The paper presents a theoretical and experimental analysis of how (Formula presented.) -matrices can accurately approximate symmetric Toeplitz matrices. The proposed approach involves adding a minimization step for a new approximation of the energy function to the GNC technique. Specifically, we replace the Toeplitz matrices found in the blocks of the blur operator with (Formula presented.) -matrices in this approximation. The experimental results demonstrate that the new GNC algorithm proposed in this paper reduces computation time by over (Formula presented.) compared with its previous version. The image reconstruction quality, however, remains unchanged.