# A Graduated Non-Convexity Technique for Dealing Large Point Spread Functions
## 1 Introduction  
This paper addresses the problem of reconstructing blurry and noisy images. In particular, we consider blur operators that have a PSF (_point spread function_) with a vast domain. This case is pervasive; for example, it is common in underwater images (cf. [1, 2]). Figure 1 shows the point spread function of the Hubble space telescope camera before NASA corrections. The non-blind problem of restoring images consists of estimating the original image, starting from the observed image and the known blur. This problem is ill-posed in the Hadamard sense (cf. [3]). However, using various regularization techniques, it is possible to turn this problem into a well-posed one that can be solved by minimizing an energy function (cf. [4, 5, 6]). This function consists of two terms, one that ensures the solution fits the observed data and another that enforces the regularity of the solution. Figure 1: Point spread function of the Hubble space telescope camera. To produce more realistic restored images, we consider the discontinuities in natural images, particularly around edges where different objects meet (cf. [7]). A possible approach is to use an energy function, which implicitly assumes these discontinuities (cf. [4; 5; 6; 8]). This energy function has a non-convex regularization term. Moreover, to improve the quality of the restored images, it is possible to add constraints that prevent thick boundaries from forming between smooth areas (cf. [4; 5]). Thus, the resulting energy function is not convex and cannot be minimized using traditional gradient descent optimization algorithms. Stochastic or deterministic techniques can minimize such a non-convex energy function. By the former methods, it is possible to obtain very accurate results; however, their computational cost is very high (cf. [7]). Deterministic algorithms do not ensure convergence to the ideal solution but allow to obtain adequate reconstruction in lower computational times (cf. [9; 10]). The GNC (_Graduated Non-Convexity_) is one of the most widely used deterministic methods for edge-preserving reconstruction. This technique approximates the energy function using a sequence of approximations that converge to the original one and then solves each approximation using a classical optimization algorithm using the minimum found in the previous approximation as a starting point. In [8], [PERSON] and [PERSON] propose the first GNC algorithm dealing with the denoising problem. [PERSON], [PERSON], and [PERSON] in [11] present an extension of GNC to restore noisy images, considering the discontinuities' geometry. [PERSON] in [12] proposes a GNC technique to restore noisy blurred images. [PERSON], [PERSON], and [PERSON] in [5] present a GNC algorithm for the deblurring and the denoising imposing the constraint of the line continuation or the non-parallelism constraint alternatively; such an algorithm is referred to as CATILED (_Convex Approximation Technique for Interacting Line Elements Deblurring_). In this paper, we extend the CATILED technique, in the case of the non-parallelism constraint, to deal with PSFs with a large domain. The GNC technique has recently been applied to solve many other applications, such as solving the combinatorial data analysis problem of seriation (cf. [13]), stochastic problems (cf. [14]), solving the combinatorial optimization problems defined on the set of partial permutation matrices (cf. [15]), solving the maximum a posteriori inference problem (cf. [16]), pose estimation (cf. [17]), and spatial perception (cf. [18]). When the blur matrix is full, the computational cost of a GNC algorithm increases considerably; however, this technique remains a good compromise between non-edge-preserving techniques that yield low-accuracy results in a low computational time and stochastic techniques that give qualitatively accurate results with much higher computational cost.