Nonharmonic multivariate Fourier transforms and matrices: condition numbers and hyperplane geometry

Consider an operator that takes the Fourier transform of a discrete measure supported in X[- 12, 12) ᵈ and restricts it to a compact ᵈ. We provide lower bounds for its smallest singular value when is either a ball or cube of radius m, and under different types of geometric assumptions on X. We first show that if distances between points in X are lower bounded by a that is allowed to be arbitrarily small, then the smallest singular value is at least Cm^d/2 (m) ^-1, where is the maximum number of elements in X contained within any ball or cube of an explicitly given radius. This estimate communicates a localization effect of the Fourier transform. While it is sharp, the smallest singular value behaves better than expected for many X, including when we dilate a generic set by parameter. We next show that if there is a such that, for each x, the set X\x\ locally consists of at most r hyperplanes whose distances to x are at least, then the smallest singular value is at least C m^d/2 (m) ʳ. For dilations of a generic set by, the lower bound becomes C m^d/2 (m) ^ (-1) /d. The appearance of a 1/d factor in the exponent indicates that compared to worst case scenarios, the condition number of nonharmonic Fourier transforms is better than expected for typical sets and improve with higher dimensionality.