DFT Matrix Oversampled In Frequency?

Question

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()

Answer 1

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.

Answer 2

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.

\begin{equation} UU^{-1} = UU^{H} = I \end{equation}

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

\begin{equation} \delta_{k} = \frac{\delta_{j}}{L}; \: L \neq 1 \end{equation}

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.