# DFT Matrix Oversampled In Frequency?

Edit 2: I am trying to replicate results from this paper Compressed Sensing with Coherent and Redundant Dictionaries. On page 3 the "oversampled DFT" is mentioned as an example of an "overcomplete frame whose columns may be highly correlated".

Edit: Replaced magnitude plots with angle plots for all matrices, and included my plotting code for clarity.

Does there exist a (potentially non-square) DFT matrix which is oversampled in frequency? By this I mean a DFT matrix where the sampled frequencies are taken over smaller evenly-spaced intervals than a standard DFT. I would expect this matrix to be a frame with highly correlated columns.

Background:

1. The standard DFT matrix $$W$$ is an $$N \times N$$ orthogonal matrix whose $$k^{th}$$ column is given by \begin{align} [W]_k & = \frac{1}{\sqrt{N}} e^{- 2 \pi i j k / N}, \hspace{0.2in} j = 0, \ldots, N-1 \end{align} where $$k=0, \ldots, N-1$$.
2. I have seen mentioned an "over complete" DFT $$W_o$$ whose $$k^{th}$$ column is given by \begin{align} [W_o]_k & = \frac{1}{\sqrt{NM}} e^{- 2 \pi i j k / (NM)}, \hspace{0.2in} j = 0, \ldots, NM-1 \end{align} with $$k=0, \ldots, MN-1$$. Here, the fundamental frequency $$2 \pi / (NM)$$ is smaller than that of the non-over complete DFT $$2 \pi/N$$, and we take $$NM$$ steps between DC and the highest frequency. Thus, we should get $$M$$ times the standard number of frequency steps from DC to $$2 \pi$$.

My problem is that I have implemented both in Python expecting the second to have more correlated columns, but this is not the case (code & images below).

Is there an oversampled DFT matrix that I am missing? I am thinking an $$LN \times N$$ matrix whose $$k^{th}$$ column is given by \begin{align} [W_{os}]_k & = \frac{1}{\sqrt{N}} e^{-2 \pi i j k / LN}, \hspace{0.2in} j = 0, 1, \ldots, N-1 \end{align} and $$k=0, \frac{1}{L}, \frac{2}{L}, \ldots, N-1$$. In this case, the fundamental frequency is the same as the standard DFT ($$2 \pi /N$$), but now we are taking $$LN$$ steps between DC and the max. We have now $$LN$$ columns, representing the $$LN$$ frequencies, and now the rows are highly correlated as desired (see below on the far right).

Can anyone provide insight on whether I am correct in my formulation of this oversampled DFT? And if not, where I went wrong? Thank you!

def standard_dft(N):
k, j = np.meshgrid(np.arange(N), np.arange(N))
omega = np.exp( - 2 * np.pi * 1J / N )
W = omega **(k * j) / np.sqrt(N)
return W

def overcomplete_dft(N, M):
k, j = np.meshgrid(np.arange(N*M), np.arange(N*M))
omega = np.exp( - 2 * np.pi * 1J / (N * M) )
W = np.power(omega, k * j) / np.sqrt(N * M)
return W

def oversampled_dft(N, L):
k, j = np.meshgrid(np.linspace(0, N-1, N*L), np.arange(N))
omega = np.exp( - 2 * np.pi * 1J / (N*L) )
W = np.power( omega, j * k ) / np.sqrt(N)
return W

N = 32
M = 8
L = 8
W1 = standard_dft(N)
W1g = W1.conj().T @ W1
W2 = overcomplete_dft(N, M)
W2g = W2.conj().T @ W2
W3 = oversampled_dft(N, L)
W3g = W3.conj().T @ W3

# Show matrices
fig, ax = plt.subplots(2, 3)
ax[0, 0].imshow(np.angle(W1), vmin=-np.pi, vmax=np.pi)
ax[0, 0].set_title(str(N)+'-Point DFT Matrix')
ax[0, 1].imshow(np.angle(W2), vmin=-np.pi, vmax=np.pi)
ax[0, 1].set_title(str(M)+'x Over Complete DFT')
ax[0, 2].imshow(np.angle(W3), aspect=L, vmin=-np.pi, vmax=np.pi)
ax[0, 2].set_title(str(L)+'x Oversampled DFT')
# Show gram matrices
ax[1, 0].imshow(abs(W1g), vmin=0, vmax=1)
ax[1, 0].set_title('Gram Matrix')
ax[1, 1].imshow(abs(W2g), vmin=0, vmax=1)
ax[1, 1].set_title('Gram Matrix')
ax[1, 2].imshow(abs(W3g), vmin=0, vmax=1)
ax[1, 2].set_title('Gram Matrix')
fig.tight_layout()


