In this paper modified variants of the sparse Fourier transform algorithms from [14] are presented which improve on the approximation error bounds of the original algorithms. In addition, simple methods for extending the improved sparse Fourier transforms to higher dimensional settings are developed. As a consequence, approximate Fourier transforms are obtained which will identify a near-optimal k-term Fourier series for any given input function, @math time (neglecting logarithmic factors). Faster randomized Fourier algorithm variants with runtime complexities that scale linearly in the sparsity parameter k are also presented.
Let @math be the @math Discrete Fourier Transform (DFT) matrix defined by @math , @math be a given function, and @math be the vector of @math equally spaced samples from @math on @math . In this case Theorem tells us that collecting the @math function samples determined by @math will be sufficient to accurately approximate the discrete Fourier transform of @math with high probability. More precisely, if @math is input to a recovery algorithm known as CoSaMP @cite_12 the following theorem holds.
@cite_12
2592413265 2924908021 2146509513 2112502349
We consider the problem of recovering a compactly supported function from a finite collection of pointwise samples of its Fourier transform taken nonuniformly. First, we show that under suitable conditions on the sampling frequencies---specifically, their density and bandwidth---it is possible to recover any such function @math in a stable and accurate manner in any given finite-dimensional subspace, in particular, one which is well suited for approximating @math . In practice, this is carried out using so-called nonuniform generalized sampling (NUGS). Second, we consider approximation spaces in one dimension consisting of compactly supported wavelets. We prove that a linear scaling of the dimension of the space with the sampling bandwidth is both necessary and sufficient for stable and accurate recovery. Thus wavelets are, up to constant factors, optimal spaces for reconstruction. Let @math be an @math Fourier matrix over @math for some prime @math . We improve upon known lower bounds for the number of rows of @math that must be sampled so that the resulting matrix @math satisfies the restricted isometry property for @math -sparse vectors. This property states that @math is approximately @math for all @math -sparse vectors @math . In particular, if @math , we show that @math rows must be sampled to satisfy the restricted isometry property with constant probability. This article describes a computational method, called the Fourier sampling algorithm. The algorithm takes a small number of (correlated) random samples from a signal and processes them efficiently to produce an approximation of the DFT of the signal. The algorithm offers provable guarantees on the number of samples, the running time, and the amount of storage. As we will see, these requirements are exponentially better than the FFT for some cases of interest. We consider the problem of the reconstruction of a continuous-time function f(x) spl isin H from the samples of the responses of m linear shift-invariant systems sampled at 1 m the reconstruction rate. We extend Papoulis' generalized sampling theory in two important respects. First, our class of admissible input signals (typ. H=L sub 2 ) is considerably larger than the subspace of band-limited functions. Second, we use a more general specification of the reconstruction subspace V( spl psi ), so that the output of the system can take the form of a band-limited function, a spline, or a wavelet expansion. Since we have enlarged the class of admissible input functions, we have to give up Shannon and Papoulis' principle of an exact reconstruction. Instead, we seek an approximation f spl isin V( spl psi ) that is consistent in the sense that it produces exactly the same measurements as the input of the system. This leads to a generalization of Papoulis' sampling theorem and a practical reconstruction algorithm that takes the form of a multivariate filter. In particular, we show that the corresponding system acts as a projector from H onto V( spl psi ). We then propose two complementary polyphase and modulation domain interpretations of our solution. The polyphase representation leads to a simple understanding of our reconstruction algorithm in terms of a perfect reconstruction filter bank. The modulation analysis, on the other hand, is useful in providing the connection with Papoulis' earlier results for the band-limited case. Finally, we illustrate the general applicability of our theory by presenting new examples of interlaced and derivative sampling using splines.