A sparse multidimensional FFT for real positive vectors
arXiv:1604.06682
Abstract
We present a sparse multidimensional FFT (sMFFT) randomized algorithm for real positive vectors. The algorithm works in any fixed dimension, requires (O(R log(R) log(N)) ) samples and runs in O( R log^2(R) log(N)) complexity (where N is the total size of the vector in d dimensions and R is the number of nonzeros). It is stable to low-level noise and exhibits an exponentially small probability of failure.
arXiv commentFixed minor typos. Corrected use of Q^{-1} in Algorithm 3 and theorem
References in corpus (4)
- A sparse Fast Fourier Algorithm for Real Nonnegative Vectors
- Fast and Efficient Sparse 2D Discrete Fourier Transform using Sparse-Graph Codes
- Sample-Optimal Average-Case Sparse Fourier Transform in Two Dimensions
- Computing a k-sparse n-length Discrete Fourier Transform using at most 4k samples and O(k log k) complexity