Multiscale estimates for the condition number of non-harmonic Fourier matrices
Weilin Li · Mathematics of Computation · 2024
This paper studies the extreme singular values of non-harmonic Fourier matrices. Such a matrix of size m × s m\times s can be written as \[ Φ = [ e − 2 π i j x k ] j = 0 , 1 , … , m − 1 , k = 1 , 2 , … , s \Phi =[ e^{-2\pi i j x_k}]_{j=0,1,\dots ,m-1, k=1,2,\dots ,s} \] for some set X = { x k } k = 1 s \mathcal {X}=\{x_k\}_{k=1}^s . Its condition number controls the stability of inversion, which is of great importance to super-resolution and non-uniform Fourier transforms. Under the assumption m ≥ 6 s m\geq 6s and without any restrictions on X \mathcal {X} , the main theorems provide explicit lower bounds for the smallest singular value σ s ( Φ ) \sigma _s(\Phi ) in terms of distances between elements in X \mathcal {X} . More specifically, distances exceeding an appropriate scale τ