Sunday, July 9, 2017

How can a linear operator on DFT vector produce the same vector using only half of the DFT vector?


Suppose there is a DFT vector $\mathbf{X}$ with length N, which presents complex conjugate symmetry around its middle point, i.e., $X(1) = X(N-1)^*$, $X(2) = X(N - 2)^*$ and so forth. $X(0)$ and $X(N/2)$ are the DC and Nyquist frequency respectively, therefore are real numbers. The remaining elements are complex.


Now, suppose there is a matrix $\mathbf{T}$, with size $N \times N$, which multiplies vector X.


\begin{align} \mathbf{Y} = \mathbf{T}\mathbf{X} \end{align}



Assuming the operator $\mathbf{T}$ preserves the complex conjugate symmetry in $\mathbf{Y}$ (see Conditions for precoding matrix to preserve complex conjugate symmetry on DFT vector for more details), how can I obtain the same "positive frequencies" (from $X(0)$ to $X(N/2)$), using an $(N/2 + 1) \times (N/2 +1)$ matrix $\mathbf{T}$, instead of an $N \times N$?


The motivation for this question is to reduce complexity in the operation.


Consider that $X$ is a DMT symbol and its elements are mapped from QAM constellations with different sizes. Consider also that only the positive frequencies carry useful information, the "negative" frequencies are only used for the IFFT to be real.


EDIT: Is there a low-complexity solution other than using the $N/2+1$ upper rows of $\mathbf{T}$ multiplying the length-$N$ vector $\mathbf{X}$? This reduces the complexity to $N(N/2+1)$ CMACS plus the operations required to assemble the hermitian symmetric symbol


EDIT(2): I suggest the following code to illustrate the problem:


N = 8;  
A = rand(N,N); %must be real-valued
w = exp(-1j*2*pi/N); % twiddle factor
W = w.^(repmat(0:N-1,N,1).*repmat(0:N-1,N,1).'); % DFT matrix
T = W*A*W' % Linear operator

x = fft(rand(8,1));

It is obviously clear that:
T(1:N/2+1,:)x
Returns the positive frequencies from:
T
x
However,


Using x(1:N/2+1), what linear operator (with size $(N/2 + 1) \times (N/2 + 1)$) should I use to obtain the positive frequencies?




No comments:

Post a Comment

periodic trends - Comparing radii in lithium, beryllium, magnesium, aluminium and sodium ions

Apparently the of last four, $\ce{Mg^2+}$ is closest in radius to $\ce{Li+}$. Is this true, and if so, why would a whole larger shell ($\ce{...