# A Graduated Non-Convexity Technique for Dealing Large Point Spread Functions
## 2 Regularization of the Problem  
The formulation of the image generation direct problem is  
\[\mathbf{y}=\widehat{A}\mathbf{x}+\mathbf{n},\]  
where the \(n^{2}\)-dimensional vectors \(\mathbf{x}\), \(\mathbf{y}\) are, respectively, the original and the observed image. We assume that all intensity values are in one column in lexicographic order. The \(n^{2}\)-dimensional vector \(\mathbf{n}\) expresses the additive noise on the image, which we assume to be independent and identically distributed Gaussian, with zero mean and known variance \(\tilde{\sigma}^{2}\). The \(n^{2}\times n^{2}\) matrix \(\widehat{A}\) represents a translation-invariant blur operation on an image. This operation involves computing a light-intensity weighted average of the neighboring pixels of each pixel in the original image and assigning the result to that pixel in the blurred image. To define the matrix \(\widehat{A}\), we use a matrix \(M\in\mathbb{R}^{(2\widehat{h}+1)\times(2\widehat{h}+1)}\) called _blur mask_, and we compute the entries of matrix \(\widehat{A}\) as  
\[a_{(i,j),(i+w,j+v)}=\left\{ \begin{array}{ll}m_{\widehat{h}+1+w,\widehat{h}+ 1+v^{\prime}}&\text{if }|w|,|v|\leq\widehat{h},\\ 0,&\text{otherwise}.\end{array} \right.\]  
Here, in lexicographic notation, the generic index \(((i,j),(k,l))\) of matrix \(\widehat{A}\) is supposed to be equal to \(((j-1)n+i,(l-1)n+k)\). Namely, the blur mask determines the weighting factors used in the weighted averaging operation. Thus, the matrix \(\widehat{A}\) becomes a block Toeplitz matrix with Toeplitz blocks (cf. [39]). Note that the size of the blur mask \(2\widehat{h}+1\) corresponds to the size of the domain of the PSF (_point spread function_). If we assume that the blur operator is symmetric in the horizontal and in the vertical direction and the domain of the PSF is vast (that is \(2\widehat{h}+1\approx n\)), then the full matrix \(\widehat{A}\) is symmetric. The image restoration problem consists of finding an estimation \(\mathbf{x}\) of the unknown original image given the blurred image \(\mathbf{y}\), the matrix \(\widehat{A}\), and the variance of the noise \(\sigma^{2}\). This problem is ill-posed in the Hadamard sense; therefore, to solve the problem, some regularization techniques are necessary. Using the second-order difference operators in a regularization technique allows for significantly better results than those obtained by first-order difference operators (cf. [5]). On the other hand, using third-order difference operators yields slightly better results than those obtained with second-order difference operators to the detriment of an excessive increase in computational costs. Therefore, we use second-order difference operators. A _clique_\(c\) of order 2 is the subset of points of a square grid on which the second-order finite difference is defined. We denote by \(C\) the set of all cliques of order 2. More precisely, we consider  
\[C=\{c=\{(i,j),(h,l),(r,q)\}:i=h=r,j=l+1=q+2,\text{ or }i=h+1=r+2,j=l=q\}.\]  
We denote by \(D_{c}\mathbf{x}\) the second-order finite difference operator of the vector \(\mathbf{x}\) associated with the clique \(c\), that is, if \(c=\{(i,j),(h,l),(r,q)\}\in C\), then  
\[D_{c}\mathbf{x}=x_{i,j}-2x_{h,l}+x_{r,q}.\]  
Let us introduce the concept of _adjacent clique of order 2_, used to define the non-parallelism constraint, whose importance is apparent in Figure 2. The blurred image appears in (a); (b) is reconstructed from (a) without imposing the non-parallelism constraint, while the image in (d) is obtained by enforcing it. Although the reconstructions of Figure 2b,d appear similar to the human eye, the underlying quality for the latter is higher, as visible in the corresponding line process plots (c) and (e).