Spark under 2-D fourier sampling

We consider the spark of submatrices of 2D-DFT matrices obtained by removing certain rows and relate it to the spark of associated 1D-DFT submatrices. A matrix has spark m if its smallest number of linearly dependent columns equals m. To recover an arbitrary fc-sparse vector, the spark of an observation matrix must exceed 2fc. We consider how to choose the rows of the 2D-DFT matrix so that it is full spark, i.e. its spark equals one more than its row dimension. We consider submatrices resulting from two sets of sampling patterns in frequency space: On a straight line and on a rectangular grid. We show that in the latter case full spark is rarely obtainable, though vectors with certain sparsity patterns can still be recovered. In the former case we provide a necessary and sufficient condition for full spark, and show that lines with integer slopes cannot attain it.