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

Question

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:
Tx
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?

Answer 1

I've suggested in the comments above (and I think Matt L is trying to say the same thing also) that you should be able to just discard the negative frequency elements entirely for your analysis. They don't seem to be relevant to what you're doing (which makes sense, since they don't carry any information, as the time-domain signal is real). Look at your equation again:

$$ \mathbf{y} = \mathbf{Tx} $$

(I changed the casing so that lower-case symbols are vectors and upper-case are matrices, as is the typical convention)

Assume for the time being that $\mathbf{x}$ and $\mathbf{y}$ are length-$N$ and thus $\mathbf{T}$ is $N$-by-$N$. This would correspond to the general case, where the time-domain signals corresponding to $\mathbf{x}$ and $\mathbf{y}$ need not be real. If $\mathbf{y}$ is a column vector, then you can think of the matrix operation instead as:

$$ \mathbf{y} = \sum_{k=1}^N x_k\mathbf{t_k} $$

where $x_k$ is the $k$-th element of the vector $\mathbf{x}$ and $\mathbf{t_k}$ is the $k$-th column of the matrix $\mathbf{T}$. My question at this point would be, instead of using the full $N$-length vector and $N$-by-$N$ matrix, why not just use the $N/2$ rows that contain information? Then, the calculation would turn into:

$$ \mathbf{y^+} = \sum_{k=1}^{N/2} x_k\mathbf{t_k} $$

(neglecting the details of the boundary cases for the zeroth and Nyquist bins, which depend upon whether $N$ is even or odd)

The resulting vector $\mathbf{y^+}$ contains the positive frequencies for the desired result. You can then just symmetrically extend it to get a full length-$N$ vector that has the conjugate symmetry that you seek. This should make intuitive sense in the following ways:

• If there is no information in the negative frequencies in the input vector $\mathbf{x}$ (which there isn't, since the entire vector is defined by its positive frequency components), then you shouldn't need to use them in your calculations.

• If there is no information in the negative frequencies in the output vector $\mathbf{y}$ (which there isn't, since the entire vector is defined by its positive frequency components), then you shouldn't need to waste time calculating what their values would be.

This should free you from worrying about any bizarre constraints on the properties of the matrix $\mathbf{T}$. I think you're trying to think of the action of the precoder as too coupled with the OFDM modulation. Instead, think of it just as a preprocessing operation that happens on the encoded symbols before you assign them to frequency bins in the OFDM modulator's IDFT.

Answer 2

Assuming that you still need conjugate symmetry, i.e. you're dealing with real-valued signals, you have vectors of length $N/2+1$ and a $(N/2+1)\times (N/2+1)$ transformation matrix:

$$\mathbf{y}=\mathbf{Tx}$$

Since we have only positive frequencies between DC and Nyquist, there are only constraints on the first and the last element of $\mathbf{y}$, respectively. They must be real-valued. All other elements of $\mathbf{y}$ can be complex-valued and there are no further constraints on them. Since the DC component of $\mathbf{y}$ is given by (I use indices from $1$ to $N/2+1$)

$$y(1)=t_{11}x(1) + t_{12}x(2)+\ldots + t_{1,N/2+1}x(N/2+1)$$ and since only $x(1)$ and $x(N/2+1)$ are necessarily real-valued, we need to make sure that $t_{11}$ and $t_{1,N/2+1}$ are real-valued and that all other elements $t_{1i}$, $i=2,\ldots, N/2$ are zero. The same constraint applies to the last row of the matrix $\mathbf{T}$ (corresponding to $y(N/2+1)$ at Nyquist). All other rows of $\mathbf{T}$ can contain arbitrary complex-valued numbers.

Answer 3

@JasonR and @MAttL. I think this problem has no solution. I tried using least squares to find a linear of operator with size $(N/2+1) \times (N/2+1)$ that minimizes the error between the positive frequencies from the set of known vectors $Y$ and the set of vectors $X$ to be linearly transformed.

The code to estimate the $(N/2+1) \times (N/2+1)$ is the following. Note that the norm of the error is significant.

clear all
clc

SET_LENGTH = 1e4;

x =  fft(rand(8,SET_LENGTH));
N = 8;

% Linear Operator
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';

% Hermitian symmetric symbols
y = T*x;

% Positive frequencies
xp = x(1:(N/2 + 1),:);
yp = y(1:(N/2 + 1),:);

% Estimate linear operator with reduced dimensions
T_est = (yp*xp')/(xp*xp')

% Compare results
norm(T_est*xp(:,2)-yp(:,2)) 

To verify the math is right, I also estimate the $N \times N$ linear operator, which I know beforehand exists. The result is that the norm of the error is null.

SET_LENGTH = 1e4;

x =  fft(rand(8,SET_LENGTH));
N = 8;

% Linear Operator
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';

% Hermitian symmetric symbols
y = T*x;

% Estimate linear operator with reduced dimensions
T_est = (y*x')/(x*x')

% Compare results
norm(T_est*x(:,2)-y(:,2)) 

Anybody with more knowledge could state whether I can conclude or not that the problem has no solution?