Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: (Nearly) Sample-Optimal Sparse Fourier Transform in Any Dimension;
  RIPless and Filterless   In this paper, we consider the extensively studied problem of computing a
$k$-sparse approximation to the $d$-dimensional Fourier transform of a length
$n$ signal. Our algorithm uses $O(k \log k \log n)$ samples, is dimension-free,
operates for any universe size, and achieves the strongest $\ell_\infty/\ell_2$
guarantee, while running in a time comparable to the Fast Fourier Transform. In
contrast to previous algorithms which proceed either via the Restricted
Isometry Property or via filter functions, our approach offers a fresh
perspective to the sparse Fourier Transform problem.

37
The categories of this paper are: supr-con
11
The categories of this paper are: hep-lat
4
The categories of this paper are: cond-mat
8
The categories of this paper are: hep-ex
31
The categories of this paper are: ao-sci
36
The categories of this paper are: cmp-lg
26
The categories of this paper are: bayes-an
0
The categories of this paper are: hep-ph
23
The categories of this paper are: solv-int
28
The categories of this paper are: alg-geom
20
The categories of this paper are: acc-phys
25
The categories of this paper are: patt-sol
21
The categories of this paper are: adap-org
3
The categories of this paper are: physics
10
The categories of this paper are: q-bio
12
The categories of this paper are: nucl-th