A sublinear algorithm for the recovery of signals with sparse Fourier transform when many samples are missing

摘要

We present a sublinear randomized algorithm to compute a sparse Fourier transform for nonequispaced data of a special type. More precisely, we address the situation where a signal S is known to consist of N equispaced time samples, of which only L < N samples are available. If the ratio p = L/N is much smaller than 1, the available data typically look like nonequispaced samples, with little or no visible trace of the equispacing of the full set of N samples. We extend an approach for equispaced data that was presented in [J. Zou, A.C. Gilbert, M. Strauss, I. Daubechies, Theoretical and experimental analysis of a randomized algorithm for sparse Fourier transform analysis, J. Comput. Phys. 211 (2006) 572-595]; the extended algorithm reconstructs, from the incomplete data, a near-optimal B-term representation R with high probability 1 — δ, in time and space poly(B, log(N), log(1/δ), ε~(-1) ), such that ‖ S — R‖_2~2≤ (1 + ε) ‖S — R_(opt)~B‖_2~2, where R_(opt)~B is the optimal B-term Fourier representation of signal S. The sublinear poly (log N) time is compared to the superlinear O(L~(1+(d-1)/β) log L) time requirement of the present best known inverse nonequispaced fast Fourier transform (INFFT) algorithms, in the sense of weighted norm with the number of dimensions d and smoothness parameter β. Numerical experiments support the advantage of our algorithm in speed over other methods for sparse signals: it already outperforms the INFFT for large but realistic size N and works well even in the situation of a large percentage of missing data and in the presence of large noise.