# A Graduated Non-Convexity Technique for Dealing Large Point Spread Functions
## 4 E-CATILED Technique
### Structural Characterizations of \(\beta\)-Matrices
If \(k=1\), then \(\mathcal{L}_{n,1}\) is the set of all _real reverse circulant_ (or _real anti-circulant_) _matrices_, which is the class of all matrices \(B\in\mathbb{R}^{n\times n}\) such that every row, after the first, has the elements of the previous one shifted cyclically one place left (see, e.g., [46]). Given a vector \(\mathbf{b}=(b_{0}\,b_{1}\cdots b_{n-1})^{T}\in\mathbb{R}^{n}\), set  
\[\text{circ}(\mathbf{b})=B= \begin{pmatrix}b_{0}&b_{1}&b_{2}&\ldots&b_{n-2}&b_{n -1}\\ b_{1}&b_{2}&b_{3}&\ldots&b_{n-1}&b_{0}\\ b_{2}&b_{3}&b_{4}&\ldots&b_{0}&b_{1}\\ \vdots&\vdots&\vdots&\ldots&\vdots&\vdots\\ b_{n-2}&b_{n-1}&b_{0}&\ldots&b_{n-4}&b_{n-3}\\ b_{n-1}&b_{0}&b_{1}&\ldots&b_{n-3}&b_{n-2}\end{pmatrix} ,\]  
with \(B\in\mathcal{L}_{n,1}\). Observe that every matrix \(B\in\mathcal{B}_{n,1}\) is symmetric, and the set \(\mathcal{L}_{n,1}\) is a linear space over \(\mathbb{R}\), but not an algebra. Note that, if \(B_{1}\), \(B_{2}\in\mathcal{L}_{n,1}\), then \(B_{1}\,B_{2}\), \(B_{2}\,B_{1}\in\mathcal{L}_{n,n-1}\) (see Theorem 5.1.2 in [46]). In Appendix A, we prove that  
\[\mathcal{B}_{n}=\mathcal{J}_{n,1}.\]  
**Proposition 2**. : _Let \(B=\text{circ}(\mathbf{b})\in\mathcal{B}_{n}\). Then, the eigenvalues \(\lambda_{j}^{(B)}\) of \(B\), can be expressed as_  
\[\lambda_{j}^{(B)}=\mathbf{b}^{T}\mathbf{u}^{(j)},\quad j=0,1,\ldots,\lfloor \frac{n}{2}\rfloor, \tag{12}\]  
_where the \(\mathbf{u}^{(j)}\)'s are as in (7). Moreover, for \(j=1,\,2,\ldots\lfloor\frac{n-1}{2}\rfloor\), we obtain_  
\[\lambda_{n-j}^{(B)}=-\lambda_{j}^{(B)}.\]  
_Furthermore, it is \(\lambda_{0}^{(B)}=0\), and \(\lambda_{n/2}^{(B)}=0\) if \(n\) is even._  
Proof. : See [45]. We note that  
\[\mathcal{F}_{n}=\{A\in\mathcal{L}_{n,1}:\text{ there is an asymmetric }\mathbf{a}\in\mathbb{R}^{n}\text{ with }A=\text{circ}(\mathbf{a})\}\]  
(see also [19]). **Proposition 3**. : _One has_  
\[\mathcal{A}_{n}=\{A\in\mathcal{L}_{n,n-1}:\text{ there is an asymmetric }\mathbf{a}\in\mathbb{R}^{n}\text{ with }A=\text{circ}(\mathbf{a})\}.\]Proof. : See [49]. From Proposition 3, it follows that  
\[\mathcal{L}_{n,n-1}=\mathcal{C}_{n}\oplus\mathcal{A}_{n}.\]  
Hence, we obtain  
\[\mathcal{V}_{n}=\mathcal{C}_{n}\oplus\mathcal{B}_{n}\oplus\mathcal{F}_{n}\oplus \mathcal{A}_{n}=\mathcal{L}_{n,1}\oplus\mathcal{L}_{n,n-1}.\]  
At each iteration of NL-SOR, we have to multiply a vector by \(\widehat{A}^{T}\widehat{A}\), where \(\widehat{A}\) is the blur matrix. Since \(\widehat{A}\) is a Toeplitz block matrix with Toeplitz blocks, each block of the \(\widehat{A}^{T}\widehat{A}\) matrix is composed of symmetric Toeplitz matrices added and multiplied together. Since we approximate every symmetric Toeplitz matrix with a matrix belonging to \(\mathcal{V}_{n}\), we now observe that \(\mathcal{V}_{n}\) is closed under the operations of addition and multiplication. Indeed, it is not difficult to see that \(\mathcal{V}_{n}\) is closed under the operation of sum between matrices. Moreover, \(\mathcal{L}_{n,1}\) is closed under the operation of multiplication, and if \(V_{1},V_{2}\in\mathcal{L}_{n,1}\), then \(V_{1}V_{2}\in\mathcal{L}_{n,n-1}\), if \(V_{1}\in\mathcal{L}_{n,n-1}\) and \(V_{2}\in\mathcal{L}_{n,1}\), then \(V_{1}V_{2}\in\mathcal{L}_{n,1}\) (see, e.g., [46]).