How ill-conditioned can submatrices of the Fourier matrix be?
This resolves a fundamental open problem about the conditioning of Fourier submatrices, providing tight bounds that are important for numerical linear algebra and applications like signal processing.
The paper determines the exact exponential rate of ill-conditioning for square submatrices of the discrete Fourier transform matrix with contiguous rows and columns, obtaining a tight upper bound of 2G/π (where G is Catalan's constant) for all submatrices with contiguous columns. The results extend to Vandermonde and Vandermonde-like matrices.
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 $2 G/π$ on the exponential rate for all submatrices with contiguous columns, where $G$ is Catalan's constant. These results follow from a more general analysis of Vandermonde and Vandermonde-like matrices for which similarly tight bounds are developed.