On the Linear Independence of Spikes and Sines
The purpose of this work is to survey what is known about the linear independence of spikes and sines. The paper provides new results for the case where the locations of the spikes and the frequencies of the sines are chosen at random. This problem is equivalent to studying the spectral norm of a random submatrix drawn from the discrete Fourier transform matrix. The proof depends on an extrapolation argument of Bourgain and Tzafriri.
© 2008 Springer. Received: 4 September 2007. Published online: 17 September 2008. Communicated by Anna Gilbert. One of the anonymous referees provided a wealth of useful advice that substantially improved the quality of this work. In particular, the referee described a version of Lemma 15 and demonstrated that it offers a simpler route to the main results than the argument in earlier drafts of this paper. Supported by NSF 0503299.
Submitted - 0709.0517.pdf