• Any non-square DFT matrix won’t be a DFT matrix in the traditional sense as the basis vectors can’t be guaranteed to be pairwise orthonormal. You will get some arbitrary frequency representation that may approximate a DFT, but it won’t be exactly a DFT. If you want to do oversampling, you can create an $LN$-by-$LN$ DFT matrix and pad your signal with $LN-N$ zeros. You can get an arbitrarily fine frequency domain representation, but it won’t be a Fourier representation as the DFT isn’t defined in that way. Commented Mar 14 at 3:59
• What exactly are you plotting here? the magnitudes of any DFT-like matrices would all be constant. Commented Mar 14 at 8:01
• @Hilmar, I replaced the unhelpful magnitude plots with angle plots for all matrices. Commented Mar 14 at 15:17
• Would you achieve your goals by zero-padding the (non-transformed-domain) input by a factor of M (M>1) prior to doing a M-sample DFT? Commented Mar 14 at 17:39
• @KnutInge I am using the DFT matrix as a dictionary for compressed sensing (the objective is sparse representation of sinusoids). I could zero-pad the coefficient vector, but I would prefer to construct the DFT dictionary ahead of time at a finer frequency resolution instead. Commented Mar 14 at 18:53

A DFT-like operation can be defined as

$$X(\omega) = \sum_{n=0}^{N-1} x[n] e^{-j2\pi n \omega} \tag{1}$$

For any set of discrete frequencies $$<\omega_m>$$ of length M the operation can be can be written in matrix./vector form with a DFT-like matrix where the elements are

$$M_{nm} = e^{-j2\pi \cdot n \cdot \omega_m} \tag{2}$$

If we chose $$\omega_m = \frac{m}{N}, m = 0...N-1$$ we get the standard DFT with the standard DFT matrix, but you can perform the operation on any frequency grid you want.

If you want to "oversample" the standard DFT, you can technically do this two ways: increase the sample rate or use a denser frequency grid. For example if you want to oversample by a factor of 2 you can chose $$\omega_m = \frac{m}{2N}, m = 0...2N-1$$. FWIW: the same thing can be done much more efficiently with zero padding in the time domain.

The properties of the DFT-like matrix depends on the specific frequency grid that you are using since it's all complex exponentials, all of the matrix elements should have unity magnitude, i.e.

$$|M_{nm}| = 1$$

and I'm a bit confused on what exactly your plots are supposed to be showing.

Does there exist a (potentially non-square) DFT matrix which is oversampled in frequency? By this I mean a DFT matrix where the sampled frequencies are taken over smaller evenly-spaced intervals than a standard DFT.

You can have a DFT matrix that is oversampled in frequency if it is equally oversampled in time, i.e. it would still be a square matrix.

I would expect this matrix to be a frame with highly correlated columns.

Why would you expect the columns to be highly correlated? The basis vectors of the DFT form an orthonormal basis, which implies they are statistically uncorrelated.

There are two primary reasons why you cannot have a non-square DFT matrix. First, assuming appropriate scaling, the DFT is a unitary transform which implies that the DFT matrix is a unitary matrix. Unitary matrices have the property that their inverse is equal to their conjugate transpose, i.e.

$$$$UU^{-1} = UU^{H} = I$$$$

This means they have to be a square matrix.

The second reason is that in order for the basis to be a Fourier basis, they must be orthonormal. Orthonormal includes orthogonality, which means that the complex inner product of any two basis vectors is 0, except for a basis vector with itself. If you have the spacings

$$$$\delta_{k} = \frac{\delta_{j}}{L}; \: L \neq 1$$$$

your basis vectors will not be pairwise orthonormal, and therefore you will not end up with a Fourier representation as your basis vectors won't be perpendicular.

Now, with a non-square DFT matrix, you will get an arbitrary frequency representation. Viewing matrix multiplication as filtering, you will end up with a filterbank that has more taps than you have signal samples, requiring you to zero-pad your signal. However, this is not a Fourier representation as your transform basis is not an orthogonal basis.

• In response to "Why would you expect the columns to be highly correlated?": I am trying to replicate results from [this paper][arxiv.org/abs/1005.2613] (see 2nd edit). On page 3 the "oversampled DFT" is mentioned as an example of an "overcomplete frame whose columns may be highly correlated". I expect the oversampled DFT columns to be correlated because they complex exponentials with very similar frequencies (when oversampled in frequency). Commented Mar 14 at 18:49
• Ah, I see, you meant of the oversampled DFT matrix. They are not highly correlated simply because their frequencies are close. If you have a $2^{24}$ DFT, the frequencies are incredibly closely spaced in terms of digital frequencies, yet the basis vectors are still orthogonal. The "DFT" matrix they're talking about has correlated columns because the basis vectors are no longer periodic within the DFT window, meaning they are no longer guaranteed to be orthogonal. Commented Mar 14 at 19:47
• Hello @Baddioes, thank you for the clarification. Are any of the matrices I defined above the correct formulation for such a "DFT" matrix with correlated columns? Commented Mar 14 at 20:31
• @coult099 the $LN$-by-$N$ matrix would have correlated columns Commented Mar 14 at 21:29