Coprime conditions for Fourier sampling for sparse recovery

This paper considers the spark of L × N submatrices of the N × N Discrete Fourier Transform (DFT) matrix. Here a matrix has spark m if every collection of its m − 1 columns are linearly independent. The motivation comes from such applications of compressed sensing as MRI and synthetic aperture radar, where device physics dictates the measurements to be Fourier samples of the signal. Consequently the observation matrix comprises certain rows of the DFT matrix. To recover an arbitrary k-sparse signal, the spark of the observation matrix must exceed 2k + 1. The technical question addressed in this paper is how to choose the rows of the DFT matrix so that its spark equals the maximum possible value L + 1. We expose certain coprimeness conditions that guarantee such a property.