Fourier-Sparse Interpolation without a Frequency Gap

We consider the problem of estimating a Fourier-sparse signal from noisy samples, where the sampling is done over some interval [0, T] and the frequencies can be "off-grid". Previous methods for this problem required the gap between frequencies to be above 1/T, the threshold required to robustly identify individual frequencies. We show the frequency gap is not necessary to estimate the signal as a whole: for arbitrary k-Fourier-sparse signals under l2 bounded noise, we show how to estimate the signal with a constant factor growth of the noise and sample complexity polynomial in k and logarithmic in the bandwidth and signal-to-noise ratio. As a special case, we get an algorithm to interpolate degree d polynomials from noisy measurements, using O(d) samples and increasing the noise by a constant factor in l2.

Authors

• Xue Chen 0001
• Daniel M. Kane
• Eric Price 0001
• Zhao Song 0002

Keywords

• Interpolation
• Robustness
• Complexity theory
• Computer science
• Noise measurement
• Frequency estimation
• Fourier transforms
• Frequent Interruptions
• Constant Factor
• Polynomial Of Degree
• Individual Frequency
• Fourier Transform
• Gaussian Noise
• Sparsity
• First Category
• Taylor Expansion
• Presence Of Noise
• Convex Optimization
• Universal Constant
• Discrete Fourier Transform
• Outcome Categories
• Filter Function
• Linear Subspace
• Constant Approximation
• Frequency Separation
• Orthogonal Matching Pursuit
• Polynomial Interpolation
• Frequency List
• Complex Exponential
• Noisy Set
• Nyquist Sampling
• Running Time
• Fraction Of Energy
• Good Approximation
• super-resolution
• sparse recovery
• compressive sensing