# Restriction of Fourier Transform

I am currently reading Candes et. al.'s 2006 paper on recovery of sparse signals from incomplete frequency samples. I am having trouble figuring out what is the form of the Fourier transform restricted to $\Omega$, $\hat{f}|_{\Omega}$, which appears in Lemma 1.2.

This restriction appears to be a bijection $\mathcal{F}_{T \to \Omega}: l_2(T) \to l_2(\Omega)$, when $|T| = |\Omega|$ and $T, \Omega$ are subsets of $\mathbb{Z}_p$, $p$ prime. Here, $l_2(C)$ denotes the space of signals with $C$ as their support.

Is there a concrete example of such a $\mathcal{F}_{T \to \Omega}$, or are we only able to prove its existence? In Terence Tao's paper containing the proof of this Lemma, the proof mentions that the matrix of $\mathcal{F}_{T \to \Omega}$'s coefficients has a form similar to that of a Vandermonde matrix, i.e. it will contain elements $(e^{- 2 \pi x_i \xi_j / p})$, which makes me suspect that we can obtain concrete examples of this linear transformation.

Yes, we can explicitely construct such an example: The DFT matrix of dimension $N$ is given by $$F=\{\exp(-j2\pi ik/N\}_{i=0,\ldots,N-1,k=0,\ldots,N-1}$$

Now, if $T,\Omega\subset\{0,1,\ldots,N-1\}$ the corresponding DFT matrix is given by

$$F_{T\rightarrow\Omega}=\{\exp(-j2\pi ik/N\}_{i\in\Omega,k\in T}$$

We can directly implement this in e.g. Python:

N = 17  # the order/dimension (P in your notation)
L = 8   # the dimension of T, Omega
# choose some random subsets of 0,...,N-1 for T and Omega
T = np.random.choice(np.arange(N), L, replace=False)
Omega = np.random.choice(np.arange(N), L, replace=False)

# Calculate the DFT matrix
t, o = np.meshgrid(T, Omega)
F = np.exp(2j*np.pi*t*o/N)

import numpy.linalg as lg
# Print its rank. It should be always equal
# to L to make F a bijection (i.e. invertible)
print (lg.matrix_rank(F))


When running above code with N=17, the rank is always 8. I've tried setting N=16, and it turns out that it can happen that the rank goes to 7 for some random configuration, i.e. F would not be a bijection.