# A Sparse Algorithm for Computing the DFT Using Its Real Eigenvectors
## 6 Accuracy and Performance of DFT Eigenvector Computation  
The two different methods used to calculate the orthonormal eigenvectors yield different computational accuracies. These differences arise due to the limitations imposed by the finite-precision data types that are used in real-world machines, and the varying methods used to produce the sparse eigenvectors. We compare the DFTs created using the Matveev method and the Gram-Schmidt orthonormalization of DFT projection matrices. All tests are run using the double-precision floating point data type on MATLAB version 2020b on a machine with Intel(R) Core(TM) i7-6700 HQ @ 2.60 GHz 4 core CPU, 8 GB RAM and Windows 10 operating system.  
Figure 3 indicates the computational error due to imprecise DFT eigenvectors. Suppose \(x\) is a vector in \(\mathbb{R}^{n}\) and \(y=\mathrm{IDFT}(\mathrm{DFT}(x))\). The figure shows the mean squared error (MSE) of \(x-y\) in decibels. The DFT and IDFT is calculated using Matveev eigenvectors, Gram-Schmidt orthonormalization of DFT projection matrices, and using the MATLAB fft() and ifft() functions. The MSE is calculated via (21), (22) and (23) where \(n\) is the length of the vectors \(x\) and \(y\) and the operator \(\|x\|\) represents the 2-norm of \(x\). The error shown in Figure 3 is caused by the limitation imposed by the machine that was used to compute the eigenvectors. More powerful machines can be used to pre-compute the eigenvectors to a high enough precision such that this error can be eliminated.  
\[\mathrm{MSE}=10\log_{10}(\mu) \tag{21}\]  
where  
\[\mu=\frac{1}{1000}\sum_{i=1}^{1000}\sigma_{i} \tag{22}\]  
and  
\[\sigma=\frac{\|x-y\|^{2}}{n} \tag{23}\]  
Here \(\sigma_{i}\) represents \(i^{th}\) sample out of 1000 samples as explained below.  
For each \(n\)-point DFT, 1000 vectors are randomly generated such that each element of a vector \(x\) is an integer that lies between \(-128\) and \(127\). These limits are chosen because we can represent the pixels of an 8-bit image after centering the pixel values to 0. For each vector \(x\), the corresponding \(y\) and \(\sigma\) are computed. Equation (22) gives the average \(\sigma\) value of the 1000 samples and (21) gives the average MSE in dB. The plot in Figure 3 shows the error after computing the forward and inverse DFT. Therefore, the error while finding the DFT in one direction will be slightly lower than what is shown and will depend on the size of DFT. Clearly, the computational performance of the eigenvector methods suffers a bit, especially as the length of the DFT increases. The differences are not significant for lengths up to 20, and the method's complexity analysis in Section 7 will show why these approaches are attractive.  
The time required to calculate the eigenvectors from the DFT projection matrices and orthonormalizing them with Matveev method and Gram-Schmidt process is summarized in Table 1. In this table, the time is calculated for 10,000 executions of each of the methods and is shown in units of seconds. This is consistent with our rudimentary analysis of the computational complexity of each of the methods: \(O\big{(}n^{3}\big{)}\) for Gram-Schmidt and \(O\big{(}n^{5}\big{)}\) for Matveev method (assuming the required matrix determinant is computed in \(O\big{(}n^{3}\big{)}\) complexity). This discrepancy arises from the need for calculating the determinant of the \(\beta\) matrix in the Matveev method, whereas the vector dot product can be calculated in \(O(n)\) time for the Gram-Schmidt process.  
\begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Length of DFT:** & **10** & **20** & **30** & **40** \\ \hline [PERSON] & 0.919 & 3.354 & 6.460 & 10.452 \\ Gram–Schmidt & 0.684 & 1.303 & 2.269 & 3.694 \\ \hline \hline \end{tabular}
\end{table}
Table 1: Computation time in seconds for 10,000 runs.