# A Graduated Non-Convexity Technique for Dealing Large Point Spread Functions
## 4 E-CATILED Technique
### Approximation of Symmetric Toeplitz Matrices  
For each \(n\in\mathbb{N}\), let us consider the following class:  
\[\mathcal{T}_{n}=\{T_{n}\in\mathbb{R}^{n\times n}:t_{k,j}=t_{|k-j|},k,j\in\{0,1,\ldots,n-1\}\ \}. \tag{13}\]  
Observe that the class defined in (13) coincides with the family of all real symmetric Toeplitz matrices. Now, we consider the following problem: Given \(T_{n}\in\mathcal{T}_{n}\), find  
\[V_{n}(T_{n})=\min_{V\in\mathcal{V}_{n}}\|V-T_{n}\|_{F},\]  
where \(\|\cdot\|_{F}\) denotes the Frobenius norm. It is not difficult to see that, since \(T_{n}\) is symmetric, then we can assume that \(V_{n}(T_{n})\) is symmetric. Therefore, \(V_{n}(T_{n})=C_{n}(T_{n})+B_{n}(T_{n})+F_{n}(T_{n})\), where \(C_{n}(T_{n})\in C_{n}\), \(B_{n}(T_{n})\in B_{n}\), and \(F_{n}(T_{n})\in\mathcal{F}_{n}\). As regards \(\gamma\)-matrices, we prove the following:  
**Theorem 5**. : _Let \(\widehat{G}_{n}=\mathcal{S}_{n}+\mathcal{H}_{n,1}\). Given \(T_{n}\in\mathcal{T}_{n}\), one has_  
\[G_{n}(T_{n})=C_{n}(T_{n})+B_{n}(T_{n})=\min_{G\in\widehat{G}_{n}}\|G-T_{n}\|_{ F}=\min_{G\in\widehat{G}_{n}}\|G-T_{n}\|_{F}, \tag{14}\]  
_where \(C_{n}(T_{n})=\operatorname{circ}(\mathbf{c})\), with_  
\[c_{j}=\frac{(n-j)\,t_{j}+j\,t_{n-j}}{n},\quad j\in\{1,2,\ldots,n-1\};\]  
\[c_{0}=t_{0},\]  
_and \(B_{n}(T_{n})=\operatorname{rcirc}(\mathbf{b})\), where: for \(n\) even and \(j\in\{1,2,\ldots,n-1\}\setminus\{n/2\}\),_  
\[b_{j} = \frac{1}{2n}\left(\frac{4\,j-2\,n}{n}(t_{j}-t_{n-j})+4\sum_{k=1}^ {(j-3)/2}\frac{2\,k+1}{n}(t_{2k+1}-t_{n-2k-1})\right.\] \[+ \left.4\sum_{k=1}^{(n-j-3)/2}\frac{2\,k+1}{n}(t_{2k+1}-t_{n-2k-1} )\right),\]  
\(j\) _odd;_  
\[b_{j}=\frac{1}{2n}\left(\frac{4\,j-2\,n}{n}(t_{j}-t_{n-j})+4\sum_{k=1}^{j/2-1} \frac{2\,k}{n}(t_{2k}-t_{n-2k})+4\sum_{k=1}^{(n-j)/2-1}\frac{2\,k}{n}(t_{2k}- t_{n-2k})\right),\]  
\(j\) _even; for \(n\) even,_  
\[b_{0} = \frac{2}{n}\left(\sum_{k=1}^{n/2-1}\frac{2\,k}{n}(t_{2k}-t_{n-2k} )\right),\]  
\[b_{n/2} = \frac{4}{n}\left(\sum_{k=1}^{n/4-1}\frac{2\,k}{n}(t_{2k}-t_{n-2k} )\right);\]  
_for \(n\) odd and \(j\in\{1,2,\ldots,n-1\}\),_  
\[V_{n}(T_{n})=\min_{V\in\mathcal{V}_{n}}\|V-T_{n}\|_{F},\]0 \[V_{n}(T_{n})=\min_{V\in\mathcal{V}_{n}}\|V-T_{n}\|_{F},\]1\(j\) odd;_  
\[V_{n}(T_{n})=\min_{V\in\mathcal{V}_{n}}\|V-T_{n}\|_{F},\]2 \[V_{n}(T_{n})=\min_{V\in\mathcal{V}_{n}}\|V-T_{n}\|_{F},\]3  
_j even; for \(n\) odd,_  
\[V_{n}(T_{n})=\min_{V\in\mathcal{V}_{n}}\|V-T_{n}\|_{F},\]4  
Proof. : Let us define  
\[V_{n}(T_{n})=\min_{V\in\mathcal{V}_{n}}\|V-T_{n}\|_{F},\]5  
for any two symmetric vectors \(\mathbf{c}\), \(\mathbf{b}\in\mathbb{R}^{n}\). The proof is achieved by calculating the partial derivatives of the function \(\phi\), for details, see [45]. We prove an analogous result for generic \(\beta\)-matrices. **Theorem 6**. : _Given \(T_{n}\in\mathcal{T}_{n}\), one has_  
\[V_{n}(T_{n})=\min_{V\in\mathcal{V}_{n}}\|V-T_{n}\|_{F},\]6  
_where \(C_{n}(T_{n})\) and \(B_{n}(T_{n})\) are the same as those given in Theorem 5, and \(F_{n}(T_{n})=\mathrm{circ}(\mathbf{f})\), where:_  
\[V_{n}(T_{n})=\min_{V\in\mathcal{V}_{n}}\|V-T_{n}\|_{F},\]7  
\[V_{n}(T_{n})=\min_{V\in\mathcal{V}_{n}}\|V-T_{n}\|_{F},\]8  
Proof. : Set  
\[V_{n}(T_{n})=\min_{V\in\mathcal{V}_{n}}\|V-T_{n}\|_{F},\]9  
for each symmetric vector \(\mathbf{c}\in\mathbb{R}^{n}\), \(\mathbf{b}\in\mathbb{R}^{n}\) and for every asymmetric vector \(\mathbf{f}\in\mathbb{R}^{n}\). The proof is achieved by calculating the partial derivatives of the function \(\phi\), for details, see [49]. Note that  
\[G_{n}(T_{n})=C_{n}(T_{n})+B_{n}(T_{n})=\min_{G\in\widehat{G}_{n}}\|G-T_{n}\|_{ F}=\min_{G\in\widehat{G}_{n}}\|G-T_{n}\|_{F}, \tag{14}\]0  
where \(C_{n}(T_{n})\) is the same as the one given in Theorem 5 (see [50]), and \(F_{n}(T_{n})\) is the one given in Theorem 6 (see [19]). Now, we show how the approximations found by \(\beta\)-matrices or \(\gamma\)-matrices allows to obtain preconditioned linear symmetric Toeplitz systems with eigenvalues clustered around \(1\).