Multiscale estimates for the condition number of non-harmonic Fourier matrices

This paper studies the extreme singular values of non-harmonic Fourier matrices. Such a matrix can be written as $\Phi=[ e^{-2\pi i j x_k}]_{j=0,1,\dots,m-1, k=1,2,\dots,s}$ for some set $\mathcal{X}=\{x_k\}_{k=1}^s$ and $m\geq s$. A main result provides an explicit lower bound for the smallest singular value of $\Phi$ under the assumption $m\geq 6s$ and without any restrictions on $\mathcal{X}$. It shows that for an appropriate scale $\tau$ determined by a density criteria, interactions between elements in $\mathcal{X}$ at scales smaller than $\tau$ are most significant and depends on the multiscale structure of $\mathcal{X}$ at fine scales, while distances larger than $\tau$ are less important and only depend on the local sparsity of the far away points. Theoretical and numerical comparisons show that the main result significantly improves upon classical bounds and achieves the same rate that was previously discovered for more restrictive settings.