## 3 The Proposed Undersampling Method  
The DFT transform has some interesting properties that can be exploited if the input data are sparse. Consider for example the matrix representation of a 16-point DFT displayed in Figure 2 that visualizes the concept on which the proposed method is based. As can be seen from this figure, there are pairs of rows that have a different number of identical \(X_{k}\) positions than others. For example, the row for \(n=0\) differs from the row that corresponds to \(n=8\) at the position of \(8\)\(X_{k}\) values while, the rows for \(n=1\) and \(n=15\) have only two common \(X_{k}\) positions (\(k=0\) and \(k=8\)). The equation \(x_{1}=x_{15}\) would hold if for the real part of the twiddles we had:  
\[ \begin{split}& f_{2}X_{1}+f_{3}X_{2}+f_{1}X_{3}+f_{1}X_{5}+f_{3}X_{ 6}+f_{2}X_{7}-\\ &-f_{2}X_{9}-f_{3}X_{10}-f_{1}X_{11}-f_{1}X_{13}-f_{3}X_{14}-f_{ 2}X_{15}=(\text{from row }n=1)\\ &=-f_{2}X_{1}-f_{3}X_{2}-f_{1}X_{3}-f_{1}X_{5}-f_{3}X_{6}-f_{2}X _{7}+\\ &+f_{2}X_{9}+f_{3}X_{10}+f_{1}X_{11}+f_{1}X_{13}+f_{3}X_{14}+f_{ 2}X_{15}\ (\text{from row }n=15)\end{split}  \tag{5}\]  
Figure 2: Distribution of the parameters \(X_{k}\) to different twiddle angles for the estimation of the \(x_{n}\) values in a 16-point DFT. Where \(f_{1}=0.382683,f_{2}=0.92388,f_{3}=0.707107\) (the cosine or sine of the various twiddle angles). In a similar manner for the imaginary part of the twiddles we would get:  
\[ \begin{split}& f_{1}X_{1}+f_{3}X_{2}+f_{2}X_{3}+X_{4}+f_{2}X_{5}+f_{3}X_{6 }+f_{1}X_{7}-\\ &-f_{1}X_{9}-f_{3}X_{10}-f_{2}X_{11}-X_{12}-f_{2}X_{13}-f_{3}X_{1 4}-f_{1}X_{15}=(\text{from row $n=1$})\\ &=-f_{1}X_{1}-f_{3}X_{2}-f_{2}X_{3}-X_{4}-f_{2}X_{5}-f_{3}X_{6}-f_ {1}X_{7}+\\ &+f_{1}X_{9}+f_{3}X_{10}+f_{2}X_{11}+X_{12}+f_{2}X_{13}+f_{3}X_{1 4}+f_{1}X_{15}\end{split}  \tag{6}\]  
Combining Equations 5 and 6 in order to have \(x_{1}=x_{15}\) we get the following conditions that must to be true:  
\[ \begin{split}& f_{2}(X_{1}+X_{7}-X_{9}-X_{15})+f_{1}(X_{3}+X_{5}-X_{1 1}-X_{13})\\ &+f_{3}(X_{2}+X_{6}-X_{10}-X_{14})=0\end{split}  \tag{7}\]  
\[ \begin{split}& f_{1}(X_{1}+X_{7}-X_{9}-X_{15})+f_{2}(X_{3}+X_{5}-X_{1 1}-X_{13})\\ &+f_{3}(X_{2}+X_{6}-X_{10}-X_{14})=0\end{split} \] (from imaginary parts) (8)  
There are several relations between the \(X_{k}\) symbols for the Equations 7 and 8 to hold. For example, if all the \(X_{k}\) symbols are zero or if the \(X_{k}\) symbols in each one of the parentheses sum up to zero as follows:  
\[ \begin{split}& X_{1}+X_{7}=X_{9}+X_{15}\\ & X_{3}+X_{5}=X_{11}+X_{13}\\ & X_{2}+X_{6}=X_{10}+X_{14}\end{split}  \tag{9}\]  
If the condition of Equation 9 holds, then the symbol \(x_{15}\) can be used in the place of \(x_{1}\) or _vice versa_. Conditions like the ones of Equations 5-9 can be found for other pairs of \(x_{n}\) symbols but the target is to find the smallest number of conditions that hold for a large number of \(x_{n}\) symbol pairs. This is not a trivial task since each conditions depends on the selected \(x_{n}\) symbol pair, the size of the DFT and the exact values that the symbols \(X_{k}\) can have, which in turn depends on the employed \(Q\)-QAM modulation. Substitutions like the one of \(x_{1}\) by \(x_{15}\) described above and the applications where conditions, such as Equations 5-9, can occur will be studied in our future work. A more general condition can be found though, since the \(x_{n}\) symbols with odd \(n\) (\(n=2p\) + 1, \(p=0\), 1, 2,..., \(N-1\)) are equal to the symbols \(x_{2p\) + 1 + \(N2}\), with \(N=4F\) if \(X_{2t\) + 1 = \(X_{2t\) + 1  
From Equations 10 and 11 it is obvious that the twiddle factors at even \(k\) positions are equal since \((-1)^{k}=1\) if \(k\) is even. At odd \(k\) positions the twiddle factors are inverted and \(x_{2t\ +\ 1}=x_{2t\ +\ 1}=x_{2t\ +\ 1}=N2\) only if \(X_{k}=0\). Unfortunately, \(X_{k}\) is never equal to zero if it is a \(Q\)-QAM output symbol. However, if the symbols \(X_{k}\) and \(X_{k\ +\ N/2}\) (=\(X_{k\ +\ 2F}\)) are equal, the following equation is true:  
\[