We investigate the problem of reconstructing sparse multivariate trigonometric polynomials from few randomly taken samples by Basis Pursuit and greedy algorithms such as Orthogonal Matching Pursuit (OMP) and Thresholding. While recovery by Basis Pursuit has recently been studied by several authors, we provide theoretical results on the success probability of reconstruction via Thresholding and OMP for both a continuous and a discrete probability model for the sampling points. We present numerical experiments, which indicate that usually Basis Pursuit is significantly slower than greedy algorithms, while the recovery rates are very similar.
@cite_40: We analyze a sublinear RA@?SFA (randomized algorithm for Sparse Fourier analysis) that finds a near-optimal B-term Sparse representation R for a given discrete signal S of length N, in time and space poly(B,log(N)), following the approach given in [A.C. Gilbert, S. Guha, P. Indyk, S. Muthukrishnan, M. Strauss, Near-Optimal Sparse Fourier Representations via Sampling, STOC, 2002]. Its time cost poly(log(N)) should be compared with the superlinear @W(NlogN) time requirement of the Fast Fourier Transform (FFT). A straightforward implementation of the RA@?SFA, as presented in the theoretical paper [A.C. Gilbert, S. Guha, P. Indyk, S. Muthukrishnan, M. Strauss, Near-Optimal Sparse Fourier Representations via Sampling, STOC, 2002], turns out to be very slow in practice. Our main result is a greatly improved and practical RA@?SFA. We introduce several new ideas and techniques that speed up the algorithm. Both rigorous and heuristic arguments for parameter choices are presented. Our RA@?SFA constructs, with probability at least 1-@d, a near-optimal B-term representation R in time poly(B)log(N)log(1 @d) @e^2log(M) such that @?S-R@?"2^2=<(1+@e)@?S-R"o"p"t@?"2^2. Furthermore, this RA@?SFA implementation already beats the FFTW for not unreasonably large N. We extend the algorithm to higher dimensional cases both theoretically and numerically. The crossover point lies at N 70,000 in one dimension, and at N 900 for data on a NxN grid in two dimensions for small B signals where there is noise.
@cite_26: Abstract 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 δ ) , e −1 ) , such that ‖ S − R ‖ 2 2 ⩽ ( 1 + e ) ‖ 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.
The striking point in these algorithms is the fact that the computation time scales sublinear'' as @math in the dimension @math . However, numerical experiments in @cite_40 @cite_26 show even for small sparsities @math a rather large crossover point with the classical FFT which scales as @math . It seems that in practice these algorithms require much more samples than OMP and BP, so that the main concern of these methods is speed rather than a minimal number of samples.