  This paper studies the extreme singular values of non-harmonic Fourier
matrices. Such a matrix of size $m\times s$ 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$. The main results provide explicit lower bounds
for the smallest singular value of $\Phi$ under the assumption $m\geq 6s$ and
without any restrictions on $\mathcal{X}$. They show 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
results significantly improve upon classical bounds and achieve the same rate
that was previously discovered for more restrictive settings.
