On the exponential rate of the condition number of Fourier submatrices and Vandermonde matrices

Abstract

The discrete Fourier transform matrix is one of the most important matrices in linear algebra, and submatrices of it arise in a variety of applications. Though the discrete Fourier transform matrix is unitary, its submatrices can be exponentially ill-conditioned, an obstacle to accurate computation. This work resolves the exact rate of the exponential ill-conditioning for square submatrices with contiguous rows and columns. As a consequence, we obtain a tight upper bound of $2G/\pi$ on the exponential rate for all submatrices with contiguous columns, or, equivalently, all Vandermonde submatrices with distinct support points, where $G$ is Catalan's constant. These results follow from a more general analysis of Vandermonde and Vandermonde-like matrices for which exact estimates for exponential ill-conditioning are developed in terms of logarithmic potentials.