We consider the problem of building numerically stable algorithms for computing Discrete Fourier Transform (DFT) of$N$- length signals with known frequency support of size$k$. A typical algorithm, in this case, would involve solving (possibly poorly conditioned) a system of equations, causing numerical instability. When$N$is a power of 2, and the frequency support is a random subset of$\mathbb{Z}_{N}$, we provide an algorithm that has (a possibly optimal)$O(k\log k)$complexity to compute the DFT while solving system of equations that are$O(1)$in size.

Suppose an$N-$length signal has known frequency support of size$k$. Given access to samples of this signal, how fast can we compute the DFT? The answer to this question depends on the structure of the frequency support. We first identify some frequency supports for which (an ideal)$O(k \log k)$complexity can be achieved, which we refer to as homogeneous sets. We give a generalization of the radix-2 FFT that enables$O(k\log k)$computation of signals with homogeneous frequency support. We use homogeneous sets as building blocks to construct more complex support structures for which the complexity of$O(k\log k)$is achievable. Applying these ideas, we present an$O(k\log ^{2}k)$algorithm for computing the DFT of signals whose frequency support is additively structured. We also present partial converses.

We consider the problem of finding the Discrete Fourier Transform (DFT) of$N$-length signals with known frequency support of size$k$. When$N$is a power of 2 and the frequency support is a spectral set, we provide an$O(k\log k)$algorithm to compute the DFT. Our algorithm uses some recent characterizations of spectral sets and is a generalization of the standard radix-2 algorithm.

We consider the problem of recovering N length vectors h that vanish on a given set of indices and satisfy h*h = h. We give some results on the structure of such h when N is a product of two primes, and investigate some bounds and their connections to certain graphs defined on ZN.

We study the problem of finding unitary submatrices of the$N \times N$discrete Fourier transform matrix, in the context of interpolating a discrete bandlimited signal using an orthogonal basis. This problem is related to a diverse set of questions on idempotents on$\mathbb {Z}_{N}$and tiling$\mathbb {Z}_{N}$. In this work, we establish a graph-theoretic approach and connections to the problem of finding maximum cliques. We identify the key properties of these graphs that make the interpolation problem tractable when$N$is a prime power, and we identify the challenges in generalizing to arbitrary$N$. Finally, we investigate some connections between graph properties and the spectral-tile direction of the Fuglede conjecture.

Consider a unitary (up to scaling) submatrix of the Fourier matrix with rows indexed by I and columns indexed by J. From the column index set J we construct a graph G so that the row index set I determines a max-clique. Interpreting G as coming from an association scheme gives certain bounds on the clique number, which has possible applications to Fuglede's conjecture on spectral and tiling sets.

We study the problem of interpolating all values of a discrete signal f of length N when dJ. The sampling pattern for f is specified by an index set I, and is said to be a universal sampling set if samples in the locations I can be used to interpolate signals from BJfor any J. When N is a prime power we give several characterizations of universal sampling sets, some structure theorems for such sets, an algorithm for their construction, and a formula that counts them. There are also natural applications to additive uncertainty principles.