I am currently reading Candes et. al.'s 2006 paper[1] 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[2] 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.


1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.