A sparse multidimensional FFT for real positive vectors

Autor:	Letourneau, Pierre-David, Langston, Harper, Meister, Benoit, Lethin, Richard
Rok vydání:	2016
Předmět:	Computer Science - Data Structures and Algorithms
Druh dokumentu:	Working Paper
Popis:	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. Comment: Fixed minor typos. Corrected use of Q^{-1} in Algorithm 3 and theorem
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1604.06682 Zobrazit plný text záznamu View this record from Arxiv