# 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?

• This (and your other question) sounds like a strange approach to me. What are you actually trying to do, at a higher level? They seem like very similar questions; instead of using the full length-$N$ vector, you could truncate it (and the matrix $T$) to the positive frequency rows only. Perhaps I'm missing something. It also seems strange to say that $X$ comes from a QAM constellation, yet it is the result of a DFT. It sounds like maybe this is for an OFDM-related application? In that case though, you would have a lot of unused subcarriers if you aren't using the negative frequencies. May 19 '13 at 18:28
• Thanks for the comment. Yes, you got the higher level idea. The applications is a DMT system, for which only the positive frequencies are populated (it is baseband). $X$ is mapped from QAM constellations with different sizes (different bit loading). The matrix $T$ is a pre-equalizer. Instead of using $N \times N$ matrix, which gives $N^2$ CMAC operations, I want to use only a pre-equalize with size $(N/2+1)\times(N/2 + 1)$. Yes, I want to to truncate and use only positive frequency rows, but the only way would be to use an $(N/2+1)\times(N)$ matrix multiplying the full length-$N$ vector? May 19 '13 at 21:12
• I do not understand why you can't simply use the positive frequencies of vector $X$ and the positive frequencies of vector $Y$. For this you obviously only need and $(N/2+1)\times (N/2+1)$ matrix. The only restriction you have are the real elements at DC and Nyquist. This can be easily solved with the (upper left part of the) matrix I suggested for your other question. Let me know if I miss anything. May 19 '13 at 22:27
• @MattL., thanks once again. I might be missing something. For example, X(2) is inner product between all the $N$ elements of the second row in $\mathbf{T}$ and the $\mathbf{X}$ vector. How could I get X(2) using only the first ($N/2 +1$) columns of the second row in T, provided that this row does not present conjugate symmetry? Remember only the main diagonal and the rows and columns correspondent to Nyquist and DC present conjugate symmetry. That's why I don't see an straightforward answer. May 19 '13 at 22:56
• Try to see it like this: your vectors $X$ and $Y$ are completely determined by the positive frequencies (because the corresponding time signals are real). So any matrix $T$ you come up with must take this redundancy into account and cannot add any extra information. So the best approach - without loss of generality - must be to simply relate the reduced vectors $X$ and $Y$ to each other by a linear transformation. Any transformation that can be done between the complete (length $N$) vectors can also be done between the non-redundant parts of it (i.e. the positive frequencies). May 20 '13 at 10:22

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.

• I totally agree. This is actually the way I came up with the answer to @igorauad 's previous question. By simply considering a transformation between the non-redundant parts of $\mathbf{x}$ and $\mathbf{y}$ and then artificially extending the transformation matrix to the full-length redundant vectors (which is a fun exercise, albeit a bit useless ...). May 20 '13 at 10:27
• Once again, thank you very much. When you make $\mathbf{y}^{+} = \sum \limits_{k=1}^{N/2} x_k \mathbf{t_k}$, you are trying to obtain the value of $y_k$ using only half of the row. However, remember the rows in $\mathbf{T}$ do not present conjugate symmetry (except the DC and the Nyquist row). In this case, even though the symbol $\mathbf{x}$ has conjugate symmetry, the inner product with the row won't be complex conjugate for the positive and negative rows. I included a code in the original question to illustrate better. May 20 '13 at 15:06
• But why do you care about the conjugate symmetry being preserved? As I said above, the negative-frequency bins that you're worrying so much about don't carry any information. What is the purpose of going through all of the work of devising a specially-structured operator that preserves this informationless property? You should be able to just operate on the positive bins and then reflect them to yield their negative counterparts. May 20 '13 at 15:08
• Based on the code I appended to the question, I am understanding you are stating that T(:,1:N/2+1)*x(1:N/2+1) would return the positive frequencies, which I don't think is true. The point is, the structure of the precoder is inevitably just like variable T in the code I suggested. I care about this conjugate symmetry because the results are not equal for the inner product between the positive frequencies and the "positive columns", when comparing to the inner product between the negative frequencies and the "negative columns". I really appreciate your help. May 20 '13 at 15:24
• One thing I know is true is that: T(2,1:N/2+1)*x(1:N/2+1) + conj(T(N,1:N/2+1))*conj(x(1:N/2+1)) is equal to: T(2,:)*x, provided that the DC and Nyquist rows and columns in the precoded are zero (which is the case for my precoder) May 20 '13 at 15:28

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.

@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?