Abstract | ||
---|---|---|
We present a sparse multidimensional FFT randomized algorithm (sMFFT) for positive real vectors. The algorithm works in any fixed dimension, requires an (almost)-optimal number of samples ($mathcal{O}left( R logleft( frac{N}{R} right ) right )$) and runs in $mathcal{O}left( R log(R) logleft( frac{N}{R} right ) right )$ complexity (where $N$ is the size of the vector and $R$ the number of nonzeros). It is stable to noise and exhibits an exponentially small probability of failure. |
Year | Venue | Field |
---|---|---|
2016 | arXiv: Data Structures and Algorithms | Discrete mathematics,Randomized algorithm,Combinatorics,Probability of failure,Fast Fourier transform,Mathematics |
DocType | Volume | Citations |
Journal | abs/1604.06682 | 0 |
PageRank | References | Authors |
0.34 | 11 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Pierre-David Létourneau | 1 | 0 | 2.03 |
Harper Langston | 2 | 76 | 6.41 |
Benoît Meister | 3 | 138 | 12.84 |
Richard Lethin | 4 | 118 | 17.17 |