2016 · 29 citations · 30 references
ComputingComputer ScienceMathematicsAlgorithmsTheory Of ComputationTime Series AnalysisApproximation AlgorithmsDigital Signal ProcessingFourier AnalysisSignal ProcessingSpectral AnalysisFourier-domain Signal ProcessingPolynomial Time ComplexitySample ComplexitySample Complexity AnalysisSignal-to-noise RatioSparse ReconstructionSparse Signal ProcessingSparse Signal Representation
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.
30
Gaussian elimination is not optimal
Volker Strassen · Numerische Mathematik · 1969 · 2.5K citations
Shift-register synthesis and BCH decoding
J. Massey · IEEE Transactions on Information Theory · 1969 · 2.2K citations
Compressed Sensing Off the Grid
Gongguo Tang, Badri Narayan Bhaskar, Parikshit Shah et al. · IEEE Transactions on Information Theory · 2013 · 1.2K citations
Natural Sciences, Electrical Engineering, Information Theory +16