Paper detail

How exponentially ill-conditioned are contiguous submatrices of the Fourier matrix?

We show that the condition number of any cyclically contiguous $p\times q$ submatrix of the $N\times N$ discrete Fourier transform (DFT) matrix is at least $$ \exp \left( \fracπ{2} \left[\min(p,q)- \frac{pq}{N}\right] \right)~, $$ up to algebraic prefactors. That is, fixing any shape parameters $(α,β):=(p/N,q/N)\in(0,1)^2$, the growth is $e^{ρN}$ as $N\to\infty$ with rate $ρ= \fracπ{2}[\min(α,β)- αβ]$. Such Vandermonde system matrices arise in many applications, such as Fourier continuation, super-resolution, and diffraction imaging. Our proof uses the Kaiser-Bessel transform pair (of which we give a self-contained proof), and estimates on sums over distorted sinc functions, to construct a localized trial vector whose DFT is also localized. We warm up with an elementary proof of the above but with half the rate, via a periodized Gaussian trial vector. Using low-rank approximation of the kernel $e^{ixt}$, we also prove another lower bound $(4/eπα)^q$, up to algebraic prefactors, which is stronger than the above for small $α, β$. When combined, the bounds are within a factor of two of the numerically-measured empirical asymptotic rate, uniformly over $(0,1)^2$, and they become sharp in certain regions. However, the results are not asymptotic: they apply to essentially all $N$, $p$, and $q$, and with all constants explicit.