SCIENCE@home

A sparse multidimensional FFT for real positive vectors

Pierre-David Létourneau,Harper Langston,Benoît Meister,R. Lethin

Published 2016 in arXiv.org

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.

PUBLICATION RECORD

  • Publication year

    2016

  • Venue

    arXiv.org

  • Publication date

    2016-04-22

  • Fields of study

    Mathematics, Computer Science

  • Identifiers
    arXiv 1604.06682
  • External record

    Open on Semantic Scholar

  • Source metadata

    Semantic Scholar

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-35 of 35 references · Page 1 of 1

CITED BY